# If a 1 meter rope is cut at two uniformly randomly chosen points, what is the average length of the smallest piece?

If a $1$ meter rope is cut at two uniformly randomly chosen points (to give three pieces), what is the average length of the smallest piece?

I got this question as a mathematical puzzle from a friend. It looks similar to MathOverflow question If you break a stick at two points chosen uniformly, the probability the three resulting sticks form a triangle is 1/4.

However, in this case, I have to find the expected length of the smallest segment. The two points where the rope is cut are selected uniformly at random.

I tried simulating it and I got an average value of $0.1114$. I suspect the answer is $1/9$ but I don't have any rigorous math to back it up.

How do I solve this problem?

• Hint: Note that the probability that the smallest segment is bigger than $x$ is equal to the probability that all segments are bigger than $x$. Can you use this to solve the problem? Dec 11, 2010 at 21:10
• @raskolnikov. I'm not sure if that is enough to solve the problem. Dec 11, 2010 at 21:32
• I didn't imply it was. Dec 11, 2010 at 21:35

My approach is maybe more naive than the others posted.

Break the unit interval at $x$ and $y$ where $x < y$. Our lengths are then $x$, $y - x$, and $1 - y$. It's not hard to show that they all have probability $1/3$ of being the shortest. In any case, our joint PDF is given by $f(x,y) = 6$ (since $x$ and $y$ remain uniform random variables on $1/6$th of the square $[0,1] \times [0,1]$). Each triangle in the diagram below corresponds to the domain of the PDF for one of the three cases. I'll take care of the case when $x$ is shortest, that is, $x \leq y - x$ and $x \leq 1 - y$. This is the leftmost triangle. Since we're assuming $x$ is least, we are looking for $$E[x] = \int_0^{1/3} \int_{2x}^{1 - x} 6x \;dy \;dx = 1/9$$

The cases when $y - x$ and $1 - y$ are shortest are similar.

• Using this approach we can calculate more complicated order statistics, such as the expected length of the smallest pair of adjacent segments on the circle. See cs.toronto.edu/~yuvalf/circle.pdf . Dec 12, 2010 at 0:09
• May I know why is the joint PDF is $6$? Feb 14, 2020 at 7:31
• @Idonknow Within the constraints the distribution is uniform so the density is constant. But you want the total probability to be $1$ across a sixth of the square and so the density needs to be $6$ for that to happen Feb 14, 2020 at 9:49
• Why must the joint density be constant? Also, if it is constant, why must it be 1 across the sixth square but not other square? Feb 14, 2020 at 10:42
• 6 is 3! meaning there are 3! possibilities of ordering the length of the 3 segments, and only 1, 1/6 has the required segments ordering.
– SeF
Apr 15, 2020 at 15:53

Update: The current version of this answer is more intuitive (IMHO) than the previous one. See also this similar answer to a similar question.

