login
Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.
0

%I #60 May 31 2019 09:50:55

%S 1,2,5,11,23,45,90,179,357,712,1422,2842,5681,11360,22716,45430,90856,

%T 181709,363413,726822,1453640,2907276,5814546,11629086,23258166,

%U 46516327,93032647

%N Least number of tosses of a fair coin needed to have an even chance or better of getting a run of at least m consecutive heads or consecutive tails.

%C There are a family of sequences that represent the number of sequences of tosses of a fair coin to n tosses where there are no runs of m or more consecutive heads or consecutive tails. Some are given in this Encyclopedia. Their general form is given as part of the formula below. As n increases, the proportion of sequences of tosses that meet this condition decreases. When that proportion becomes a half or less of the total number of sequences of tosses, there is an even or better chance that a run of m consecutive heads or m consecutive tails occurs.

%C There is actually a family of sequences of which the above sequence is an instance: those in which, for successive values of m, r*g(n) <= 2^n for r > 1.

%C a(n) - ceiling((log 2)*2^n + (1-log 2)*n + (log 2)/2-2) equals 0 or (almost never) 1 for all n. Obtained using Weisstein's exact formula for Fibonacci k-step number seeing that the function g(N) described in the Formula section is 2*A092921(n-1,N+1). - _Andrey Zabolotskiy_, Nov 01 2016

%D Marcus du Sautoy, The Number Mysteries, Fourth Estate, 2011, pages 126 - 127.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>

%F For successive integers m, where g(n) is the number of sequences of tosses of a fair coin with runs of fewer than m consecutive heads or tails out of all possible sequences of tosses to n tosses, g(n) = 2^n where n <= m-1, and thereafter g(n) = g(n-1) + g(n-2) + ... + g(n-m+1) and a(m) = the least value of n for which 2g(n) <= 2^n.

%p a:= proc(n) option remember; local l, j; Digits:= 50;

%p if n<3 then n else l:= 0$n;

%p for j from 0 while l[n]<1/2 do l:= seq(

%p (`if`(i=1, 1.0, l[i-1])+l[n-1])/2, i=1..n)

%p od; j

%p fi

%p end:

%p seq(a(n), n=1..16); # _Alois P. Heinz_, Nov 01 2016

%t a[n_] := a[n] = Module[{l, j}, If[n < 3, n, l = Table[0, {n}]; For[j = 0, l[[n]] < 1/2, j++, l = Table[(If[i == 1, 1, l[[i - 1]]] + l[[n - 1]])/2, {i, n}]]; j]];

%t Array[a, 16] (* _Jean-François Alcover_, May 31 2019, after _Alois P. Heinz_ *)

%o (Python)

%o def a(m):

%o if m == 1:

%o return 1

%o g = [2**i for i in range(1, m)]

%o sg, lim, n = sum(g), 2**(m-1), m

%o while True:

%o g.append(sg)

%o sg <<= 1

%o sg -= g.pop(0)

%o if g[-1] <= lim:

%o return n

%o lim <<= 1

%o n += 1

%o print([a(i) for i in range(1, 15)])

%o # _Andrey Zabolotskiy_, Nov 01 2016

%o (PARI) step(v)=my(n=#v); concat([sum(i=1,n-1,v[i])], concat(vector(n-2,i, v[i]), 2*v[n]+v[n-1]))

%o a(n)=if(n<3, return(n)); my(v=vector(n), flips=1, needed=1/2); v[1]=1; while(v[n]<needed, v=step(v); needed<<=1; flips++); flips \\ _Charles R Greathouse IV_, Nov 02 2016

%o (PARI) a(n)=if(n<3, return(n)); my(M=2^(n-1),v=powers(2,n-1)[2..n],i=1,m=n); while(1, v[i]=vecsum(v); if(v[i]<=M, return(m)); if(i++>#v, i=1); M*=2; m++) \\ _Charles R Greathouse IV_, Nov 02 2016

%Y Cf. A135491, A135492, A135493.

%K nonn,more

%O 1,2

%A _Tim Miles_, Nov 01 2016

%E a(11)-a(22) from _Andrey Zabolotskiy_, Nov 01 2016

%E a(23)-a(27) from _Alois P. Heinz_, Nov 02 2016