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
    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
    @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.)