Probability question

[Antrax]

From my homework:

A jar contains A black balls and B white balls. A series of balls is chosen by the following rules: every time one ball is chosen at random, then is put back in the jar, plus C more balls of the same color.
a) What is the probability that after n such selections, n1 black balls and n2 white balls are chosen?
b) given that the second ball to be taken out was black, what's the probability the first one was white?

c is trivial, but I'm fairly stumped with the rest. Help?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[extropalopakettle]

This is just a start, off the top of my head, for (a). I'd do it as a recurrence relation.

Let P(n,k) mean the probability that after n iterations, k black balls (and n-k white balls) were chosen.

P(n,k) = 0 for k>n
P(n,k) = 0 for k<0
P(1,1) = A/(A+B)

P(n,k) = P(black chosen on Nth iteration GIVEN k-1 blacks were chosen during previous n-1 iterations) * P(n-1, k-1) + P(white chosen on Nth iteration GIVEN k blacks were chosen during previous n-1 iterations) * P(n-1, k)


P(black chosen on Nth iteration GIVEN k-1 blacks were chosen during previous n-1 iterations) = (A+C*(k-1)) / (A+B+C*(n-1))

P(white chosen on Nth iteration GIVEN k blacks were chosen during previous n-1 iterations) = (B+C*(n-k)) / (A+B+C*(n-1))

So, the defining recursive equation is:
1) P(n,k) = (A+C*(k-1)) / (A+B+C*(n-1)) * P(n-1, k-1) + (B+C*(n-k)) / (A+B+C*(n-1)) * P(n-1, k)
2) P(n,k) = 0 for k>n
3) P(n,k) = 0 for k<0
4) P(1,1) = A/(A+B)

Now, to solve that non-recursively .... ?

By the way, if solving for P(n,k) recursively with the above equation, the number of different P(x,y) instance you'll have to solve for, excluding the base cases which are trivial, is (n-k+1)*k = nk-k^2+k, which in the worst case (where k is about half n), is about n^2/4.

[kevinatilusa]

Consider any specific ordering for the n balls we pick out of the jar (e.g. WWB or BWB). At any given step the probability that the next ball is white is equal to (# of white balls in the jar)/(# of balls in the jar). The probability that we get exactly the ordering we're looking for is equal to the product of the fractions corresponding to to the probability we get the desired ball at each stage.

The denominators of the fractions are A+B, A+B+C, A+B+2C, ...

The numerators of the fractions corresponding to when we're trying to pick white balls out are A, A+C, A+2C, ...

The numerators of the fractions corresponding to when we're trying to pick black balls out are B, B+C, B+2C, ...

Although the fractions may be different for each ordering, the product of all the numerators (and therefore the probability of getting that ordering) depends only on the number of white balls and the number of black balls occurring in it! For example, consider the case A=1, B=2, C=3, and the two orderings WWB, WBW.

The probability of the first ordering is (1/3)*(4/6)*(2/9) (at the first stage there's 1 white ball out of 3, then 4 white balls out of 6, then two black balls out of 9). The probability of the second ordering is (2/3)*(1/6)*(4/9) (2 black balls out of 3, then 1 white ball out of 6, then 4 black balls out of 9). The numerators may have switched themselves around, but the product is still the same.

Therefore the probability of getting n1 white balls and n2 black balls is equal to (the number of different orderings we can pick which have n1 white balls and n2 black balls)*(the probability of getting each such ordering). If you worked out the fractions above you'll have the second term in the product here, or alternatively you can just work it out for a simpler ordering like WW...WBB... B (it doesn't matter which ordering you pick since they all have the same probability).

For (b), remember that (probability of A given B) is equal to (probability of A and B) divided by (probability of B).

So in this case, the probability you want is
(Probability of drawing a white, then a black)
-----------------------------------------------------------------------------
(probability of drawing a white, then a black + probability of drawing black, then black)
and you can just calculate the necessary probabilities directly

Note that (by a) the odds of drawing white, then black are the same as drawing black, then white, so the answer you get should be equal to

(Prob of BW)
------------------------------ = Prob(2nd ball is white after you draw a black one)!
(Prob of BW + Prob of BB)


As a sidenote, part (a) of this problem appeared as question B1 on the 2002 Putnam Exam (with n1=49=n2, C=1, and W=B=1). It turns out that with those numbers the final probabilities simplify down rather drastically.

[Antrax]

Thanks both - I ended up getting kevinatilusa's solution last night, more or less. Proved by induction the probability of choosing a black ball at the nth picking is a/(a+b), and from there I did pretty much the same. Good to see it's not trivial (putnam is for really cool math people, right? )
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!