2
$\begingroup$

I've been trying to find a way to solve this question for some time now, but nothing seems to work.

Suppose we have a box. Inside it are 1 white and 1 black marble. We play the game for n rounds, where for each round we choose randomly a marble and then put it back along with an extra of the same colour. So, after round 2, we'd have 1 white and 2 black or 2 white and 1 black, etc.

I am looking for the probability that the number of white marbles, X, is x by the end of the game (after n rounds). Therefore:

$$P[X=x]$$ where $x={1,...,1+n}$.

I know that by the end of the game I'll have 2+n marbles, black and white. I also have made a diagram that shows me that I get 1 more state the more I play.

I originally thought I could solve this by assuming the variable follows a binomial distribution, but... doesn't the probability that we pick a white or black marble change the more we play?

My second attempt was to see if I could solve this by using first step analysis, but I'm not sure if that's correct. I also tried to see if any other distribution methods worked, but none that I find take the extra added ball into consideration. Any help?

$\endgroup$
1
  • $\begingroup$ I am unsure, but I suspect that this question has been asked before on mathSE. Assuming not, my first try, which might fail would be recursion. That is, I would compute $p(X = x)$, given $n = 1$. Then, I would try to use this computation to compute $p(X = x)$, given $n = 2$. I would probably extend that to $n=3$ and $n=4$. Then, I would attempt to examine the data, looking for patterns. My goal would be to create a conjecture for the computation of $p(X = x)$, given that there are $n$ rounds. Then, I would attempt to prove the conjecture. ...And better you than me. $\endgroup$ Nov 7, 2021 at 14:20

1 Answer 1

1
$\begingroup$

After $n$ rounds, the box contains $m = n + 2$ marbles. Let $(B, W)$ be the state of the box containing $B$ black marbles and $W$ white marbles. So $B + W = m$. The probability of drawing a black marble is $B/m$, and the probability of drawing a white marble is $W/m$. So $(B, W)$ transitions to $(B+1, W)$ with probability $B/(B+W)$, and to $(B, W+1)$ with probability $W/(B+W)$.

Conversely, for $B, W > 1$, we can get to state $(B, W)$ from $(B-1, W)$ with probability $(B-1)/(B+W-1)$, or from $(B, W-1)$ with probability $(W-1)/(B+W-1)$.

This leads to the interesting situation that each state in a given round has the same probability!

Here's a diagram showing the states and the transition probabilities for 4 rounds of the game.

                    (1, 1)
                   1/2  1/2
               (2, 1)    (1, 2)
              2/3  1/3  1/3  2/3
          (3, 1)    (2, 2)    (1, 3)
         3/4  1/4  2/4  2/4  1/4  3/4
     (4, 1)    (3, 2)    (2, 3)    (1, 4)
    4/5  1/5  3/5  2/5  2/5  3/5  1/5  4/5
(5, 1)    (4, 2)    (3, 3)    (2, 4)    (1, 5)

So when there are $m$ marbles in the box, the probability that the box contains $x$ white marbles is simply $\frac1{m-1} = \frac1{n+1}$.


This is essentially a proof by mathematical induction. Clearly, in the initial state $(1, 1)$, when $n=0$ and $m=2$, the probability of 1 white ball is 1.

After one round, $m=3$, and the two possible states $(2, 1), (1, 2)$ have equal probability of $\frac12$.

In the next round, when $m=4$, we have three possible states, $(3, 1), (2, 2), (1, 3)$. We can only get to $(3, 1)$ from $(2, 1)$, with probability $\frac23$, but the probability of $(2, 1)$ is $\frac12$, so the total probability of getting to $(3, 1)$ from the initial $(1, 1)$ state is $\frac12×\frac23=\frac13$.

The case for $(1, 3)$ is the same by symmetry, so it has the same probability, $\frac13$.

The case for $(2, 2)$ is more interesting. We can get to that state either from $(2, 1)$ or $(1, 2)$, in both cases with probability $\frac13$, so we need to add those probabilities, which gives us $(\frac12×\frac13)+(\frac12×\frac13)=\frac13$.

Thus each of the 3 states in the $m=4$ row have the same probability, $\frac13$.

Let's assume that our hypothesis of equal probabilities is true for all rows up to some $m$. The same reasoning we used on the first few rows applies to subsequent rows, so if the hypothesis is true for row $m$ it should also be true for row $m+1$

The probability of $(m-1, 1)$ going to $(m, 1)$ is $\frac{m-1}m$, so the total probability of $(m, 1)$ is $\frac1{m-1}×\frac{m-1}m=\frac1m$.

As mentioned earlier, a general state $(B, W)$ inside the triangle diagram (with both $B, W > 1$) with $B+W=m+1$ has two parent states, $(B-1, W)$ and $(B, W-1)$, with associated transition probabilities $(B-1)/m$ and $(W-1)/m$. We add those probabilities, and multiply by the probability of the parent row:

$$\left(\frac{B-1}m + \frac{W-1}m\right) × \frac1{m-1}$$ $$=\frac{m-1}m\frac1{m-1}= \frac1m$$

Thus each state in the $m+1$ row has probability $\frac1m$, and so by induction the hypothesis is true for all $m\ge2$.

$\endgroup$
5
  • $\begingroup$ $\frac{1}{m-1}$ $\endgroup$ Nov 7, 2021 at 17:31
  • $\begingroup$ Thanks, @Daniel! The dreaded off-by-one error strikes again. :) $\endgroup$
    – PM 2Ring
    Nov 7, 2021 at 17:35
  • $\begingroup$ Can you explain how you got that each state has the same probability? $\endgroup$
    – Tita
    Nov 7, 2021 at 19:47
  • 1
    $\begingroup$ @Tita I'll add some more info to my answer in a while. But briefly, if each state in a given row has the same probability ($\frac1{m-1}$), then the transition rules guarantee that the next row will too. $\endgroup$
    – PM 2Ring
    Nov 7, 2021 at 19:54
  • 1
    $\begingroup$ @Tita I've expanded my answer. $\endgroup$
    – PM 2Ring
    Nov 7, 2021 at 22:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .