Feller's coin-tossing constants explained

Feller's coin-tossing constants are a set of numerical constants which describe asymptotic probabilities that in n independent tosses of a fair coin, no run of k consecutive heads (or, equally, tails) appears.

William Feller showed^[1] that if this probability is written as p(n,k) then

\lim _{n →} p(n,k) \alpha ^{n +1} _{k} = \beta _{k}

where α_k is the smallest positive real root of

x ^{k+1} =2 ^{k+1} (x -1 )

and

\beta _{k={2-\alpha} _{k} \over k +1- k\alpha _{k}.}

Values of the constants

k	\alpha _{k}	\beta _{k}
1	2	2
2	1.23606797...	1.44721359...
3	1.08737802...	1.23683983...
4	1.03758012...	1.13268577...

For

k =2 the constants are related to the golden ratio, \varphi , and Fibonacci numbers; the constants are \sqrt{ 5 } -1=2 \varphi -2=2 /\varphi and 1+1 /\sqrt{ 5 } . The exact probability p(n,2) can be calculated either by using Fibonacci numbers, p(n,2) = \tfrac{F _{n+2} } or by solving a direct recurrence relation leading to the same result. For higher values of k , the constants are related to generalizations of Fibonacci numbers such as the tribonacci and tetranacci numbers. The corresponding exact probabilities can be calculated as p(n,k) = \tfrac{F ^{(k)} _{n +2} }. ^[2]

Example

If we toss a fair coin ten times then the exact probability that no pair of heads come up in succession (i.e. n = 10 and k = 2) is p(10,2) = 

\tfrac{ 9 }{ 64 }  = 0.140625. The approximation p(n,k) ≈ \beta _{k} / \alpha ^{n +1} _{k} gives 1.44721356...×1.23606797...^-11 = 0.1406263...

External links

• Steve Finch's constants at Mathsoft

Notes and References

1. Feller, W. (1968) An Introduction to Probability Theory and Its Applications, Volume 1 (3rd Edition), Wiley. Section XIII.7
2. http://mathworld.wolfram.com/CoinTossing.html Coin Tossing at WolframMathWorld