The generalization of this problem to $$n$$ pieces is discussed extensively in David and Nagaraja's Order Statistics (pp. 133-135, and p. 153).

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_{(1)}$$ denotes the shortest piece of rope, then for $$x \leq \frac{1}{n}$$, (following Raskolnikov's comment) $$P(V_{(1)} > x) = P(V_1 > x, V_2 > x, \ldots, V_n > x) = (1 - nx)^{n-1}.$$

Therefore, $$E[V_{(1)}] = \int_0^{\infty} P(V_{(1)} > x) dx = \int_0^{1/n} (1-nx)^{n-1} dx = \frac{1}{n^2}.$$

David and Nagaraja also give the formula Yuval Filmus mentions (as Problem 6.4.2):

$$E[V_{(r)}] = \frac{1}{n} \sum_{j=1}^r \frac{1}{n-j+1}.$$

If we divide the rope into $n$ segments then the $k$th largest segment will have expected length $$\frac{1}{n} \left( \frac{1}{n} + \cdots + \frac{1}{k} \right),$$ but I don't remember why. In particular, the smallest segment has expected length $1/n^2$.

Note that equivalently we could throw $n$ random points on a circle of unit circumference and consider lengths of segments on the circle.

### Derivation of the general formula from the formula for the smallest segment

Len $n$ points be thrown uniformly on the circle. Suppose the smallest segment has length $x$. We can remove an initial prefix of length $x$ from each segment to get a uniformly generated ensemble of $n-1$ segments on a circle of length $1-nx$. In this new arrangement, the smallest segment has expected size $(1-nx)/(n-1)^2$. Therefore the expected size of the second smallest segment is $$Ex + \frac{1-nEx}{(n-1)^2} = \frac{1}{n^2} + \frac{1-1/n}{(n-1)^2} = \frac{1}{n^2} + \frac{1}{n(n-1)}.$$ We can get the general formula in the same way.

### Derivation of the formula for the smallest segment

Use the same method and come up with one more equation that will enable you to find this unknown.

• Thanks for a great comment. That's some nifty reasoning there. Dec 11, 2010 at 23:29
• Note that I don't actually remember that "one more equation", but there's a way to calculate the expected size of the smallest segment only using expectations and without integrals. Dec 12, 2010 at 0:06
• Yeah, I'm still working on it to be honest, but I like the idea in your comment. Dec 12, 2010 at 1:43

Here you have two independent random variables $X,Y$, both uniform on $[0,1]$. Let $A=\min (X,Y), B=\max (X,Y)$ and $C=\min (A, 1-B, B-A)$. First you want to find the probability density function $f_C(a)$ of $C$. Let $F_C(a)$ be the cumulative distribution function. Then $$1- F_C(a) = P(C\ge a)=P(A\ge a, 1-B\ge a, B-A\ge a)$$ $$=P(a\le X\le 1-a, a\le Y\le 1-a, |X-Y|\ge a)$$ This is equal to the total area of the two sets $$\lbrace (x,y): 0\le x,y\le 1, y\le x-a, x\le 1-a, y\ge a\rbrace$$ and

$$\lbrace (x,y): 0\le x,y\le 1, y\ge x+a, x\ge a, y\le 1-a\rbrace$$ which is $(1-3a)^2$. Note that for these sets to be nonempty, one must have $0\le a\le 1/3$.

Hence $F_C(a)=1-(1-3a)^2$, from which it follows $f_C(a)=F_C'(a)=6(1-3a)$. Therefore the expected value of $C$ is $$\int_0^{1/3} 6a(1-3a) da= \frac{1}{9}.$$

• In the above derivation, we use the facts that $1-B=\min(1-X,1-Y)$ and that $|X-Y|\ge a$ iff $X-Y\ge a$ or $Y-X\ge a$.
– TCL
Dec 11, 2010 at 23:34

Maybe this geometric argument clarifies the intuition. For convenience, assume we are looking for average value of the maximum.

The question can be translated to the following: $(x_1,\ldots,x_n)$ are uniformly distributed on the polytope $x_1+x_2+...+x_n = 1$, $x_i\geq 0$, find the expectation of the largest $x_i$. The polytope is naturally divided into $n!$ pieces which each piece correspond to a ordering of the coordinates. Examples in lower dimension are clear to show the meaning. By symmetry, the average maximum is just the first coordinate of the mass center of the piece bounded by points $(1,0,\ldots)$ $(1/2,1/2,0,\ldots)$ .. $(1/n,1/n,1/n,\ldots,1/n)$.

Which gives $(1+1/2+1/3+\cdots+1/n)/n$, and one can see, the average of the $k$-th value is $(1/k+\cdots+1/n)/n$.

• Hello, I need an email from you@ Yudong Tang
– user61135
Jan 26, 2015 at 16:51
• Just one question about the solution: how do you justify that the coordinate of the mass center of the piece bounded by $(1,0,…) (1/2,1/2,0,…) .. (1/n,1/n,1/n,…,1/n)$ is actually the average of all the vertices' coordinates? Oct 4, 2019 at 15:33

If you think of this as uniformly randomly choosing points from $[0,1]\times[0,1]$ and break the square into the triangles sharing the diagonal $y=x$, the expected value can be expressed as twice the integral of the function $f(x,y)=\min(x,y-x,1-y)$ over the region $0\leq x\leq y\leq 1$. You can use explicit formulas for the minimum value of 2 numbers to compute the integral. There is probably a lot more simplifying that can be done. If this seems too tedious, it is at least something you could put into Mathematica to find the answer.

Hans and Jonas pretty much tell you how to do it. You are basically trying to calculate the volume on the square with side 0:1, and coordinates of each of the random variables, and height equal to the minimum segment. So you have several regions, as shown by Jonas, each of which you could obtain an analytic integral for. There will be symmetry above/below the diagonal, so you can compute just one and double it. The problem is it is quite a bit of algebra, and it is just too easy to make a mistake. A wrote a simple monte-carlo program, pich two random values, r1,r2, compute the minimum, and do this N times. My results for the differing values of N: n=1K .111988 n=10k .111647 n=100k .111101 n=1m .111298 n=10m .111121 n=100m .111129 n=1G .111111 So it sure seems to be converging on 1/9. Monte Carlo, is a good way to gain confidence in your result, i.e. if you did an analytic solution and it agrees with the Monte Carlo result, it is probably correct. If it doesn't agree you have probably made a mistake. Programming the Monte Carlo for this problem only took a few minutes.

In extension of Hans' answer, the below shows a contour plot of the function $$f(a,b) = \min\left[\min(a,b),\quad\max(a,b)-\min(a,b),\quad1-\max(a,b) \right]$$

The picture clearly shows the triangles which we can integrate to get the expected value. if you take a geometric view, think of a unit cube representing possible random draws for the 2 cuts (x,y) , and "height" or z, representing the minimum length of the 3 pieces. it's pretty easy to show that the maximum (apex) point of the minimums is (1/3,1/3,1/3) and that the points form a pyramid - the area of the pyramid is BH (1/3) -> since H = 1/3 and B = 1, the avg of the minimums is 1/9

the pattern is the same for higher and lower dimensions - the area of a n-pyramid with a unit length base is 1/(n*n)

To provide a guideline (and avoid any solution not providing reasonable numbers):

Average of any piece:

In : a = [np.diff( + list(np.sort(np.random.uniform(0,1,size=))) + ) for _ in range(10000)]

In : np.mean(a)
Out: 0.3333333333333333


Average of largest:

In : a = [np.max(np.diff( + list(np.sort(np.random.uniform(0,1,size=))) + )) for _ in range(100000)]

In : np.mean(a)
Out: 0.6107856361897389


Average of smalles:

In : a = [np.min(np.diff( + list(np.sort(np.random.uniform(0,1,size=))) + )) for _ in range(100000)]

In : np.mean(a)
Out: 0.11126863698743916


The solution proposed by Yudong Tang is in line with the data, and uses convex polytopes, that are easy to visualize and generalize.