Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an ordered list of $m$ uniform random numbers in the range $1$ to $n$ $$a_{1} \le a_{2} \le \ldots \le a_{m}, \forall a_{i}: a_{i}\in [1;n] \cap \mathbb{N}$$ compute the pairwise spacings of these numbers: $$d_{1} = a_{2}-a_{1} d_{2} = a_{3}-a_{2} \ldots d_{m-1} = a_{m}-a_{m-1}$$

Then, define $Y$ as the number of distinct $d_{i}$ that appear more than once: $$ Y = | \bigcup \limits_{i=1}^{m} \{d_{i}: \exists j \ne i : d_{i} = d_{j} \}| $$ (Note that for each distinct value that appears more than once, Y is increased by only one, no matter how often this value actually appears).

George Marsaglia [1] has stated that Y is Poisson-distributed with $\lambda = \frac{m^{3}}{4m}$, but I couldn't find a proof for that anywhere and I've just spent an entire day trying to figure it out myself. I seem to be unable to even get the probability of 2 $d_{i}$s having the same value. Does anyone have an idea how to start? Or is there even a "simple" explanation for the Poisson-distribution? I would be happy already if I could only prove that Y is Poisson-distributed at all, but I can't even do that by myself.

Thanks a million times for any help!

[1] http://www.stat.fsu.edu/pub/diehard/cdrom/pscript/keynote.ps

share|improve this question
add comment

Your Answer


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

Browse other questions tagged or ask your own question.