Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a sequence of IID random variables $X_1, X_2, \dots, X_n$. In this particular case, each of the variables is Lévy distributed with PDF

$f(x) = (\lambda / 2 \pi x^3)^{-1/2} \exp(-\lambda/2x)$

for $x > 0$, and $f(x) = 0$ otherwise.

I'm trying to find the probability, given constants $\tau > 0$ and $b < n$, that there exists an interval of length $\tau$ which contains at least $b$ of the $n$ random variables.

My first approach was to use order statistics; for example, if $X_{(1)}, X_{(2)}, \dots, X_{(n)}$ are the order statistics, the probability that the $b$ smallest fall in an interval of length $\tau$ could be found using the joint distribution of $X_{(1)}$ and $X_{(b)}$. From the Wikipedia article,


This could then be integrated over the simplex $0 \leq x \leq y \leq x + \tau$, and the result could be repeated for each group of $b$ random variables and summed. However, I feel that this approach leads to double counting (for example, both $X_{(1)} \dots X_{(b)}$ and $X_{(n-b+1)} \dots X_{(n)}$ could fall in disjoint intervals of length $\tau$) and also seems to be difficult to obtain in closed form.

The other approach I considered was to use the joint density of all order statistics:

$f_{X_{(1)},\ldots,X_{(n)}}(x_1,\ldots,x_n)\,dx_1\cdots dx_n=n!f_X(x_1)\cdots f_X(x_n)\,dx_1\cdots dx_n$

However, I can't determine how to express the region of integration in any meaningful way. Any thoughts or pointers would be appreciated!

share|cite|improve this question
up vote 2 down vote accepted

The nonexistence of such interval is equivalent to $X_{(i+b-1)} > X_{(i)}+r$ for $i=1\ldots n-b+1$. So for the probability of the complement of your event, integrate $n! f(x_1) \ldots f(x_n)$ over the region defined by $$ x_{b-1} > x_{b-2}> \ldots >x_2 > x_1>0 $$ and $$ x_b > \max(x_{b-1}, x_1 + r), \ldots, x_n > \max(x_{n-1}, x_{n-b+1} + r). $$

share|cite|improve this answer
Thanks, that makes a lot of sense. This helps when using numerical approximations, but the bounds don't seem to lead to a closed form solution - I suppose this is unlikely anyways. – sciyoshi May 25 '11 at 18:19

As said before, there is no simple closed form solution. But one can prove some upper and lower bounds, which yield a precise value in a semi-explicit range of values of $b$, $n$ and $\tau$.

We start with some notations. For $x\le y$, call $g(x,y)=P(x\le X_1\le y)$ the integral of the density function $f$ of $X_1$ from $x$ to $y$. For any subset $I$ of $\{1,2,\ldots,n\}$ of size $b$, call $A_I=[R_I\le\tau]$ where $R_I$ is the range of the sample $(X_k)$ over $I$, that is, $$ A_I=[R_I\le\tau],\qquad R_I=\max\{X_k;k\in I\}-\min\{X_k;k\in I\}. $$ Using the fact that the event $[x\le\min\{X_k;k\in I\},\max\{X_k;k\in I\}\le y]$ has probability $g(x,y)^b$, one sees that $P(A_I)=\alpha_b$ for every $I$ of size $b$, with

$$ \alpha_b=\int bf(x)g(x,x+\tau)^{b-1}\mathrm{d}x. $$

The event $A$ that there exists an interval of length (at most) $\tau$ which contains (at least) $b$ values from the sample of size $n$ is $$ A=\bigcup_IA_I,\quad A_I=[R_I\le\tau], $$ where the union is over the subsets $I$ of $\{1,2,\ldots,n\}$ of size $b$. By the inclusion-exclusion principle, $$ S-S'\le P(A)\le S,\quad S=\sum_{I}P(A_I),\ S'=\sum_{I\ne J}P(A_I\cap A_J). $$ For every $I$ of size $b$, $P(A_I)=\alpha_b$. For every $I\ne J$ of size $b$, $A_I$ and $A_J$ are independent if $I\cap J=\emptyset$ and positively correlated otherwise, hence $P(A_I\cap A_J)\ge \alpha_b^2$. Finally,

$$ {n\choose b}\alpha_b-\frac12\left({n\choose b}^2-{n\choose b}\right)\alpha_b^2\le P(A)\le{n\choose b}\alpha_b. $$

This reads approximately as $p-\frac12p^2\le P(A)\le p$ with $p=\displaystyle{n\choose b}\alpha_b$ hence this estimation of $P(A)$ is as precise as the upper bound $p$ is small.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.