On camels and straws

A famous puzzle about probability and expectation involving sum of uniform random variables.

By Vamshi Jandhyala

August 27, 2021

Puzzle

A camel is loaded with straws until its back breaks. Each straw gas a weight uniformly distributed $0$ and $1$, independent of the other straws. The camel’s back breaks as soon as the total weight of all the straws exceeds $1$.

Problem 1

Find the expected number of straws that break the camel’s back.

Solution (using integral equation)

Let $X_i$ be the random variable representing the weight of each straw and let $f(t)$ be the expected number of straws that need to be drawn such that $\sum X_i \geq t$ for $t \in [0,1]$.

We have the following integral equation:

$$ f(t) = 1 + \int_0^t f(t-x)dx $$

Differentiating on both sides, we get the differential equation $f'(t) = f(t)$ with the boundary condition $f(0)=1$.

The solution to the above differential equation is $f(t)=e^t$ and the expected number of straws is $f(1)=\textbf{e}$.

Solution (using Irwin-Hall Distribution)

Let $S_n = \sum_{i=1}^n X_n$ be the random variable representing the sum of $n$ uniform random variables (i.e. sum of the weights of $n$ straws in this case). $S_n$ follows the Irwin-Hall distribution. For $x \in [0,1]$, the PDF of $S_n$ is given by $x^n/n!$.

Let $N$ be the random variable for the number of straws required such that $\sum_{i=1}^N X_i \geq 1$. We see that

$$ \begin{aligned} \mathbb{P}[N=n] &= \mathbb{P}[S_{n-1} < 1 \text{ and } S_{n} > 1] \\
&= \mathbb{P}[1 - X_{n} < S_{n-1} < 1] \\
& = \int_0^1 \frac{1}{(n-1)!} - \frac{(1-x)^{n-1}}{(n-1)!} dx \\
& = \frac{n-1}{n!} \end{aligned} $$

The expected number of straws satisfying the condition is given by

$$ \mathbb{E}[N] = \sum_{n=2}^\infty n\cdot\mathbb{P}[N=n] = \sum_{n=2}^\infty \frac{1}{(n-2)!} = \textbf{e}. $$

Computational verification

From the simulation below, we see that the expected weight of the last straw is $\approx \textbf{2.718}$.

from random import random
runs, sum_num_straws = 1000000, 0
for _ in range(runs):
    num_straws, weight = 0,0
    while (weight < 1):
        weight += random()
    sum_num_straws += num_straws
print(sum_num_straws/runs)

Problem 2

Find the probability that the weight of the last straw is less than or equal to $x$.

Solution (using Irwin-Hall distribution)

Let $X$ be the random variable representing the weight of the last straw. We have the conditional distribution

$$ \begin{aligned} \mathbb{P}[X \leq x \text{ and } N = n] &= \mathbb{P}[X \leq x \text{ and } S_{n-1} < 1 \text{ and } S_{n} > 1] \\
&= \mathbb{P}[X \leq x \text{ and } 1 - X_{n} < S_{n-1} < 1] \\
&= \int_0^x \frac{1}{(n-1)!} - \frac{(1-x)^{n-1}}{(n-1)!} dx \\
&= \frac{(1-x)^n - 1 + nx}{n!} \end{aligned} $$

Therefore the required probability distribution for $X$ is

$$ \begin{aligned} \mathbb{P}[X \leq x] &= \sum_{n=2}^\infty \mathbb{P}[X \leq x \text { and } N=n] \\
&= e^{1-x} - e + ex \end{aligned} $$

Problem 3

Find the expected weight of the last straw that breaks the camel’s back.

Solution (using Irwin-Hall distribution)

From the probability distribution calculated above, we get the probability density function of $X$ which is $e - e^{1-x}$.

Therefore, the expected weight of the last straw is given by

$$ \mathbb{E}[X] = \int_0^1 x(e - e^{1-x}) dx = 2 - \frac{e}{2}. $$

Solution (using integral equation)

Let $X_i$ be the random variable representing the weight of each straw and let $w(t)$ be the expected weight of the last straw that needs to be drawn such that $\sum X_i \geq t$ for $t \in [0,1]$. We have the following integral equation:

$$ w(t) = \int_{t}^{1} x dx + \int_{0}^t w(t-x) dx $$

Differentiating both sides, we get the differential equation $w'(t) = -t + w(t)$ with the boundary condition $w(0) = \frac{1}{2}$.

The solution to the above differential equation is $w(t)=-\frac{1}{2}e^t + t + 1$ and the expected weight of the last straw is $w(1)=2-\frac{e}{2}$.

Computational verification

From the simulation below, we see that the expected weight of the last straw is $\approx \textbf{0.64}$.

from random import random
runs, sum_last_straw_weight = 1000000, 0
for _ in range(runs):
    weight = 0
    while (weight < 1):
        straw = random()
        weight += straw
    sum_last_straw_weight += straw
print(sum_last_straw_weight/runs)