# Probability that difference between any two numbers is at least $5$

Suppose you select $$5$$ numbers uniformly and randomly from $$[1, 2, 3, ..., 150]$$ with replacement. What is the probability the difference between any two of them is at least $$5$$?

My first thought was to find the compliment of the probability by picking an arbitrary number for the first pick and measure the probability that all $$4$$ numbers picked after that are within a range of $$4$$. The issue with that is that the numbers could be within $$4$$ of the original but still have a difference exceeding $$5$$ we pick numbers that are $$+4$$ and $$-4$$. Is there a clever way to go about this other than brute force? Perhaps some way to compute $$P(max - min) \geq 5$$

EDIT: I initially misinterpreted the problem.

For numbers $$5-146$$, we see that there are $$9$$ numbers that are within $$4$$ of it giving that a probability of $$\frac9{150}$$ of selecting a number within $$4$$. So if the first number is between $$5$$ and $$146$$ the probability none of the other numbers are within $$4$$ of it is $$\frac{141}{150}^4$$. We can find the numbers outside of this range in a similar process and get:

$$\frac2{150}\cdot\frac{145}{150}^4 + \frac2{150}\cdot\frac{144}{150}^4 + \frac2{150}\cdot\frac{143}{150}^4 + \frac2{150}\cdot\frac{142}{150}^4 + \frac{142}{150}\cdot\frac{141}{150}^4 = \frac{59519652498}{150^5} \approx 0.7838$$

To clarify, this is the probability that no number is within $$4$$ of the first selected number.

By linearity of expectation, let's use this value to signify the probability that there is no number within $$4$$ of any selected number. giving us a value of $$\approx 0.7838^5 \approx \boxed{0.29582}$$

• Your characterization of the complement is not correct. It should be "at least two of the numbers are within 4 of each other." Note that $\{1, 2, 3, 4, 150\}$ is in the complement, but doesn't satisfy "all 4 numbers picked after the first one are within 4 of the first one." Commented Apr 5 at 15:51
• @angryavian I agree my compliment characterization was wrong but is yours not also incorrect? we see that $150-1 \geq 5$ so that would satisfy the difference being at least $5$, right? If any two numbers are at least 5 apart wouldn't compliment of that be all numbers are within $4$ of each other? Commented Apr 5 at 16:00
• I am interpreting "difference between any two of them" as "difference between every pair," whereas you seem to be interpreting it as "difference between some pair." Commented Apr 5 at 16:06
• @angryavian ahh I see, thank you for that I think I misinterpreted the problem. I agree with your characterization of the compliment Commented Apr 5 at 16:11
• @shrizzy: Your answer is incorrect. The formula in my answer gives $$Pr=\dfrac{\dbinom{134}{5}{5!}}{{150}^5},≈0.52758$$ I have checked for two numbers chosen in a length of 12, and the manual working tallies *exactly^ with the formula. The two blocks (one of $5$ and one of $1$) plus the $6$ numbers yield $8$ entities, and there will be $\dbinom82 2!\;$ "successes" against $12^2$ possibilities Commented Apr 7 at 13:09

Make $$4$$ blocks of chosen-unchosen with chosen shown as bullets, plus a short block of one chosen, viz
four boxes like $$\boxed{\bullet\circ\circ\circ\circ}$$ and one $$\boxed{\bullet}$$
$$150-21 = 129$$ numbers plus $$5$$ blocks $$=134$$ entities remain among which the $$5$$ blocks may be placed with the short box last and the patterns renumbered, in $$\binom{134}5$$ ways. The position of the bullets in each such sequence represents the numbers chosen. But as selections are with replacement, each could be selected in $$5!$$ sequences, against unrestricted selections of $$150^5$$, thus
$$Pr = \frac{\binom{134}5 5!}{150^5}$$
• This is very small... of course, the patterns you construct for the numerator can each be selected in $5!$ ways, so that factor is missing.