# 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?

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.

• Please clarify with an example what is meant with "can be arranged in order" ? Can't we arrange every finite set of numbers in order ? Commented Aug 13, 2020 at 9:50
• Oh I am sorry. Like in a consecutive sequence without missing one number. I. e. 8 from 1 to 10 could be 1,2,3,4,5,6,7,8 or 3,4,5,6,7,8,9,10 Commented Aug 13, 2020 at 9:51
• And the numbers must already appear in this order ? So, $5,4,1,3,2,6,7,8,10,9$ would qualify as a $3$-example because $678$ appears, correct so ? Commented Aug 13, 2020 at 9:55
• @Peter no, this is why I mean arranged. So in your example $1,3,2$ would also count as I could I arrange it in order I am sorry. This is literally the wording from my problem. Commented Aug 13, 2020 at 9:56
• In case $n=10$ and $m=9$ isn't it so that such order is only possible if one of 10,9,1, 2 is not picked? Commented Aug 13, 2020 at 9:56

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.

• thank you so much for this. I tried this with 2 values just now and it works totally fine. I have to study it a bit more to completely understand, such a nice derivation. Commented Aug 13, 2020 at 10:25
• You are very welcome. Commented Aug 13, 2020 at 10:25
• Hi, I hope I don't pester you too much. I have been able to understand your inclusion exclusion principle and the following derivation that leads to the final formula. I am however struggling to really get how you arrived at $P(E_1)$ and $P(E_1E_2)$. I wrote out all the possibilities and see it's correct. I just feel I am missing the "understanding". Commented Aug 13, 2020 at 11:28
• Let me try to explain with example $m=3$ and $n=5$. The event $E_1$ occurs iff we pick 1,2,3 or 1,2,4 or 1,2,5. So $n-m+1=5-3+1=3$ favourable outcomes on a total of $\binom53=10$ possible and equiprobable outomes. The events $E_1$ and $E_2$ occur both iff we pick 1,2,3. So 1 favourable outcome on a total of again $\binom53=10$ possible and equiprobable outcomes. Commented Aug 13, 2020 at 13:38
• thank you very much. This example made things much clearer again. I feel quite silly since this is the second time I am solving this and I couldn't even remember how to arrive at the solution after your clear derivation above. It finally clicked! Thank you again for your patience. Commented Aug 13, 2020 at 13:45