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

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!


share|cite|improve this question

This is clearly wrong, since $Y\lt m$ whereas the Poisson distribution has support on all of $\mathbb N$. Perhaps it was meant as an approximation? It's hard to tell, since the link you provided has gone stale. Note also that one of the $m$s in your expression for $\lambda$ should probably be an $n$, both because the result must depend on $n$ and because otherwise the fraction could be reduced.

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.