## 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)