1
$\begingroup$

For $s \geq n$, sample with replacement $n$ integers $A_i$ from the range $\{1,\dots,s\}$ uniformly and independently. The probability that all the $A_i$ are distinct is:

$$\prod_{i=1}^{n-1}\left(1-\frac{i}{s}\right)$$

Now instead consider the sums of pairs of consecutive values. That is $$Z_1 = A_1+A_2, Z_2 = A_2+A+3, Z_3 = A_3+A_4, \dots$$

What is the probability that all of the $Z_i$ are distinct?

Numerically it seems that if $s = n^2$ the probability is approximately $0.75$. I don't know how true this mathematically is however.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.