2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ k is less than i (k <i). $\endgroup$ – papabiceps Jul 8 '16 at 15:17
  • $\begingroup$ 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$)? $\endgroup$ – lulu Jul 8 '16 at 15:22
  • $\begingroup$ 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. $\endgroup$ – Clement C. Jul 8 '16 at 15:22
  • $\begingroup$ But why do you refer to the $(i-1)^{st}$ $b_i$? There's only one $b_i$, right? $\endgroup$ – lulu Jul 8 '16 at 15:24
  • $\begingroup$ My reading is the same as that of @ClementC. but I am not sure we have the question right. $\endgroup$ – lulu Jul 8 '16 at 15:25
3
$\begingroup$

$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$.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.