A stick broken in three

A stick of length one is broken at two points chosen independently and uniformly along it. What is the chance that the three pieces can be put together to form a triangle? The question appears in the Cambridge examinations of the 1850s, and it is usually answered by integrating over the two break points. It has a much better answer, which is a picture, and the picture keeps working for questions that the integrals make tedious: how often $n$ pieces can form a polygon, how long the longest piece is, and why the same numbers describe points scattered on a circle.

There is also a warning in it. “Break a stick at random into three pieces” sounds like a precise instruction, and it is not. What a random chord is showed how Bertrand’s question about a circle has three answers according to how “random” is read; the stick has the same trouble, and the three readings give three different numbers.

The pieces are a point in a triangle #

Three pieces of lengths $x$, $y$ and $z$ with $x + y + z = 1$ can be drawn as a single point. Take an equilateral triangle of height 1. For any point inside it, the distances to the three sides add up to exactly 1 — a theorem of Vincenzo Viviani’s — so the three distances can be the three pieces. Every way of breaking the stick is a point of the triangle, and every point is a way of breaking the stick. Bruno de Finetti used this picture for exactly this purpose.

Two uniform cuts spread the point evenly over the triangle. The two cut positions $u$ and $v$ are uniform on a square, the pieces are $\min(u, v)$, $|u - v|$ and $1 - \max(u, v)$, and the map from the square to the triangle folds the square along its diagonal and shears each half linearly onto the whole triangle. A linear map multiplies all areas by the same factor, so equal areas of the square go to equal areas of the triangle.

Now the triangle condition. Three lengths form a triangle when each is less than the sum of the other two, and since they add to 1, that says each is less than one half. The region where $x < \tfrac12$ is everything except a corner triangle; doing this for all three pieces cuts off three corners and leaves the triangle whose vertices are the midpoints of the sides. That is exactly a quarter of the area, and so the probability is $\tfrac14$. The figure’s 500 random breaks put 118 points in the middle quarter, a share of 0.236.

The picture also explains why most breaks fail. A break fails when one piece is longer than one half, and that happens in three corner triangles, one for each piece, each with a quarter of the area. Only one piece can be longer than a half, so the corners do not overlap, and three quarters is simply three times one quarter.

More pieces #

Break the stick at $n - 1$ random points into $n$ pieces. They can form a polygon — be laid end to end to close up — exactly when the longest piece is shorter than the sum of the others, which again says the longest is shorter than one half. The corner argument generalises: the chance that a particular piece is at least a half is $1/2^{n-1}$, because it means all $n - 1$ cuts land in the half of the stick away from it, in the right arrangement; only one piece can be at least a half, so the chance that some piece is equals $n/2^{n-1}$, and

$$P(\text{polygon}) = 1 - \frac{n}{2^{n-1}}.$$

For four pieces the chance is $\tfrac12$, for five $\tfrac{11}{16}$, for ten 0.9805. The simulated shares, from 40,000 breaks for each $n$, agree with the formula to within a percentage point. A polygon is almost certain once there are many pieces, because the longest piece of a stick broken into many is very much shorter than half.

The geometric picture still holds: the $n$ pieces are a point spread evenly over an $(n-1)$-dimensional simplex, the higher-dimensional triangle, and the bad region is $n$ corner simplices, each a copy of the whole scaled by a half in every direction, so each has volume $1/2^{n-1}$ of the whole. That is the same count, read as a volume.

The pieces, in order #

How long is the shortest piece, on average, and how long the longest? There is an exact and beautiful answer. Sort the $n$ pieces from shortest to longest. The $k$-th shortest has mean

$$\frac1n\left(\frac1n + \frac1{n-1} + \cdots + \frac1{n-k+1}\right).$$

So the shortest piece averages $1/n^2$, the next $1/n^2 + 1/(n(n-1))$, and the longest averages $\frac1n H_n$, where $H_n = 1 + \tfrac12 + \cdots + \tfrac1n$.

The reason for the reciprocals is a memoryless property. The pieces behave like $n$ independent exponential waiting times divided by their total — a fact due to Alfréd Rényi — and for exponential waits, the minimum of $n$ is itself exponential with $n$ times the rate. So the shortest piece is $1/n$ of an average waiting time, scaled; after it, the remaining $n - 1$ pieces each exceed it by a fresh exponential, whose minimum adds $1/(n-1)$ of a unit; and so on. Adding the increments gives the reciprocals. For six pieces, the shortest averages $1/36$, less than a sixth of the average piece, and the longest $49/120 = 0.4083$, nearly two and a half times the average.

