Intereting Posts

Order of $\mathbb{Z}/(1+i)$
Irreducibility of $~\frac{x^{6k+2}-x+1}{x^2-x+1}~$ over $\mathbb Q$
Number of zero digits in factorials
Do we know a number $n\gt 5$ with no twin prime $n\lt q\lt 2n$?
Integration of sqrt Sin x dx
Every polynomial with real coefficients is the sum of cubes of three polynomials
Why can you turn clothing right-side-out?
Diffeomorphism invariant scalars of a Riemannian manifold
how to extend a basis
Two paths that show that $\frac{x-y}{x^2 + y^2}$ has no limit when $(x,y) \rightarrow (0,0)$
“Intrinsic” treatment of projective spaces
Existence of non-trivial ultrafilter closed under countable intersection
Can a ring of positive characteristic have infinite number of elements?
Is there an absolute notion of the infinite?
Why does finding the $x$ that maximizes $\ln(f(x))$ is the same as finding the $x$ that maximizes $f(x)$?

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}.$$

- Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
- Throwing $k$ balls into $n$ bins.
- Distribution of Difference of Chi-squared Variables
- Is conditional expectation with respect to two sigma algebra exchangeable?
- On average, how many times must I roll a dice until I get a $6$?
- Is the function $F(x,y)=1−e^{−xy}$ $0 ≤ x$, $y < ∞$, the joint cumulative distribution function of some pair of random variables?

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?

- How to choose between two options with a biased coin
- Derivation of chi-squared pdf with one degree of freedom from normal distribution pdf
- Coupon collector's problem using inclusion-exclusion
- Probability the three points on a circle will be on the same semi-circle
- operations on probability distributions
- Probability from a collection of independent predictions
- What is the expected time to cover $m \leq N$ elements in a set by sampling uniformly and with replacement?
- Probability that distance of two random points within a sphere is less than a constant
- Birthday Problem for 3 people
- Rolling $2$ dice: NOT using $36$ as the base?

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.

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!!

A more intuitive answer. Let the three segments be $x$, $x+y$ and $x+y+z$.

$sum\ of\ segments$ = 1;

$\implies 3x + 2y + z = 1$;

subject to constraints: $x>=0,y>=0,z>=0$;

$\implies x <= 1/3 , y <= 1/2, z <= 1$

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)

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 length of longest segment $= (x+y+z)/(3x+2y+z)= 5.5/9\ or\ 11/18 $

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

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.

- Nearly, but not almost, continuous
- Subgroups of symmetric group
- A nice pattern for the regularized beta function $I(\alpha^2,\frac{1}{4},\frac{1}{2})=\frac{1}{2^n}\ $?
- Why is not the answer to all probability questions 1/2.
- Is there a reason why the number of non-isomorphic graphs with $v=4$ is odd?
- Example for an ideal which is not flat (and explicit witness for this fact)
- Committee combinatorics
- Localization of the Integer Ring
- Optimal multiplying method
- $G/H$ is a finite group so $G\cong\mathbb Z$
- Homomorphism and normal subgroups
- Is $\sum_{n=1}^{\infty}\frac{(\log\log2)^n}{n!}>\frac{3}{5}$
- How to change the order of summation?
- Equivalences of $\diamondsuit$-principle.
- Limit to infinity and infinite logarithms?