This article is cited in 4 papers

Short Communications

Limit distribution of a number of coinciding intervals

N. V. Klykova

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Let $X_1,\dots,X_T$ be independent random variables uniformly distributed on the set $\{1,\dots,N\}$, let $X_{(1)},\dots,X_{(2)}\le\dots\le X_{(T)}$ be their order statistics and $\zeta(T,N)$ be a number of pairs $(i,j)$, $1\le i<j\le T-1$, such that $X_{(i+1)}-X_{(i)}=X_{(j+1)}-X_{(j)}$. We give a full proof of the convergence theorem of the distribution $\zeta(T,N)$ to the Poisson distribution with parameter $\lambda$ for $T,N\to\infty$, $T^3/4N\to\lambda$. Heuristic proof of this statement was given in [D. Aldous, Probability Approximation via the Poisson Clumping Heuristic, Springer-Verlag, Berlin, Heidelberg, 1989].

Keywords: birthday problem, set of order statistics, spacings.

Received: 12.03.2001

DOI: 10.4213/tvp3069

 English version: Theory of Probability and its Applications, 2003, 47:1, 151–156

Bibliographic databases:

• 
• 
•