4
$\begingroup$

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

  • 1
    Hi guys, I have updated my question.2011-02-11

1 Answers 1

2

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.

  • 0
    Thank you for your comprehensive explanation. Yes, maybe a closed form is needed.2011-02-11