Feller's coin-tossing constants

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 that if this probability is written as p(n,k) then

[math]\displaystyle{ \lim_{n\rightarrow \infty} p(n,k) \alpha_k^{n+1}=\beta_k }[/math]

where α_k is the smallest positive real root of

[math]\displaystyle{ x^{k+1}=2^{k+1}(x-1) }[/math]

and

[math]\displaystyle{ \beta_k={2-\alpha_k \over k+1-k\alpha_k}. }[/math]

Values of the constants

k	[math]\displaystyle{ \alpha_k }[/math]	[math]\displaystyle{ \beta_k }[/math]
1	2	2
2	1.23606797...	1.44721359...
3	1.08737802...	1.23683983...
4	1.03758012...	1.13268577...

For [math]\displaystyle{ k=2 }[/math] the constants are related to the golden ratio, [math]\displaystyle{ \varphi }[/math], and Fibonacci numbers; the constants are [math]\displaystyle{ \sqrt{5}-1=2\varphi-2=2/\varphi }[/math] and [math]\displaystyle{ 1+1/\sqrt{5} }[/math]. The exact probability p(n,2) can be calculated either by using Fibonacci numbers, p(n,2) = [math]\displaystyle{ \tfrac{F_{n+2}}{2^n} }[/math] or by solving a direct recurrence relation leading to the same result. For higher values of [math]\displaystyle{ k }[/math], 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) = [math]\displaystyle{ \tfrac{F^{(k)}_{n+2}}{2^n} }[/math].

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) = [math]\displaystyle{ \tfrac{9}{64} }[/math] = 0.140625. The approximation [math]\displaystyle{ p(n,k) \approx \beta_k / \alpha_k^{n+1} }[/math] gives 1.44721356...×1.23606797...⁻¹¹ = 0.1406263...

External links

• Steve Finch's constants at Mathsoft