The longest piece and the collector #

The mean of the longest piece, $H_n/n$, is the harmonic sum divided by $n$, and the harmonic sum has appeared before in exactly this role. How long until every one turns up found that collecting all $n$ coupons of a set takes on average $n H_n$ draws — and for the same reason. The collector’s wait is a sum of $n$ geometric waits with rates $n/n, (n-1)/n, \ldots, 1/n$, and the longest piece of the stick is a sum of exponential pieces with rates $n, n - 1, \ldots, 1$, scaled. Geometric waits are the discrete form of exponential ones, and both problems are about the last of $n$ things to happen.

For two pieces the longer averages $\tfrac34$, for three the longest $\tfrac{11}{18}$, for ten 0.2929. As $n$ grows, $H_n$ grows like $\ln n + 0.5772$, so the longest piece is about $\ln n$ times the average piece. That is why polygons become almost certain: the longest of a hundred pieces averages about 0.052, nowhere near a half. It is also the first step in a more delicate theory. Broken sticks model the cycles of a randomly shuffled deck, in which the longest cycle takes a fraction of the cards that behaves like the longest piece of a stick broken in a particular sequential way, and the hundred prisoners of a puzzle about one shuffle survive exactly when that longest cycle is at most half the deck.

Random gaps and regular ones #

The pieces of a randomly broken stick are as uneven as gaps can be, in a precise sense, and setting them beside deliberately even gaps shows what that means. Turn a circle repeatedly by an irrational angle and mark the points: the three-gap theorem says that after any number of turns the gaps between neighbouring marks take at most three different lengths, and the longest is never more than a fixed multiple of the average. Random points on a circle have gaps of every length, and the longest is $\ln n$ times the average — unboundedly worse. That clumping is exactly why points chosen to be evenly spread integrate functions so much more accurately than random ones: a random sample always leaves some gap of relative size $\ln n$ in which nothing is measured.

The logarithm has a familiar source. The longest piece of a stick broken into $n$ is the stick’s version of the longest run of heads in $n$ tosses, which is about $\log_2 n$; both are the largest of about $n$ nearly independent things with exponential tails, and the largest of $n$ exponentials is $\ln n$ plus a fluctuation that does not settle. In both problems the mean is easy, a harmonic sum here, and the distribution around it is a Gumbel law in the limit.

Geometric probability of this kind — chances computed as areas or volumes in a space of configurations — began with Buffon’s needle, whose answer $2/\pi$ is the proportion of a rectangle of positions and angles in which the needle crosses a line. The broken stick is the cleanest example of the method, because its configuration space is a simplex on which the uniform distribution is forced by symmetry, and every question becomes a question about the volume of a piece of it. The same simplex holds every model in which a fixed total is divided at random with no part favoured — shares of a prize split by random cuts, the proportions of a population falling into categories under a uniform prior, the composition of a mixture — and in each of them a question about the parts is a question about a region of the simplex, answered by its volume. The matchbox problem of the matches left in the other pocket is the discrete cousin: there the total is fixed and the division is made one match at a time, and the expectation is again a sum that the picture of a region makes easy to read.

Three ways to break a stick #

Here is the warning. Suppose the stick is broken once at a uniform point, and then one of the two pieces is broken again at a uniform point along it. Which piece? The question “break a stick into three at random” does not say, and the answer depends on it.

If the longer piece is broken again, a triangle is more likely than with two simultaneous cuts. Let the longer piece have length $L$, which is uniform between $\tfrac12$ and 1. Cut it at a uniform point into $a$ and $L - a$. The shorter original piece, $1 - L$, is already under a half; the other two are under a half when $a$ lies between $L - \tfrac12$ and $\tfrac12$, an interval of length $1 - L$. So the chance is $(1 - L)/L$, and averaging over $L$,

$$\int_{1/2}^{1} 2\,\frac{1 - L}{L}\,dL = 2\ln 2 - 1 \approx 0.3863.$$

If instead a coin decides which piece to break, half the time the shorter piece is broken, the longer one stays at least a half, and no triangle is possible; the chance halves, to $\ln 2 - \tfrac12 \approx 0.1931$.

So three natural procedures, each of which could be called “breaking a stick at random into three pieces”, give 0.25, 0.386 and 0.193. The simulations, 60,000 breaks of each kind, agree with each exact value to within a percentage point. As with Bertrand’s chords, none of the three is wrong; the original question was incomplete, and a probability is a property of a procedure, not of a description. The first procedure has a special status — it is the only one of the three in which the three pieces are exchangeable, each equally likely to be any of the lengths — and that symmetry is what makes the triangle picture work.

