A277828 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.

1, 2, 5, 11, 23, 45, 90, 179, 357, 712, 1422, 2842, 5681, 11360, 22716, 45430, 90856, 181709, 363413, 726822, 1453640, 2907276, 5814546, 11629086, 23258166, 46516327, 93032647

Offset: 1

Author

Tim Miles, Nov 01 2016

Keywords

• nonn
• more

Comments

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.

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.

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

References

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

Links

• Eric Weisstein's World of Mathematics, Coin Tossing

Crossrefs

Cf. A135491, A135492, A135493.

Programs

Maple

a:= proc(n) option remember; local l, j; Digits:= 50;
      if n<3 then n else l:= 0$n;
        for j from 0 while l[n]<1/2 do l:= seq(
          (`if`(i=1, 1.0, l[i-1])+l[n-1])/2, i=1..n)
        od; j
      fi
    end:
seq(a(n), n=1..16);  # Alois P. Heinz, Nov 01 2016

Mathematica

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]];
Array[a, 16] (* Jean-François Alcover, May 31 2019, after Alois P. Heinz *)

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]))
a(n)=if(n<3, return(n)); my(v=vector(n), flips=1, needed=1/2); v[1]=1; while(v[n]Charles R Greathouse IV, Nov 02 2016

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

Python

def a(m):
    if m == 1:
        return 1
    g = [2**i for i in range(1, m)]
    sg, lim, n = sum(g), 2**(m-1), m
    while True:
        g.append(sg)
        sg <<= 1
        sg -= g.pop(0)
        if g[-1] <= lim:
            return n
        lim <<= 1
        n += 1
print([a(i) for i in range(1, 15)])
# Andrey Zabolotskiy, Nov 01 2016

Formula

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.

Extensions

a(11)-a(22) from Andrey Zabolotskiy, Nov 01 2016

a(23)-a(27) from Alois P. Heinz, Nov 02 2016