# Gauss–Kuzmin distribution

Jump to: navigation, search
Parameters (none) $k \in \{1,2,\ldots\}$ $-\log_2\left[ 1-\frac{1}{(k+1)^2}\right]$ $1 - \log_2\left(\frac{k+2}{k+1}\right)$ $+\infty$ $2\,$ $1\,$ $+\infty$ (not defined) (not defined) 3.432527514776...[1][2][3]

In mathematics, the Gauss–Kuzmin distribution is a discrete probability distribution that arises as the limit probability distribution of the coefficients in the continued fraction expansion of a random variable uniformly distributed in (0, 1).[4] The distribution is named after Carl Friedrich Gauss, who derived it around 1800,[5] and Rodion Kuzmin, who gave a bound on the rate of convergence in 1929.[6][7] It is given by the probability mass function

$p(k) = - \log_2 \left( 1 - \frac{1}{(1+k)^2}\right)~.$

## Gauss–Kuzmin theorem

Let

$x = \frac{1}{k_1 + \frac{1}{k_2 + \cdots}}$

be the continued fraction expansion of a random number x uniformly distributed in (0, 1). Then

$\lim_{n \to \infty} \mathbb{P} \left\{ k_n = k \right\} = - \log_2\left(1 - \frac{1}{(k+1)^2}\right)~.$

Equivalently, let

$x_n = \frac{1}{k_{n+1} + \frac{1}{k_{n+2} + \cdots}}~;$

then

$\Delta_n(s) = \mathbb{P} \left\{ x_n \leq s \right\} - \log_2(1+s)$

tends to zero as n tends to infinity.

## Rate of convergence

In 1928, Kuzmin gave the bound

$|\Delta_n(s)| \leq C \exp(-\alpha \sqrt{n})~.$

In 1929, Paul Lévy[8] improved it to

$|\Delta_n(s)| \leq C \, 0.7^n~.$

Later, Eduard Wirsing showed[9] that, for λ=0.30366... (the Gauss-Kuzmin-Wirsing constant), the limit

$\Psi(s) = \lim_{n \to \infty} \frac{\Delta_n(s)}{(-\lambda)^n}$

exists for every s in [0, 1], and the function Ψ(s) is analytic and satisfies Ψ(0)=Ψ(1)=0. Further bounds were proved by K.I.Babenko.[10]

## References

1. ^ Blachman, N. (1984). "The continued fraction as an information source (Corresp.)". IEEE Transactions onInformation Theory 30 (4): 671–674. doi:10.1109/TIT.1984.1056924.
2. ^ Kornerup, P.; Matula, D. (July 1995). "LCF: A lexicographic binary representation of the rationals". Journal of Universal Computer Science 1: pp. 484–503. doi:10.1007/978-3-642-80350-5_41.
3. ^ Vepstas, L. (2008), Entropy of Continued Fractions (Gauss-Kuzmin Entropy)
4. ^
5. ^ Gauss, C.F. Werke Sammlung 10/1. pp. 552–556.
6. ^ Kuzmin, R.O. (1928). "On a problem of Gauss". DAN SSSR: 375–380.
7. ^ Kuzmin, R.O. (1932). "On a problem of Gauss". Atti del Congresso Internazionale dei Matematici, Bologna 6: pp. 83–89.
8. ^
9. ^ Wirsing, E. (1974). "On the theorem of Gauss–Kusmin–Lévy and a Frobenius-type theorem for function spaces". Acta Arithmetica 24: pp. 507–528.
10. ^ Babenko, K.I. (1978). "On a problem of Gauss". Soviet Math. Dokl. 19: pp. 136–140.