Three Marbles in Pólya's Urn
You have an urn with three marbles in it, a red one a yellow one and a blue one. Every ten seconds you pull out one marble at random and replace it together with one of the same color. e.g. If you pick out a red marble, you will replace it with two red marbles.
So, now the question...
The probability that at some point you will have 8 red marbles, 12 yellow marbles, and 3 blue ones after the corresponding number of moves is b a , where a and b are coprime positive integers .
What is a + b ?
Image credit: www.funeral-urn.com
The answer is 232.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Ah.... Nice solution, @Mark Hennings ! :)
What does the terms P ⊂ u − 1 , v , w × u mean ?
Log in to reply
Think of how it might be possible to have u + 1 , v + 1 , w + 1 reds, blues and greens after u + v + w picks.. You could have u , v + 1 , w + 1 of each after u + v + w − 1 picks, and then pick a red ball (to get another one). The probability of this happening is p u − 1 , v , w × u + v + w + 2 u . Alternatively you could have u + 1 , v , w + 1 of the colours, and then pick a blue, or else you could have u + 1 , v + 1 , w of the colours, and then pick a green. These are the three ways you could end up with u + 1 , v + 1 , w + 1 of each colour. My first formula expresses precisely that.
It just so happens that with Polya's urn starting with the given distribution, the probabilities of all outcomes yielding n marbles are all equally likely.
So define P ( n ) = probability of any given arrangement of n marbles after n − 3 moves.
P ( n ) = T n − 2 1 where T n = 2 n × ( n + 1 )
In this case n = 8 + 1 2 + 3 = 2 3 .
So, P ( 2 3 ) = T 2 1 1 = 2 3 1 1
1 + 2 3 1 = 2 3 2
You haven't proved that the distribution is equally likely. Here's a quick sketch:
This can be done by induction on the number of marbles. To get r red marbles, y yellow marbles, and b blue marbles (aka the state ( r , y , b ) ), you can either pick one red out from the state ( r − 1 , y , b ) with probability ( r − 1 ) + y + b r − 1 , one yellow out from the state ( r , y − 1 , b ) with probability r + ( y − 1 ) + b y − 1 , or one blue out from the state ( r , y , b − 1 ) with probability r + y + ( b − 1 ) b − 1 . By induction hypothesis, all these previous states have the same constant probability p of occurring, and thus the probability for state ( r , y , b ) is just p ⋅ r + y + b − 1 ( r − 1 ) + ( y − 1 ) + ( b − 1 ) , which is constant because r + y + b is fixed.
I didn't know about Pólya's urn process before, so thanks for the introduction. I solved the problem from "scratch" and was surprised (and relieved) to discover the equal outcome probabilities observation you've mentioned. I ended up with the same result (in a roundabout way) in the form ( 2 2 2 ) 1 , after which I recognized ( 2 2 2 ) as being the number of non-negative integer solutions to the equation a + b + c = 2 0 , (representing the 2 0 moves taken).
How would all the outcomes be equally likely? For example the probability of having 21 blue 1 red 1 green marble is clearly 1/3^20, while the probability of having 8 blue 8 red 7 green marbles is (20!/7!/13!)*(13!/7!/6!)/3^20. So the solution is incorrect in my opinion.
Log in to reply
Your "clearly" is wrong. The probability of getting 21 blue 1 red 1 green is 3 1 ⋅ 4 2 ⋅ 5 3 ⋅ … ⋅ 2 2 2 0 ; the probability of picking a blue with 1 blue in 3, times the probability of picking a blue with 2 blue in 4, times the probability of picking a blue with 3 blue in 5, and so on until 20 blue in 22.
I think you forgot to replace the marble you draw wirth TWO marbles of that colour.
Without knowing that all outcomes are equally likely or even thinking about it, cries , you can use the following way to solve this. We know that we have to draw 7 red, 11 yellow and 2 blue marbles. Think about a way of first drawing all blue balls, then the red ones, then the yellow ones, the probability for that is: 3 × 4 × 5 × 6 × 7 × . . . × 2 1 × 2 2 1 × 2 × 1 × 2 × 3 × 4 × 5 × 6 × 7 × 1 × 2 × 3 × . . . × 1 1 = 2 2 ! 2 ! × 7 ! × 1 1 ! × 2 ! . Remember this is just one way how to get to the preferred end arrangement and all those ( 1 1 2 0 ) ⋅ ( 7 9 ) ways are equally likely. So the probability of the given distribution is: = 2 2 ! 2 ! × 7 ! × 1 1 ! × 2 ! ⋅ ( 1 1 2 0 ) ⋅ ( 7 9 ) which can easily be reduced to 2 3 1 1 . So the answer is 1+231=232. In that way we can derive a general formula for x red marbles y yellow marbles and z blue marbles to be P = ( x + y + z − 1 ) ( x + y + z − 2 ) 2 ! . However, @Geoff Pilling 's solution appears to be simpler.
Typo: drawing all blue balls, then the red ones, then the yellow ones
Very nice write up @Aaa Bbb ... On the contrary, it is likely more robust than mine as it doesn't assume any prior knowledge of Pólya's Urn.
how did you get( 20 choose 11)( 9 choose 7)
That's the number of distinct ways that 11 yellow, 7 red and 2 blue marbles can be arranged
Let p u , v , w be the probability that there are u + 1 reds, v + 1 blues and w + 1 yellows in the urn after u + v + w picks. Then p 0 , 0 , 0 = 1 and p u , v , w = u + v + w + 2 p u − 1 , v , w × u + p u , v − 1 , w × v + p u , v , w − 1 × w A simple induction on u + v + w shows that p u , v , w = ( u + v + w + 1 ) ( u + v + w + 2 ) 2 for all u , v , w ≥ 0 . The probability we want is p 7 , 1 1 , 2 = 2 3 1 1 , so the answer is 2 3 2 .