Spacing Limit Theorem

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Theorem

Let $X_{\paren i}$ be the $i$th ordered statistic of $N$ samples from a continuous random distribution with density function $\map {f_X} x$.

Then the spacing between the ordered statistics given $X_{\paren i}$ converges in distribution to exponential for sufficiently large sampling according to:

$N \paren {X_{\paren {i + 1} } - X_{\paren i} } \xrightarrow D \map \exp {\dfrac 1 {\map f { X_{\paren i} } } }$

as $N \to \infty$ for $i = 1, 2, 3, \dotsc, N - 1$.

Proof

Given $i$ and $N$, the ordered statistic $X_{\paren i}$ has the probability density function:

$\map {f_{X_{\paren i} } } {x \mid i, N} = \dfrac {N!} {\paren {i - 1}! \paren {N - i}!} \map {F_X} x^{i - 1} \paren {1 - \map {F_X} x}^{N - i} \map {f_X} x$

where $\map {F_X} x$ is the cumulative distribution function of $X$.

This article needs to be linked to other articles. In particular: The page Definition:Conditional Probability needs to be expanded so as to define and explain the notation $\tuple {x \mid i, N}$ in the context of a PDF You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Let $Y_i = N \paren {X_{\paren {i + 1} } - X_{\paren i} }$ be an independent spacing variable valid for $i = 1, 2, 3, \dotsc, N - 1$ which is always positive.

The joint density function of both $X_{\paren i}$ and $Y_{i}$ is then:

$\map {f_{X_{\paren i}, Y_i} } {x, y \mid i, N} = \dfrac {\paren {N - 1}!} {\paren {i - 1}! \paren {N - i - 1}!} \map {F_X} x^{i - 1} \paren {1 - \map {F_X} {x + \dfrac y N} }^{N - i - 1} \map {f_X} x \map {f_X} {x + \dfrac y N}$

The conditional density function of $Y_i$ given $X_{\paren i}$ is:

$f_{Y_i} = \dfrac {f_{X_{\paren i}, Y_i} } {f_{X_{\paren i} } }$

which turns into:

$\map {f_{Y_i} } {y \mid x = X_{\paren i}, i, N} = \dfrac {N - i} N \dfrac {\paren {1 - \map {F_X} {x + \dfrac y N} }^{N - i - 1} } {\paren {1 - \map {F_X} x}^{N - i} } \map {f_X} {x + \dfrac y N}$

The conditional cumulative function of $Y_i$ given $X_{\paren i}$ is:

$\map {F_{Y_i} } {y \mid x = X_{\paren i}, i, N} = 1 - \paren {\dfrac {1 - \map {F_X} {x + \dfrac y N} } {1 - \map {F_X} x} }^{N - i}$

The following Taylor expansion in $y$ is an approximation of $\map {F_X} {x + \dfrac y N}$:

$\map {F_X} {x + \dfrac y N} = \map {F_X} x + \map {f_X} x \dfrac y N + \map \OO {N^{-2} }$

Inserting this produces:

$\map {F_{Y_i} } {y \mid x = X_{\paren i}, i, N} = 1 - \paren {1 - \dfrac {\map {f_X} x y} {N \paren {1 - \map {F_X} x} } + \map \OO {N^{-2} } }^{N - i}$

The limit as $N$ gets large is the exponential function:

$\map {F_{Y_i} } {y \mid x = X_{\paren i}, i, N} = 1 -e^{- \map {f_X} x y \dfrac {1 - \dfrac i N} {1 - \map {F_X} x} } + \map \OO {N^{-1} }$

The distribution of $F_X$ is uniform by definition of a random pick:

$\map {F_X} x \sim \map U {0, 1}$

Therefore $i$ is uniformly distributed as well:

$\map {F_X} {X_{\paren i} } \approx \dfrac i N$

The limit of $F_{Y_i}$ is then:

$\ds \lim_{N \mathop \to \infty} \map {F_{Y_i} } {y \mid x = X_{\paren i}, i, N} = 1 - e^{- \map {f_X} x y}$

$\blacksquare$