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

 
discard

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

Browse other questions tagged or ask your own question.