Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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? –  ShreevatsaR Nov 14 '11 at 11:20
    
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? –  Leo Nov 14 '11 at 11:27
1  
Express formally what? –  Did Nov 14 '11 at 11:29
    
yes, 2) is ambiguous –  David Mitra Nov 14 '11 at 11:43
1  
Maybe you should write up your solution more neatly as an answer, and accept it? –  Dilip Sarwate Nov 16 '11 at 0:36

2 Answers 2

up vote 4 down vote accepted

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)

share|improve this answer
    
+1 for that final sentence! –  Byron Schmuland Nov 16 '11 at 13:25
    
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. –  David Mitra Nov 16 '11 at 13:25
    
@David Mitra - Thanks, it is imporant to mention. –  Leo Nov 16 '11 at 15:16

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.