Bank vaults and probability

Question

A burglar breaks into a bank with the intention to open the vaults and steal some gold coins. He knows that each vault contains a number of 1 to 100 such coins with equal probability for each number. Since he is what we call an “ethical burglar”, he will only get 100 coins to help some people in need. How many vaults must he breach on average?

This is really confusing because we are not given how many vaults we have. Is it safe to say that since the numbers from 1 to 100 have equal probability, then we have 100 vaults? Then, if vault Number 1 has 1 coin, 2 has 2 etc, we need to open as many that will give sum of 100? And then get the average?

I need help with the interpretation and solution please!

Ok after having asked several people, here is my interpretation: We may have any number of vaults, not necessarily 100 (maybe more, maybe less) but the number of coins in them has been placed randomly, with equal probability for each number from 1 to 100.

The burglar will stop once he has collected 100 or more coins: That is, if, after the last vault, he has 99, he may open another one, with 23 coins, so he will have a total of 122 and this is OK.

Any ideas for the solution?

Thank you!

Answer 1

Let $E(n)$ be the expected number of vaults needed to obtain at least $n$ coins. By conditioning on the number $k$ of coins in the next vault, we have $$E(n)= \begin{cases} 0 &\text{if $n\le 0$}\\ 1+\displaystyle{\frac{1}{100}\sum_{k=1}^{100} E(n-k)} &\text{if $n > 0$} \end{cases} $$

To make this derivation explicit for $n>0$, let random variable $V_n$ be the number of vaults needed to obtain at least $n$ coins, and let (discrete uniform) random variable $C$ be the number of coins in a vault. By the law of total expectation, conditioning on $C$ yields \begin{align} \mathbb{E}(V_n)&=\sum_{k=1}^{100}\mathbb{E}(V_n|C=k)\mathbb{P}(C=k)\\ &=\sum_{k=1}^{100}(1+\mathbb{E}(V_{n-k}))\frac{1}{100}\\ &=1+\frac{1}{100}\sum_{k=1}^{100}\mathbb{E}(V_{n-k}) \end{align}

We want to compute $E(100)$, which turns out to be approximately 2.678. You can verify that $E(n)=1.01^{n-1}$ satisfies the recursion if $n>0$, so the exact value is $E(100)=1.01^{99}$.

Answer 2

It doesn't matter how many vaults there are - you open the first one you come to and it will have an amount of coins in which can be any number between 1 and 100 with equal probability.

You pocket all those coins and move onto the next vault. This vault also has between 1 and 100 coins in, again with equal probability for each number.

You add together these coins and the ones already in your pocket. If this number is greater than or equal to 100 then you stop and leave with your 100 coins. If you have less than 100 coins, then you pocket all the coins and move on to the next vault, repeating the process until you have the desired 100 coins

Answer 3

Very nice problem! You can safely assume that there are exactly $100$ vaults since this is the maximal number of vaults the burglar may have to open. (See below for an argument.)

My take on the interpretation is as follows: Number the vaults $V_1, V_2, \ldots, V_{100}$ and say that the burglar opens $V_1$ first, then $V_2$ if necessary, and then $V_3$ and so on. Suppose that the number of coins in vault $V_i$ is $C_i$. There are $N = 100^{100}$ different possible configurations of coins in the vaults, all of which are equally likely if we assume that the contents of different vaults are independent. That is, for any $(n_1, \ldots, n_{100}) \in S:= \lbrace 1, \ldots, 100 \rbrace^{100}$, \begin{align*} P\left( C_1 = n_1, \ldots, C_{100} = n_{100} \right) = \frac{1}{N}. \end{align*} For $\textbf{n} = (n_1, \ldots, n_{100}) \in S$, corresponding to specific configuration of coins, let

\begin{align*} b(\textbf{n}) = \min \left\lbrace 1 \leqslant x \leqslant 100 \mid n_1 + \cdots + n_x \geqslant 100 \right\rbrace. \end{align*}

The problem is to compute \begin{align*} P_{100} := \frac{1}{\# S} \sum_{\textbf{n} \in S} b(\textbf{n}) = \frac{1}{N} \sum_{\textbf{n} \in S} b(\textbf{n}). \end{align*}

To see why you can assume that there are only $100$ vaults, consider $100 + k$ vaults for some $k \geqslant 1$. Then (extending our notation in an obvious way) we have

\begin{align*} P\left( C_1 = n_1, \ldots, C_{100 + k} = n_{100 + k} \right) = \frac{1}{100^k N}. \end{align*} But for $\textbf{n} = (n_1, \ldots, n_{100+k})$, it is clear that $b (\textbf{n})$ is independent of $n_{101}, \ldots, n_{100+k}$ since $n_i \geqslant 1$ for all $i$. Letting $S_{100+k} = \lbrace 1, \ldots, 100 \rbrace^{100 + k} = S \times \lbrace 1, \ldots, 100 \rbrace^k$, we now see that the average number of vaults the burglar needs to open in the case of $100 + k$ vaults is \begin{align*} P_{100+k} := \frac{1}{100^k N} \sum_{\textbf{n} \in S_{100 + k}} b(\textbf{n}) = \frac{100^k}{100^k N} \sum_{\textbf{n} \in S} b(\textbf{n}) = P_{100}, \end{align*} since there are precisely $100^k$ ways to choose the last $k$ entries of the $(100+k)$-tuple n, and $b(\textbf{n})$ is independent of these entries.