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
    You may have to clarify a lot of this. Is the original line finite and if so does it have a particular length? Are there $m$ points or $n$ points? Or both? How do you divide points into segments? Are the points at integer values or real numbers? If real numbers, then how can a segment have a positive probability of being precisely any particular length?2011-02-11
  • 1
    I think this needs to be clarified a bit. As I understand it, you have $m$ points on a line, and you randomly (i.e. with a uniform distribution) choose $n \le m$ of these points. Then you consider "segments" that this divides the $m$ points into. Are these segments sets of points, or segments of the lines? Is their "length" the number of points they contain, or the length of a line segment? If the latter, we would need to know how the $m$ points are distributed on the line. And how are the segments defined? Do the points before the first and/or after the last chosen point also form a segment?2011-02-11
  • 0
    Sorry for my ambiguous question. Actually, the line is finite of length m-1, the m points are on the integer point including the end point of the line.2011-02-11
  • 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