A probability theory question which I came across lately and where the answer unexpectedly turned out to be not so easy?!Given a perfect coin. Throw the coin 12 times. Have a look at the longest "trend", that is the biggest number of consecutive throws that have the same outcome. Example: abaabbbababa (longest trend = 3)What is the probability that a) the longest trend when throwing 12 times is AT LEAST x throws long (x=1,...,12)?b) the longest trend when throwing 12 times is EXACTLY x throws long (x=1,...,12)?Any suggestions hwo to generalize this to a variable number of throws?

If (b) is solved, (a) is automatically solved. It's only one question

The answer to b) is :{2, 464, 1388, 1126, 606, 286, 128, 56, 24, 10, 4, 2}/4096and the answer to a) follows :{4096, 4094, 3630, 2242, 1116, 510, 224, 96, 40, 16, 6, 2}/4096Answers to b) for different numbers of throws are:{{2, {2, 2}/4}, {3, {2, 4, 2}/8}, {4, {2, 8, 4, 2}/16}, {5, {2, 14, 10, 4, 2}/32}, {6, {2, 24, 22, 10, 4, 2}/64}, {7, {2, 40, 46, 24, 10, 4, 2}/128}, {8, {2, 66, 94, 54, 24, 10, 4, 2}/256}, {9, {2, 108, 188, 118, 56, 24, 10, 4, 2}/512}, {10,{2, 176, 370, 254, 126, 56, 24, 10, 4, 2}/1024}, {11,{2, 286, 720, 538, 278, 128, 56, 24, 10, 4, 2}/2048}, {12,{2, 464, 1388, 1126, 606, 286, 128, 56, 24, 10, 4, 2}/4096}}

Could you elaborate a little bit more on the way you came to your answers? Or did you count?

Counting (Mathematica) ... An interesting pattern is how the values converge ...For x=n limit is 2/2^nFor x=n-1 limit is 4/2^nFor x=n-2 limit is 10/2^nFor x=n-3 limit is 24/2^nFor x=n-4 limit is 56/2^nFor x=n-5 limit is 128/2^nIf we look at the sequence {1,2,5,12,28,64, ...} in Sloane we find:A045623 Number of 1's in all compositions of n+1The next term in A045623 is 144, and without counting further we could hazard a guess that for x=n-6 the limit is 288.

I still dont get it ! Can someone explain the answer?

The Mathematica code (version 6) is: f[n_] := Sort[Tally[Map[Max, Map[Map[Length, #] &, Map[Split, Tuples[{a, b}, n]]]]]];g[n_] := Transpose[f[n]][[2]];h[n_] := Reverse[Accumulate[Reverse[g[n]]]];The answer to b) is given by g[12], and the answer to a) is given by h[12] (cumulative sum, nothing to see here, move along people...).So Tuples[{a,b},n] generates a list of all possible n-tuples of elements from {a,b}.We then split each tuple (separate into sublists consisting of runs of identical elements).After that we find the size (Length) of each sublist.Then we find the maximum size of the sublists of each n-tuple.Then we use Tally (frequencies in v 5) to count those maximum sizes over the whole set of n-tuples.I did not look for an explicit formula, I usually find the results first (simulations most of the time), and then look at them trying to find some pattern.

I get the generalized formula as:P(X >= i) = [2 * 2^(n-i) / 2^n] * [(n-i+1)/(nCi)]Term 1: Probability of getting the same face (=2) for i tosses and getting any face for the rest (2^(n-i) ). These i tosses need not be sequential.Term 2: This is the fraction of i SEQUENTIAL tosses in a process of 'selecting' i tosses from a total of n tosses (nCi = combination).My formula equals MCarreira's end point values only.