3
$\begingroup$

We begin with a bag containing 3 white balls and another 5 black balls. After each ball is picked, it is returned AND you add to the bag another 4 balls of the same color.

For example, the probability that the second ball I pick is black is: $\frac{3}{8}\cdot \frac{5}{12} + \frac{5}{8} \cdot \frac{9}{12}$.

$\frac{3}{8} \cdot \frac{5}{12}$ -- picking a white ball first, so in the second pick we have a bag of 12 balls, that only 5 of them are black.

$\frac{5}{8} \cdot \frac{9}{12}$ -- picking a black ball first, so in the second pick we have a bag of 12 balls, that only 9 of them are black.

I hope that simple example explains all the details in the question.

Now, the question is: What is the probability that the $100^{th}$ ball you pick is black?

I'm not looking for the final answer, but for the way of solving such questions, as what makes this question complicated for me is that the probability for picking a black ball changes in each pick.

$\endgroup$
  • $\begingroup$ It does.. I have edited this, thank you. $\endgroup$ – johni May 2 '15 at 12:30
3
$\begingroup$

Let $B_n$ be the event of picking a black ball on the $n$-th turn.

Let $a_n = 4+4n$ be the total count of balls available on the $n$-th turn. Four new balls are always added to the bag each turn.

Let $p_n$ be the probability of picking a black ball on the $n$-th turn. $p_1=5/8$

Then the count of black balls available on the $n$-th turn is $a_np_n$. Eg $a_1p_1= 5$.

Now use the Law of Total Probability.

$$\begin{align} p_{n+1} & = P(B_{n+1}) \\ & = P(B_{n+1} \mid B_{n})P(B_{n}) + P(B_{n+1}\mid \neg B_{n})(1-P(B_{n})) \end{align}$$

Can you express this in terms of $a_n$ and $p_n$?   What happens when you simplify?

$\endgroup$
  • $\begingroup$ I'm not sure if the answer is supposed to be the exact calculated probability. Assuming it is, how could I calculate P100? as it's a long recursive expression. $\endgroup$ – johni May 2 '15 at 12:33
  • $\begingroup$ No it actually isn't. Observe that: $\mathsf P(B_{n+1}\mid B_n)$ is the probability of picking a black ball on turn $n+1$ given that the last four balls added were black. Now on turn $n$ there were $a_np_n$ black balls out of $a_n$ balls. So thus:$$\mathsf P(B_{n+1}\mid B_n) = \frac{a_np_n+4}{a_n+4}$$ Apply similar logic to find $\mathsf P(B_{n+1}\mid \neg B_n)$, then simplify the expression. $\endgroup$ – Graham Kemp May 2 '15 at 13:52
  • $\begingroup$ Could it be that the probability to pick a black ball on the n'th pick remains 5/8 ? Because it doesn't seem very trivial to me, though this is the result for n = 1,2,3 $\endgroup$ – johni May 2 '15 at 14:59
  • 1
    $\begingroup$ Hmm, could be. :-) $\endgroup$ – Brian Tung May 2 '15 at 15:27
2
$\begingroup$

Added:

The probability is $\frac{5}{8}$. Graham pretty much nailed it, but didn’t want to take away your chance to work out the answer on your own. Since you’ve marked his answer correct, maybe it’s not so bad to give a full answer here.

First note that after $n$ balls are selected, and the $n$-th replacement of $1+4$ balls is made, the number of balls in the urn is $8+4(n)$.

Let $p_i$ be the probability that the $i$-th ball drawn is black. Right before the $i$-th draw, there are $8+4(i-1)=4i-4$ balls in the urn, so the expected number of black balls after $i-1$ draws and before the $i$-th draw is $b=p_i(4i-4)$.

Right after the $i$-th draw and replacement, there will $4i$ balls, among which either $b=p_i(4i-4)$ or $b+4=p_i(4i-4)+4$ will be black. There will be $p_i(4i-4)$ black balls with probability $(1-p)$ and $p_i(4i-4)+4$ with probability $p$.

Therefore, right before the $i+1$-st draw, the expected fraction of balls that are black is $$p_i\frac{p_i(4i-4)+4}{4i}+(1-p_i)\frac{p_i(4i-4)}{4i}=p_i\frac{p_i(i-1)+1}{i}+(1-p_i)\frac{p_i(i-1)}{i}.$$

