Average length of the longest segment

Question

This post is related to a previous SE post If a 1 meter rope …. concerning average length of a smallest segment.

A rope of 1m is divided into three pieces by two random points. Find the average length of the largest segment. My answer is 11/18. Here is how I do it:

Here we have two independent random variables $X,Y$, both uniform on $[0,1]$. Let $A=\min (X,Y), B=\max (X,Y)$ and $C=\max (A, 1-B, B-A)$. First we want to find the probability density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then $$ F_C(a) = P(C\le a)=P(A\le a, 1-B\le a, B-A\le a).$$ By rewriting this probability as area in the unit square, I get $$F_C(a)=\left\{\begin{array}{ll} (3a-1)^2 & \frac{1}{3}\le a\le \frac{1}{2}\\ 1-3(1-a)^2 & \frac{1}{2}\le a\le 1\end{array}\right.$$ from which it follows that $$f_C(a)=\left\{\begin{array}{ll} 6(3a-1) & \frac{1}{3}\le a\le \frac{1}{2}\\ 6(1-a) & \frac{1}{2}\le a\le 1\end{array}\right.$$ Therefore the expected value of $C$ is $$\int_{1/3} ^{1/2}6a(3a-1) da+\int_{1/2} ^{1}6a(1-a) da= \frac{11}{18}.$$

My questions are:

(A) Is there a "clever" way to figure out this number 11/18?

(B) What is the answer if the rope is divided into $n>3$ segments?

Answer 1

The answer to (B) is actually given in both Yuval Filmus' and my answers to the question about the average length of the shortest segment. It's $$\frac{1}{n} H_n,$$ where $H_n = \sum_{k=1}^n \frac{1}{k},$ i.e., the $n$th harmonic number.

---

"Clever" is of course subjective, but here's an argument for (A) in the $n$-piece case. At least there's only one (single-variable) integration in it. :)

If $X_1, X_2, \ldots, X_{n-1}$ denote the positions on the rope where the cuts are made, let $V_i = X_i - X_{i-1}$, where $X_0 = 0$ and $X_n = 1$. So the $V_i$'s are the lengths of the pieces of rope.

The key idea is that the probability that any particular $k$ of the $V_i$'s simultaneously have lengths longer than $c_1, c_2, \ldots, c_k$, respectively (where $\sum_{i=1}^k c_i \leq 1$), is $$(1-c_1-c_2-\ldots-c_k)^{n-1}.$$ This is proved formally in David and Nagaraja's Order Statistics, p. 135. Intuitively, the idea is that in order to have pieces of size at least $c_1, c_2, \ldots, c_k$, all $n-1$ of the cuts have to occur in intervals of the rope of total length $1 - c_1 - c_2 - \ldots - c_k$. For example, $P(V_1 > c_1)$ is the probability that all $n-1$ cuts occur in the interval $(c_1, 1]$, which, since the cuts are randomly distributed in $[0,1]$, is $(1-c_1)^{n-1}$.

If $V_{(n)}$ denotes the largest piece of rope, then $$P(V_{(n)} > x) = P(V_1 > x \text{ or } V_2 > x \text{ or } \cdots \text{ or } V_n > x).$$ This calls for the principle of inclusion/exclusion. Thus we have, using the "key idea" above, $$P(V_{(n)} > x) = n(1-x)^{n-1} - \binom{n}{2} (1 - 2x)^{n-1} + \cdots + (-1)^{k-1} \binom{n}{k} (1 - kx)^{n-1} + \cdots,$$ where the sum continues until $kx > 1$.

Therefore, $$E[V_{(n)}] = \int_0^{\infty} P(V_{(n)} > x) dx = \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \int_0^{1/k} (1 - kx)^{n-1} dx = \sum_{k=1}^n \binom{n}{k} (-1)^{k-1} \frac{1}{nk} $$ $$= \frac{1}{n} \sum_{k=1}^n \frac{\binom{n}{k}}{k} (-1)^{k-1} = \frac{H_n}{n},$$ where the last step applies a known binomial sum identity.

Answer 2

A more intuitive answer. Let's arrange the segments from smallest to largest. Let the three segments be $x$, $x+y$ and $x+y+z$.

${\rm sum\ of\ segments}$ = 1 $\implies 3x + 2y + z = 1$;

subject to the constraints: $x\geqslant 0,y \geqslant 0,z \geqslant 0$ $\implies x \leqslant 1/3 , y \leqslant 1/2, z \leqslant 1$.

Within these limits, we can assume $x$,$y$ and $z$ can take on any values as long as we renormalize the total length to be equal to 1, sort of building the larger string from its constituent parts. These relative limits are equivalent to the following:

Let $x$ be chosen randomly among a pool from $[0,2n]$, $y$ be chosen randomly from a pool $[0,3n]$ and $z$ from a pool $[0,6n]$ where $(x,y,z,n)$ $\in$ $\mathbb R$.

Expected value of $x = n$, expected value of $y = 1.5n$ and expected value of $z = 3n$.
Expected length of longest segment = $x+y+z = 5.5n$
Expected total length = $3x+2y+z = 9n$

Therefore the expected length of longest segment is

$(x+y+z)/(3x+2y+z)= 5.5/9= 11/18 $.

The expected length of the shortest segment is

$x/(3x+2y+z) = 1/9$.

Answer 3

Neat as it is, I don't think Rahul's answer can be correct. If we have $3x+2y+z=1$ and $3x+2y+z=9n$, then $n=1/9$, which means $x \leq 2/9$, which can't be right, as one solution is all pieces being of length 1/3 (however unlikely this exact solution may be, $x$ can take values in $(2/9,1/3]$).

Stefan's answer is wrong because the probability of any given point on the stick being in the longest piece (when cut in 2) is not uniform. That can be seen by considering the point halfway along, which is always in the longest piece. You can find the probability density function for the likelihood of any given point being in the longer half, then integrate to get the answer below.

My preferred solution is to let the cuts be at $X, Y$, with $Y \gt X$:

Image of cut positions

Then each piece is equally likely to be the longest, and the expected length of the longest piece doesn't depend on which piece we choose. Then we can calculate $\mathop{\mathbb{E}}(X|X \text{ is the longest piece} )$.

We have the three inequalities: $$X \gt Y-X \implies Y < 2X$$ $$X \gt 1-Y \implies Y > 1-X$$ and, from our setup, $$Y \gt X$$ These can be represented by the following diagram:

Diagram of inequalities

Then the area satisfying our inequalities is the two triangles A and B. So we wish to find the expected value of $X$ within this area.

The expected value of $X$ in A is $\bar{X}_A = \frac{1}{2}-\frac{1}{3}(\frac{1}{2}-\frac{1}{3}) = \frac{8}{18}$.

The expected value of $X$ in B is $\bar{X}_B = \frac{1}{2}+\frac{1}{3}(\frac{1}{2}) = \frac{4}{6} = \frac{12}{18}$

The area of A is $A_A = \frac{1}{2} \times \frac{1}{2}\times (\frac{1}{2}-\frac{1}{3}) = \frac{1}{24}$.

The area of B is $A_B = \frac{1}{2} \times \frac{1}{2}\times \frac{1}{2} = \frac{1}{8} = \frac{3}{24} = 3 A_A$.

So $\mathop{\mathbb{E}}(X|X \text{ is the longest piece} ) = \frac{\tfrac{8}{18} + 3\left(\tfrac{12}{18}\right)}{4} = \frac{11}{18}$

(Apologies for the comments on other solutions and the links, but I haven't got a high enough reputation to comment or embed directly)

Answer 4

Why is this answer wrong?

Let the length of the longest segment created by the FIRST cut be $L_1$. Now consider the second cut. With probability $(1-L_1)$ it will be in the shorter segment made by the first cut, and the longest of the 3 segments will then have length $L_1$.

On the other hand, with probability $L_1$ the second cut will be in the longer first segment, and the longest of the 3 segments will then be the max of the longer segment made by the second cut, call it $L_2$, or the shorter segment made by the first cut, of length $(1-L_1)$.

This gives an expected length of the longest segment as: $(1-L_1)L_1+L_1 \max[L_2,(1-L_1)]$. If we now average this over cut positions, it is easy to reason that $L_1=3/4$, and $L_2=L_1^2=9/16$, giving the average length of the longest segment to be 39/64. This disagrees with 11/18, but only by 0.3%!

I assume there is a problem with performing the "averaging" over the $\max$ function, but I don't understand why. Any feedback would be great! Thanks!!

Answer 5

A similar, but a bit more complex problem, that highlights how important it is to understand the exact wording of a formulation:

cut a rope (or break a rod) at a random point. Set aside a piece. Cut (or break) the remaining piece at another random point.

Question is the same (expected length of the longest segment).

That's how I initially understood the problem.. Got stuck in algebra and closed-form anti-derivatives..

Same principle, heavier calculations. I got an answer 2ln2 - ln3 + 3/8 ~ 0.663, that matches what a MatLab script gives for 1000 tests.