Misplaced Pages

Feller's coin-tossing constants

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Mathematical 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

lim n → ∞ p ( n , k ) α k n + 1 = β k {\displaystyle \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 ) {\displaystyle x^{k+1}=2^{k+1}(x-1)}

and

β k = 2 − α k k + 1 − k α k . {\displaystyle \beta _{k}={2-\alpha _{k} \over k+1-k\alpha _{k}}.}

Values of the constants

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

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

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) =  9 64 {\displaystyle {\tfrac {9}{64}}}  = 0.140625. The approximation p ( n , k ) ≈ β k / α k n + 1 {\displaystyle p(n,k)\approx \beta _{k}/\alpha _{k}^{n+1}} gives 1.44721356...×1.23606797... = 0.1406263...

References

  1. Feller, W. (1968) An Introduction to Probability Theory and Its Applications, Volume 1 (3rd Edition), Wiley. ISBN 0-471-25708-7 Section XIII.7
  2. Coin Tossing at WolframMathWorld

External links

Categories:
Feller's coin-tossing constants Add topic