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)- How to cite
-
Jandhyala, Vamshi. 2021. “On Cames and Straws’, August 27, 2021. URL