title: Feller's coin-tossing constants
text: # 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
  
      $\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}}.$
  
  ## 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}}{2^{n}}}$ 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_{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) = ${\tfrac {9}{64}}$ = 0.140625. The approximation $p(n,k)\approx \beta _{k}/\alpha _{k}^{n+1}$ gives $1.44721356...×1.23606797...^{−11}$ = 0.1406263...
  
  