Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
There is a simple geometric answer: It is the first corrdinate of mass center of these points: (1,0,..) (1/2,1/2,0,..) .. (1/n,1/n,1/n,...1/n) =(1+1/2+...1/n)/n –  Yudong Tang Mar 23 at 20:59

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
You are right. It was my fault for not checking. –  TCL Dec 13 '10 at 16:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.