3
$\begingroup$

The problem is stated as follows. We have a box with $W$ white balls and $B$ black ones. Repeat $N$ times: each iteration a ball is taken out (uniformly), and put back along with $K$ (constant) more balls of the same color.

The questions:

  1. Prove that the probability to take out a black ball on the $i$-th iteration is independent of $i$. This is intuitive but I was unable to prove it (tried using induction).

  2. Define the sample space and probability function for the problem of repeating the above iteration $N$ times. The sample space is clear to me (binary vectors of length $N$) but the probability function is hard to define in a closed form.

Moreover, I'm surprised that question 2 did not come before question 1 because to solve 1, we must understand the probability space. Or is it a common approach in probability to define how we want the space to "act" and only then define the space along with the distribution function?

EDIT: Solved

  • 0
    What have you worked out for (1)? For the very first iteration, can you calculate the probability of drawing a white ball, of drawing a black ball, and the probability of drawing a black or white ball on the next iteration?2011-11-14
  • 0
    Yes I made sure probabilities in first and seconds iteration are the same but I'm having trouble generalizing it. Is digging into the sum of sums of sums.... formula the correct way to do this?2011-11-14
  • 1
    *Express formally* what?2011-11-14
  • 0
    yes, 2) is ambiguous2011-11-14
  • 0
    sorry, check out the edit2011-11-14
  • 0
    But, what is the "problem" exactly? What is the experiment? Picking a ball at the last iteration? The sequence of colors picked throughout the process?2011-11-14
  • 0
    Could you say a few words about why you _intuitively_ feel that the probability of drawing a black ball on the $i$-th draw does not depend on $i$? David Mitra's answer shows (by induction) why this is so, and you probably came up with the same result since you state that "I made sure probabilities in first and seconds iteration are the same" (but failed in extending it). But I am interested why you felt _intuitively_ that the result is true, perhaps even before you showed that the probability is the same on the first and second draws.2011-11-14
  • 0
    @Leo You are correct, my previous answer was off. I have deleted it. Very sorry.2011-11-14
  • 0
    @Dilip Sarwate - my intuition tells me that there are just as many cases where it'll be hard to pick a black ball on j-th iteration(because we've added lots of whites) as those where it'll be easier by the time we reach iteration j. So eventually there's some sort of symmetry or balance that leaves us a "clean slate" when we pick out the j-th ball. This is of course intuition alone.2011-11-14
  • 0
    @David Mitra - thanks for the effort though.2011-11-14
  • 1
    Maybe you should write up your solution more neatly as an answer, and accept it?2011-11-16
  • 0
    See also http://math.stackexchange.com/questions/64280/polya-urn-scheme-question/64513#645132011-11-16

2 Answers 2

4

There are the B and W when the game begins.

For $i = 0,1,\ldots,N$, define the random variables

$$B_i ={\rm\ number\ of\ black\ balls\ on\ iteration\ } i$$ and

$$ X_i =\cases{1,& if a black ball was drawn on iteration $i$ \cr 0,& otherwise}$$

Our induction assumption is: $P[X_i = 1] = {B\over W+B}$.

We compute $$ P[X_{i+1} = 1] = \sum_{ {\rm admiss.\ } b} P[B_i = b] \cdot{ b\over i*K+W+B } ={ E(B_i) \over i*K+W+B}.$$

Here's the magic: $B_i = B +\sum\limits_{j=0}^{i-1} {K*X_j}$.

Now $E(X_j) = P[X_j = 1] ={ B\over W+B}$ by the induction assumption. So:$$ E(B_i) = E(B)+\sum\limits_{j=0}^{i-1} {K*E(X_j)=}B + i K{B\over W+B}.$$

Going back to $ P[X_{i+1} = 1]$: $$\eqalign{ P[X_{i+1} = 1] &={ E(B_i) \over i*K+W+B}\cr & = [ B + i*K*B/(W+B) ] / i*K+W+B \cr &={ B\over B+W}. } $$ Having wasted so much time trying to prove this looking at the tedious "tree" of results, I now fully appreciate the elegance brought by linearity of expectation (even when the random variables are dependent)

  • 0
    Very nice! By the way, when I "TeXified" your post, I added an extra detail when finding $E(B_i)$. I felt it was important to emphasize that linearity of taking expectations was being used.2011-11-16
  • 0
    @David Mitra - Thanks, it is imporant to mention.2011-11-16
1

Here is an informal argument by induction, with j a positive integer.

Inductive statement(j):

  For all w, b, k, (positive integers), the chance of     drawing a black ball on the j-th draw starting from a     box with b black balls and w white balls is b/(b + w).   

The case j = 1 is clear.

Suppose correct for j. If a black ball shows on draw 1, the box will then contain (b + k) black balls and w white balls: a new starting box for draws 2 to j + 1. By the inductive assumption, the chance of getting a black ball on the j-th draw from the new box is (b + k)/((b + k) + w). The other case, a white ball shows on draw 1, is handled in the same way: the chance of getting a black ball on the j-th draw is b/(b + (w + k)). In either case, the (j + 1)-st draw of draws 1 to j + 1 is the j-th draw of draws 2 to j + 1. So the chance of black on the (j + 1)-st draw is given by:

[(b + k)/den][chance black on 1st draw] + [b/den][chance white on 1st draw]

where den = (b + k) + w = b + (w + k).

The ratio b/(b + w) occurs in both terms. If you remove it, the sum remaining is 1. That does the inductive step. (Note: the reasoning is informal, and does not make a proof. By similar standards, the first answer is likely not a proof either.)