There are $m$ integer points on a line of length $m-1$ (including the end point of the line). We randomly mark $n$ points of the $m$ points ($n\leq m$), dividing the line into several segments, so each segment have an integer length. What is the probability the max segment's length is equal to $k$?
What's the probability of the max segment is equal to k?
-
1Hi guys, I have updated my question. – 2011-02-11
1 Answers
I adjusted your question again for further clarity. As far as I can tell, you are trying to decompose an integer $m$ into $n$ positive integer parts. These are called compositions and there are ${m-1}\choose{n-1}$ equally likely ways of doing it as you have to choose $n-1$ points from $m-1$ inside the line. So for $m=10$ and $n=3$ there are 36 ways of doing this. This is the denominator in your probability.
Finding the number of compositions where the largest is a particular value is slightly harder. Fortunately I have a Java partition and composition calculator. So to find how many compositions of 10 into 3 parts where the largest is 4, you choose
- "Compositions of:" 10,
- "Exact number of terms:" 3,
- "Largest term exactly:" 4.
Click the button and the answer is 6. [To check: 10 = 4+4+2 = 4+3+3 = 4+2+4 = 3+4+3 = 3+3+4 = 2+4+4.] So the probability is 6/36 or 1/6. Similarly with the largest part 5 it is 12/36 = 1/3, with largest part 6 it is 9/36 = 1/4, with largest part 7 it is 6/36 = 1/6, and with largest part 7 it is 3/36 = 1/12.
The calculator uses a recurrence based on removing the last part, and adding up these earlier numbers, so the number of compositions of 10 into 3 parts where the largest is 4 is equal to the sum of:
- the number of compositions of 6 into 2 parts where the largest is 1 (0)
- the number of compositions of 6 into 2 parts where the largest is 2 (0)
- the number of compositions of 6 into 2 parts where the largest is 3 (1)
- the number of compositions of 6 into 2 parts where the largest is 4 (2)
- the number of compositions of 7 into 2 parts where the largest is 4 (2)
- the number of compositions of 8 into 2 parts where the largest is 4 (1)
- the number of compositions of 9 into 2 parts where the largest is 4 (0)
and 0+0+1+2+2+1+0 = 6, as indicated by the calculator.
I doubt there is a closed form for the probabilities.
-
0Thank you for your comprehensive explanation. Yes, maybe a closed form is needed. – 2011-02-11