1
$\begingroup$

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}$

$\endgroup$
5
  • $\begingroup$ 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." $\endgroup$
    – angryavian
    Commented Apr 5 at 15:51
  • $\begingroup$ @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? $\endgroup$
    – shrizzy
    Commented Apr 5 at 16:00
  • 2
    $\begingroup$ 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." $\endgroup$
    – angryavian
    Commented Apr 5 at 16:06
  • $\begingroup$ @angryavian ahh I see, thank you for that I think I misinterpreted the problem. I agree with your characterization of the compliment $\endgroup$
    – shrizzy
    Commented Apr 5 at 16:11
  • $\begingroup$ @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 $\endgroup$
    – true blue anil
    Commented Apr 7 at 13:09

1 Answer 1

Reset to default
2
$\begingroup$

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}$$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Apr 5 at 17:20
  • $\begingroup$ @lulu: You are right, thanks, amended. $\endgroup$
    – true blue anil
    Commented Apr 5 at 17:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .