Breaking a slide rule into four pieces

Problem

The Riddler Manufacturing Company makes all sorts of mathematical tools: compasses, protractors, slide rules — you name it!

Recently, there was an issue with the production of foot-long rulers. It seems that each ruler was accidentally sliced at three random points along the ruler, resulting in four pieces. Looking on the bright side, that means there are now four times as many rulers — they just happen to have different lengths.

On average, how long are the pieces that contain the 6-inch mark?

Order Statistics

Let $X_1,X_2, \cdots, X_n$ be a random sample of size $n$ from a continuous distribution with distribution function $F(x)$ . We order the random sample in increasing order and obtain $Y_1,Y_2, \cdots, Y_n$ . In other words, we have:

$Y_1$ = the smallest of $X_1,X_2, \cdots, X_n$ $Y_2$ = the second smallest of $X_1,X_2, \cdots, X_n$ $\cdot \\ \cdot \\ \cdot \\$ $Y_n=$ the largest of $X_1,X_2, \cdots, X_n$ We set $Y_{min}=Y_1$ and $Y_{max}=Y_n$ . The order statistic $Y_i$ is called the $i^{th}$ order statistic. Since we are working with a continuous distribution, we assume that the probability of two sample items being equal is zero. Thus we can assume that $Y_1<Y_2< \cdots <Y_n$ . That is, the probability of a tie is zero among the order statistics.

The Distribution Functions of the Order Statistics

The distribution function of $Y_i$ is an upper tail of a binomial distribution. If the event $Y_i \le y$ occurs, then there are at least $i$ many $X_j$ in the sample that are less than or equal to $y$ . Consider the event that $X \le y$ as a success and $F(y)=P[X \le y]$ as the probability of success. Then the drawing of each sample item becomes a Bernoulli trial (a success or a failure). We are interested in the probability of having at least $i$ many successes. Thus the following is the distribution function of $Y_i$ :

F_{Y_i}(y)=P[Y_i \le y]=\sum \limits_{k=i}^{n} \binom{n}{k} F(y)^k [1-F(y)]^{n-k}

The Probability Density Functions of the Order Statistics

The probability density function of $Y_i$ is given by:

f_{Y_i}(y)=\frac{n!}{(i-1)! (n-i)!} \thinspace F(y)^{i-1} \thinspace [1-F(y)]^{n-i} f_X(y)

The details of the derivation can be found here - Order Statistics.

The Order Statistics of the Uniform Distribution

When $X_i \sim \mathcal{U}[0,1]$ , we have $F(y) = y$ and $f_X(y)=1$ , therefore

F_{Y_i}(y)=P[Y_i \le y]=\sum \limits_{k=i}^{n} \binom{n}{k} y^k (1-y)^{n-k}

f_{Y_i}(y)=\frac{n!}{(i-1)! (n-i)!} \thinspace y^{i-1} \thinspace (1-y)^{n-i}

\begin{align*} \mathbb{E}[Y_i] &= \int_0^1 f_{Y_i}(y) y dy \\ &= \int_0^1 i \binom{n}{i}y^i(1-y)^{n-i}dy = \frac{i}{n+1} \end{align*}

Solution

Let $LY_1,LY_2$ and $LY_n$ be the $n$ places where the ruler has been sliced where $L$ is the length of the ruler in inches, $X_i \sim \mathcal{U}[0,1]$ and $Y_i$ are the order statistics of the Uniform distribution.

When the mark $m$ lies between $LY_k$ and $LY_{k+1}$ , we have

\begin{align*} \mathbb{P}[Y_k \le a \le Y_{k+1}] &= 1 - \left( \mathbb{P}[Y_{k+1} \le a] + \mathbb{P}[Y_{k} \ge a] \right) \\ &= 1- \left(F_{Y_{k+1}}(a) + 1 - F_{Y_{k}}(a)\right) \\ &= F_{Y_{k}}(a) - F_{Y_{k+1}}(a) \\ &= \binom{n}{k}a^k(1-a)^{n-k} \\ \end{align*}

\mathbb{E}[LY_{k+1}-LY_{k}|Y_{k} \le a \le Y_{k+1}] = \frac{m}{k+1} + \frac{L-m}{n-k+1}

where $a = \frac{m}{L}$ .

The average length of the piece which has the $m$ inch mark is given by

\begin{align*} (1-F_{Y_1}(a))(m+ \frac{L-m}{n+1}) + (F_{Y_1}(a) - F_{Y_2}(a))(\frac{m}{2} + \frac{L-m}{n}) + \\ \cdots + F_{Y_n}(a)(\frac{m}{n+1}+L-m) \\ = (1-a)^n(m + \frac{L-m}{n+1}) + \binom{n}{1}a(1-a)^{n-1}(\frac{m}{2} + \frac{L-m}{n}) + \\ \cdots + a^n(\frac{m}{n+1}+L-m)\\ = m \int_0^1 (ax + 1-a)^ndx + (L-m)\int_0^1 (a + (1-a)x)^ndx \\ = \frac{m}{a(n+1)} - \frac{m(1-a)^{n+1}}{a(n+1)} + \frac{m}{a(n+1)} - \frac{(L-m)a^{n+1}}{(1-a)(n+1)} \\ = \frac{L}{n+1} \left(2 - (1-a)^{n+1} - a^{n+1} \right) \end{align*}

In the given problem, $L=12$ , $m=6$ , $n=3$ and $a = \frac{6}{12} = \frac{1}{2}$ , therefore the average length of the piece we are interested in is given by

\frac{12}{3+1} \left(2 - \frac{1}{2^{3+1}} - \frac{1}{2^{3+1}} \right) = 6 - \frac{3}{8} = 5.625

Computational solution in Python

from random import uniform

l = 0
u = 12
m = 6
n = 4
runs = 500000

tl = 0
for _ in range(runs):
    endpoints = [l] + sorted([uniform(l, u) for _ in range(n-1)]) + [u]
    for i, ep in enumerate(endpoints[:-1]):
        if ep < m < endpoints[i+1]:
            tl += (endpoints[i+1] - ep)

print("Avg length of the piece that contains the mark:", tl/runs)

Ikigai

Basics of network science with Networkx - 2