# Probability that we get X white marbles.

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?

• 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. Commented Nov 7, 2021 at 14:20

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

• $\frac{1}{m-1}$ Commented Nov 7, 2021 at 17:31
• Thanks, @Daniel! The dreaded off-by-one error strikes again. :) Commented Nov 7, 2021 at 17:35
• Can you explain how you got that each state has the same probability?
– Tita
Commented Nov 7, 2021 at 19:47
• @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. Commented Nov 7, 2021 at 19:54
• @Tita I've expanded my answer. Commented Nov 7, 2021 at 22:15