Points on a circle #

The surprising connection is with points on a circle. Scatter $n$ points at random on a circle of circumference 1. They cut it into $n$ arcs, and the arcs are exactly the pieces of a stick of length 1 broken at $n - 1$ random points and bent round — the lengths of the arcs have the same joint distribution as the pieces, by the rotational symmetry of the circle. All $n$ points lie in some semicircle exactly when one of the arcs between neighbours is at least half the circle.

So the chance that $n$ random points on a circle lie in a semicircle is $n/2^{n-1}$, the complement of the polygon probability: $\tfrac34$ for three points, $\tfrac12$ for four, $\tfrac5{16}$ for five. J. G. Wendel proved in 1962 a far-reaching extension: for $n$ random points on a sphere in $d$ dimensions, chosen from any distribution symmetric about the centre, the chance that they lie in a hemisphere is

$$\frac{1}{2^{n-1}} \sum_{k=0}^{d-1} \binom{n-1}{k},$$

which is $n/2^{n-1}$ when $d = 2$. That formula has turned up in the theory of linear classifiers, in convex geometry and in the analysis of random polytopes, wherever one asks whether random vectors can be separated from the origin by a single plane.

Samples agree, arguments decide #

Every simulated share is a finite sample, and agreement within a percentage point is what samples of 40,000 or 60,000 should give; it confirms that the exact values are right to that accuracy and could not distinguish, say, $2\ln 2 - 1$ from 0.387. The exact values come from the arguments, not the dots. The triangle picture is drawn for three pieces only; the simplex for four pieces is a tetrahedron, and for more it cannot be drawn at all, though the volume argument is the same.

The figure of three procedures shows three readings of an ambiguous question and does not settle which reading is “correct”, because there is no correct one. And the circle figure’s individual panels are single samples, chosen by a fixed seed; they illustrate the condition, not the probability.

Seeded breaks and quoted theorems #

Computed here: 500 random breaks in de Finetti’s triangle; 40,000 simulated breaks for each $n$ from 3 to 10 against $1 - n/2^{n-1}$; the sorted means for six pieces from the formula, checked to add to 1, against 40,000 simulated breaks; 60,000 breaks under each of the three procedures; 40,000 samples of points on a circle for five values of $n$; and $H_n/n$ for $n$ to 60. Every random number comes from a fixed seed, so every figure is reproducible.

Quoted: the history of the problem, Viviani’s theorem, de Finetti’s use of the triangle, Rényi’s representation of the pieces by exponentials, and Wendel’s theorem in higher dimensions. The integral for the two-stage break is derived above.

Still open: questions with a little more structure #

The basic broken-stick questions are all solved, often in several ways. What remains open is at the edge where the pieces interact with geometry. If $n$ random points are placed in a square rather than on a stick, and the question is whether they form the vertices of a convex polygon, the answer is known — Pierre Valtr found it in 1995, $\big(\binom{2n-2}{n-1}/n!\big)^2$ — but for a disc, and for most other shapes, the exact probability that $n$ random points are in convex position is not known, only its asymptotic form. Sylvester’s four-point problem, which asks for the chance that four random points in a region form a convex quadrilateral, has an answer for each region, and Wilhelm Blaschke showed in 1917 that among convex regions the chance is largest for a disc and smallest for a triangle; the analogous extremal question for five or more points is open.

A question closer to the stick: if the pieces are required to form a polygon with sides in the order broken, and that polygon must be convex with all its vertices on a circle, the chance is the same $1 - n/2^{n-1}$, because any lengths that can close up can be arranged around a circle. Questions about which polygon is formed — its area, its angles — have answers in terms of the simplex for small $n$ and are mostly open as distributions for large $n$.

A quarter of a triangle #

Two uniform cuts make three pieces spread evenly over a triangle, and the pieces form a triangle when they land in its middle quarter, so the chance is $\tfrac14$; with $n$ pieces it is $1 - n/2^{n-1}$, and that is also the chance that $n$ random points on a circle do not all lie in one semicircle. The pieces in order have means given by sums of reciprocals, so the longest of $n$ averages $H_n/n$, about $\ln n$ times the average piece, for the same reason that a collector waits $nH_n$ draws.

The other lesson is about the word “random”. Cutting once and then cutting the longer piece gives $2\ln 2 - 1$, cutting a piece chosen by a coin gives half that, and both are honest readings of the same English sentence. The picture of a point spread evenly over a triangle belongs to only one of them, the one in which the pieces are exchangeable — which is why that reading is the one that has a picture.