At this point, you can realize that the number of extra balls added ($4$) doesn’t matter, and might as well have been zero, or you can simplify the expression for the expected fraction of balls that are black and see that it equals $p_i$.

In other words, the probability that the $i+1$-st ball is black equals the probability that the $i$-th ball is black. By induction, this probability is $\frac{5}{8}$.

This is an example of a martingale, and this example is Pólya’s Urn Model.

Everything below this line in my original answer is still fun, and perhaps useful for understanding the underlying distribution, but it doesn’t directly address your original question.


So this is a really fun problem, and I’ve drawn a picture.enter image description here Right-click and “view image” to see it larger.

Let me explain. (Let me also warn you that I won’t completely answer your question, but if I have time tomorrow, I’ll look again. I’m virtually certain the answer is $\frac{5}{8}$, as you suspect, and I think there’s a clever way to show that that I’m too tired to see.)

It’s a little involved, but I hope it’s worth it. The picture is based on a Bratelli diagram for the ball-drawing process. (Hat tips to Reem Yassawi, Karl Peterson, Anthony Quas, and other folks who I remember discussing some related problems at a workshop I attended last summer, where I learned enough about this stuff to be dangerous. Anthony can probably answer this question in a flash.)

Note that the main pyramid is composed of $2\times2$ blocks. Start at the top block and start drawing balls. If you draw a white ball, move left. If you draw a black ball, move right.

Notice the four numbers in each block.

The top two represent number of ball-drawing sequences (considering all balls distinguishable) that could have led you to that block: the left number is the number of those with White as the final draw; the right one is the number with Black as your final draw.

The bottom two numbers represent the number of White and Black balls in the urn, after the required replacement of extra balls.

An example: Note the block in the fourth level down containing the number 1755. The only way to arrive there is if you have (from the top) moved right 3 times and left 1 time. Thus this block corresponds to draw-sequences totaling 1 White and 3 Black balls.

The 1755 indicates that there are 1755 draw-sequences ending in White that lead there. There are 5265 draw-sequences ending in Black that lead there. And after you've drawn 1 White and 3 Blacks, you will have augmented the initial urn contents from 3W+5B to 7W+17Black (having added 4 extra White balls once and 4 extra Black balls thrice).

The unboxed numbers around the pyramid are there to make the calculations work with consistent formulas in Excel. The formula for the 1755 calculates $(0+585)\times3$, because to arrive with White as the final draw means you came from the box above and right. There were $0+585$ ways to get there, and there were $3$ White balls in the urn at that point.

Now, there are all kinds of interesting things involving non-commutative algebra about this problem and this diagram, but 1) I don’t understand them all, and 2) your question is about how to calculate something.

Well, you could continue this diagram in Excel for dozens more rows, but you’d quickly go beyond what Excel can do with integer calculations. Or you could redo it in Mathematica or with a computer program. The numbers you’d end up calculating reach $4^{100}\cdot100!$ or so and have about 200 digits, though. Mathematica should be fine with that.

Or you could notice that the probability you want seems to be $\frac{5}{8}$ at every level (as you observed) and try to prove that. The numbers towards the left in the picture do some checking that verifies this behavior. The pairs of numbers that get really big are the numbers of White-last and Black-last draw-sequences of $n$ balls. The bold numbers that grow slowly are the multipliers from the number of sequences at the previous level.

It looks like the number of White-last (Black-last respectively) draw-sequences for $n$ balls is $4(n+1)$ times the number for $n-1$ balls. If you can prove that, you’re done, because $\frac{5X}{5X+3X}=\frac{5}{8}$ so long as $X=X$, even if $X$ is a messy product.

The number of ways to draw $n$ balls is pretty easy to calculate, though that’s not the key. For $n=1$ it’s $3+5=8$. For $n=2$, it’s $8*12$, because no matter what color you draw, there are $12$ balls in the urn before the second draw. And so on.

That’s it for now. I doubt you need to go through all this to answer your question, but these kinds of diagrams are interesting, useful, and connected with a lot of good stuff, so here they are. Thanks for listening.

$\endgroup$

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.