6
$\begingroup$

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

1 Answers 1

0

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.