4

May you have an idea for the following exercise I found from some olympiad.

Each day you have to bring home one full can of water. To do so you go to the next well and make the can full. On the way home you loose a proportion which is uniformly distributed on [0,1].

Question: How many times, on average, do you need to go and get water each day?

Intuitively I would guess the answer is 2 but I do not know how to show this formally.

Sasha
  • 70,631
Alexander
  • 1,251

1 Answers1

4

Suppose $U_k$ is the amount of water you bring during $k$-th visit to the well, and $\{U_k\}$ are iid uniform random variables on $(0,1)$. Let $N$ denote the random variable of the number of trips to the well needed to bring home a full can.

Then $$ \{N=n\}= \{ U_1+\cdots+U_{n-1} < 1, U_1+\cdots+U_{n-1} + U_n \geqslant 1 \} $$ That is $$ \mathbb{P}\left(N=n\right) = \mathbb{P}\left( U_1+\cdots+U_{n-1} < 1, U_1+\cdots+U_{n-1} + U_n \geqslant 1 \right) = \frac{1}{n \cdot (n-2)!} \tag{$\ast$} $$ The expected number of trips is thus: $$ \mathbb{E}\left(N\right) = \sum_{n=2}^\infty n \frac{1}{n \cdot (n-2)!} = \mathrm{e} \approx 2.71828 > 2 $$

To prove $(\ast)$ note that $V_{n-1} = U_1 + \cdots + U_{n-1}$ follows Irwin-Hall distribution, and that $$ \mathbb{P}\left(V_{n-1} < v \leqslant 1\right) = \frac{v^{n-1}}{(n-1)!} $$ as a volume of the corner section of $n-1$-dimensional unit hypercube by the plane $u_1 + \cdots + u_{n-1} = v$. Therefore, $f_V(v) = \frac{v^{n-2}}{(n-2)!}$ for $0<v<1$. $$ \mathbb{P}(N=n) = \mathbb{P}\left( V_{n-1} < 1, U_{n} + V_{n-1} > 1\right) = \int_0^1 \int_{1-v}^1 \frac{v^{n-2}}{(n-2)!} \mathrm{d} v \mathrm{d}u = \frac{1}{n (n-2)!} $$

Sasha
  • 70,631
  • Thank you very much, could you explain me a little more in detail why $P(V_{n-1}<v\le 1)=\frac{v^{n-1}}{(n-1)!}$, I do not exactly understand what you mean with "as a volume of the corner section" – Alexander Mar 18 '13 at 18:43
  • Computing this volume amounts to evaluating $$\int_0^v \mathrm{d}u_1 \int_0^{v-u_1} \mathrm{d} u_2 \cdots \int_0^{v-u_1-\cdots-u_{n-2}} \mathrm{d} u_{n-1} $$ Rescaling all variables $u_k = v t_k$: $$ v^{n-1} \int_0^1 \mathrm{d}t_1 \int_0^{1-t_1} \mathrm{d} t_2 \cdots \int_0^{1-t_1-\cdots-t_{n-2}} \mathrm{d} t_{n-1}$$ The latter integral is the volume of the $n$-cube $0<t_k<1$ cut by $t_1+\cdots+t_{n-1}<1$ which equals $\frac{1}{(n-1)!}$ by symmetry. – Sasha Mar 18 '13 at 19:08