Feller's coin-tossing constants

From Wikipedia, the free encyclopedia

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\rightarrow \infty} p(n,k) \alpha_k^{n+1}=\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}.$

[edit] Values of the constants

k	$α k$	$β 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 and Fibonacci numbers; the constants are $\sqrt{5}-1=2\varphi-2=2/\varphi$ and $1-1/\sqrt{5}$ . For higher values of $k$ they are related to generalizations of Fibonacci numbers such as the tribonacci and tetranacci constants.

[edit] 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 gives 1.44721356...×1.23606797...⁻¹¹ = 0.1406263...