Picking 5 random numbers on average how big is the largest gap between them?

63 Views Asked by At

We pick 5 random numbers from 1 to 100 with repetition. We order them. On average what is the largest difference between two consecutive numbers? What is the smallest difference? Example: 4, 22, 47,55,96

The largest gap is 96-55=41 The smallest gap is 55-47=8

1

There are 1 best solutions below

0
On BEST ANSWER

Mean of smallest difference

Here's a fairly simple formula for the mean of the smallest difference, under the assumption that the smallest difference for the multiset $\ \left\{i_1,i_2,i_3,i_4, i_5\right\}\ $ with $\ i_1\le i_2\le i_3\le i_4\le i_5\ $ is defined to be $\ \min_\limits{2\le k\le5}\big(i_k-i_{k-1}\big)\ $.

The mean of this smallest difference is \begin{align} \frac{5!\sum_\limits{n=1}^{24}{104-4n\choose5}}{100^5}&=\frac{1270221}{390625}\\ &\approx3.25\ . \end{align} For $\ 0\le n\le24\ $ the number of multisets, $\ \left\{i_1,i_2,i_3,i_4, i_5\right\}\ $, of cardinality $5$ of integers in the range $\ [1,100]\ $ with $\ \min_\limits{j\ne k}\left|\,i_k-i_j\right|\ge n\ $ is $\ {104-4n\choose5}\ $. For $\ n\ge1\ $ (when the multiplicity of every element of the multiset is one) each of these sets has the same probability of $\ \frac{5!}{100^5}\ $ of occurring. Thus, if $\ G\ $ is the smallest gap then $$ P(G\ge n)=\cases{1&if $\ n=0$\\ \frac{5!{104-4n\choose5}}{100^5}&if $\ 1\le n\le24$\\ 0&if $\ 25\le n\ $.} $$ Thus, \begin{align} E(G)&=\sum_{n=1}^\infty P(G\ge n)\\ &=\frac{5!\sum_\limits{n=1}^{24}{104-4n\choose5}} {100^5}\ , \end{align} as stated above.

Appendix

For completion, I here give a derivation of the formula for the number of multisets with minimum difference at least $\ n\ $. I expect there's likely to be a much slicker combinatorial proof of this, but the following is the best I've so far been able to come up with.

Let $$ I\big(i_1,i_2,i_3,i_4,i_5,n\big)=\cases{1&if $\min_\limits{j\ne k}\left|\,i_k-i_j\right|\ge n$\\ 0&otherwise.} $$ Then the number of multisets with minimum difference at least $\ n\ $ is given by \begin{align} &\sum_{i_1=1}^{100}\sum_{i_2=i_1}^{100}\sum_{i_3=i_2}^{100}\sum_{i_4=i_3}^{100}\sum_{i_5=i_4}^{100}I\big(i_1,i_2,i_3,i_4,i_5,n\big)\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{i_3=i_2+n}^{100-2n}\sum_{i_4=i_3+n}^{100-n}\sum_{i_5=i_4+n}^{100}1\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{i_3=i_2+n}^{100-2n}\sum_{i_4=i_3+n}^{100-n}(101-i_4-n)\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{i_3=i_2+n}^{100-2n}\sum_{j=1}^{101-i_3-2n}j\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{i_3=i_2+n}^{100-2n}\left(1+\sum_{j=2}^{101-i_3-2n}\left\{{j+1\choose2}-{j\choose2}\right\}\right)\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{i_3=i_2+n}^{100-2n}{102-i_3-2n\choose2}\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\sum_{j=2}^{102-i_2-3n}{j\choose2}\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}\left(1+\sum_{j=3}^{102-i_2-3n}\left\{{j+1\choose3}-{j\choose3}\right\}\right)\\ &=\sum_{i_1=1}^{100-4n}\sum_{i_2=i_1+n}^{100-3n}{103-i_2-3n\choose3}\\ &=\sum_{i_1=1}^{100-4n}\sum_{j=3}^{103-i_1-4n}{j\choose3}\\ &=\sum_{i_1=1}^{100-4n}\left(1+\sum_{j=4}^{103-i_1-4n}\left\{{j+1\choose4}-{j\choose4}\right\}\right)\\ &=\sum_{i_1=1}^{100-4n}{104-i_1-4n\choose4}\\ &=\sum_{j=4}^{103-4n}{j\choose4}\\ &=1+\sum_{j=5}^{103-4n}\left({j+1\choose5}-{j\choose5}\right)\\ &={104-4n\choose5} \end{align}