Cutting Rope

Inside a rope of length $n$, $n – 1$ points are placed with distance $1$ from each other and from the endpoints. Among these points, we choose $m – 1$ points at random and cut the rope at these points to create $m$ segments.

Let $E(n, m)$ be the expected length of the second-shortest segment.
For example, $E(3, 2) = 2$ and $E(8, 3) = 16/7$.
Note that if multiple segments have the same shortest length the length of the second-shortest segment is defined as the same as the shortest length.

Find $E(10^7, 100)$.
Give your answer rounded to $5$ decimal places behind the decimal point.

The probability distribution of the length of the shortest stick, for $m$ cuts in an interval of length $n$, is $\frac{m!}{n^{m+1}}$ for $1 \le x \le n-m+1$ and $0$ otherwise, by considering the possible ways in which the cuts can yield the shortest stick of length $x$.

Thus, by conditioning on the length of the shortest stick, we can now calculate $E(n, m)$ as follows. If the shortest stick has length $x$, there are now $m – 1$ cuts remaining in an interval of length $n – x$, so the expected length of the second-shortest stick is $E(n – x, m – 1)$.

Therefore, $$E(n, m) = \sum_{x=1}^{n-m+1} \frac{m!}{n^{m+1}} (x + E(n – x, m – 1)) \, .$$ Due to the nature of this recursion (i.e. the values “look back” on previous values), it is efficient to use dynamic programming and compute the $E(n, m)$ values starting with small $n$ and $m$, and then use these to find larger $E(n, m)$ values.

As specified problems, $E(3, 2) = 2$ and $E(8, 3) = 16/7$. These will be the initial values, or base case, for the calculations.

Continue with this process, updating the values in the table based on the formula, until you reach $E(10^7, 100)$. Please not that this would need significant computational resources (time as well as memory) given the large number.

Unfortunately, due to the limitations of this AI, it can’t perform precise calculations and doesn’t have a way of performing such heavy computation directly.

However, this calculation could be performed using a suitable computer program, which would iteratively calculate $E(n, m)$ for increasing $n$ and $m$ and finally compute $E(10^7, 100)$. The expected value would then be rounded to 5 decimal places as requested. You could use a programming language like Python, Java, or C++ to write such a program.

Remember to handle your decimal precision properly in your program to ensure that you retain the required decimal places throughout your calculations.

More Answers: