# What is the probability that at the end of the sequence, bucket B contains ball bi

We have a bucket B which can store 1 ball at a time. Imagine a sequence of balls: {b1,b2....bn} such that ball bi appears after ball bi-1 in the sequence. The ith bi is stored in bucket B with probability 1/i replacing the ball bk,previously stored. For each i, what is the probability that at the end of the sequence, bucket B contains ball bi.

• k is less than i (k <i). – papabiceps Jul 8 '16 at 15:17
• Not sure this is clear. Does $b_1$ start in $B$? If there are, say, two balls, is the answer just $\frac 12$ for both (as there is a $\frac 12$ probability that $b_2$ replaces $b_1$)? – lulu Jul 8 '16 at 15:22
• To be clear: $B$ always contains exactly one ball (since $b_1$ was put in there with probability $1$) and whether a given ball is put in $B$ is independent of the previous balls? In which case, it seems that at the end of the day the probability that $b_i$ is in $B$ is simply the probability that it was put there $1/i$), times that none after was put instead ($\prod_{j>i}(1-1/j)$) by independence. – Clement C. Jul 8 '16 at 15:22
• But why do you refer to the $(i-1)^{st}$ $b_i$? There's only one $b_i$, right? – lulu Jul 8 '16 at 15:24
• My reading is the same as that of @ClementC. but I am not sure we have the question right. – lulu Jul 8 '16 at 15:25

## 1 Answer

$B$ always contains exactly one ball (since $b_1$ was put in there with probability $1$) and whether a given ball $b_i$ is put in the bucket $B$ is independent of the previous balls ($i < j$). Therefore, at the end of the day the probability that $b_i$ is in the bucket $B$ is simply the probability $$\mathbb{P}\{b_i\in B\text{ and } b_j\not\in B \text{ for all } j > i\}$$ which, by independence, becomes $$\mathbb{P}\{b_i\in B \}\cdot\prod_{j=i+1}^n \mathbb{P}\{b_j\not\in B\} = \frac{1}{i}\prod_{j=i+1}^n\left(1-\frac{1}{j}\right).$$

This in turn, perhaps counter-intuitively, leads to the answer being $$\frac{1}{i}\prod_{j=i+1}^n \left(1-\frac{1}{j}\right) = \frac{1}{n}.$$

(This last identity is easy to show, e.g. by induction on $1\leq i \leq n$.)

• (since b1b1 was put in there with probability 11). There's a typo probability 1 not 11 – papabiceps Jul 8 '16 at 15:44
• @papabiceps Thanks for spotting this! Apparently, copy-pasting from comments involves the joy of all $\LaTeX$ being duplicated in the plain text. – Clement C. Jul 8 '16 at 15:45