If you randomly pick $m$ numbers from $1$ to $n$, what is the probability that at least $m-1$ numbers that can be arranged in consecutive order?

Question

Hi I have this question and I do not quite understand why the solution is much lower than my intuition:

If you randomly pick $m$ numbers from $1$ to $n$, what is the probability that you have at least $m-1$ numbers that can be arranged in consecutive order? Edit: I.e. m= 8 numbers from 1 to 10 could be $1,2,3,4,5,6,7,8$ or $3,4,5,6,7,8,9,10$ A sequence that doesn't skip a number. I hope this explains it better. These numbers can be picked in any order, as long as they can be arranged in such a way as above. /end of edit.

I thought that the probability should be at least that of picking exactly $m$ numbers that can be arranged in order. I thought this would be $\frac{m \choose m-1}{n \choose m}$. For example this with $ n = 10$ and $m = 9 $ gives me $\frac{9}{10}$ however the correct solution is $\frac{4}{10}$.

I am likely making a thinking mistake but I can't find it. Thank you for your help!

PS: I was also thinking with at least I would have to take $1 - $ the probability that it can't happen. Well that's when there is a gap, so that's not picking $2$ numbers for the example aboth? But this gives me something way to low again.

Answer 1

For $i=1,2,\dots,n-m+2$ let $E_{i}$ denote the event that the numbers $i,i+1,\dots,i+m-2$ are among the $m$ picked numbers.

Then to be found is: $$P\left(\bigcup_{i=1}^{n-m+2}E_{i}\right)$$

Applying the principle of inclusion/exclusion and symmetry we find:

$$P\left(\bigcup_{i=1}^{n-m+2}E_{i}\right)=\left(n-m+2\right)P\left(E_{1}\right)-\left(n-m+1\right)P\left(E_{1}E_{2}\right)=$$$$\left(n-m+2\right)P\left(E_{1}\right)-\left(n-m+1\right)P\left(E_{1}E_{2}\right)$$

Here $P\left(E_{1}\right)=\frac{\binom{m-1}{m-1}\binom{n-m+1}{1}}{\binom{n}{m}}=\frac{n-m+1}{\binom{n}{m}}$ and $P\left(E_{1}E_{2}\right)=\frac{1}{\binom{n}{m}}$ so we arrive at:

$$\cdots=\binom{n}{m}^{-1}\left[\left(n-m+2\right)\left(n-m+1\right)-\left(n-m+1\right)\right]=$$$$\binom{n}{m}^{-1}\left(n-m+1\right)^{2}$$

Sanity check $n=10$ and $m=9$ is passed.