I am working through Parzen and I came across a problem that has completely stumped me.

I have an urn which has $M$ black balls and $N$ white balls. Each turn, I reach in and randomly choose one ball without replacement. If the ball is black, I add one white ball to the urn. If the ball is white, I do nothing. I want to know $X$, the expected number of white balls I will have when I drawn all of the black balls and also $Y$, the expected number of draws necessary to have drawn all of the black balls.

No approach I can think of helps: indicator variables, re-arrangements, thinking about the event before the last event, recasting $\operatorname{P}(Y = y) = \operatorname{P}(Y>y-1)-\operatorname{P}(Y>y)$, etc. If someone could give me a hint as to how to start, I'd be most appreciative.

  • $\begingroup$ I would start by looking at the case $M=1$, and then $M=2$, to see if that helps with the general case. $\endgroup$
    – Henry
    Dec 14 '15 at 8:40
  • 1
    $\begingroup$ If you let $f(m, n)$ be the expected number of terms to drawn all black balls, then it satisfy a recurrence relationship $ f(m, n) = \frac {m} {m+n} f(m-1, n+1) + \frac {n} {m+n} f(m, n-1) + 1, f(0,n) = 0 $. It is a markov chain type problem with the use of first step analysis. $\endgroup$
    – BGM
    Dec 14 '15 at 8:43
  • 2
    $\begingroup$ Look at this Markov Chain in $\mathbb{N}^2$, with transitions: \begin{align} (m,n) \mapsto \begin{cases} (m-1,n+1) \qquad & \frac{m}{m+n}\\ (m,n-1) \qquad & \frac{n}{m+n} \end{cases} \end{align} $\endgroup$ Dec 14 '15 at 8:45
  • 1
    $\begingroup$ Note that $Y-X=M$ so you only really have to calculate one of them $\endgroup$
    – Henry
    Dec 14 '15 at 8:58

Each white ball that we start out with has probability $\frac1{M+1}$ of being drawn after all $M$ black balls. The white ball that's added when there are $k$ black balls left has probability $\frac1{k+1}$ of being drawn after all $k$ remaining black balls. Thus the expected number of white balls left when the last black ball is drawn is

$$ \frac N{M+1}+\sum_{k=0}^{M-1}\frac1{k+1}=\frac N{M+1}+H_M\;. $$

The number of draws is simply the total number of balls minus the number left in the end. The total number of balls is $N+2M$, so the expected number of draws is

$$ N+2M-\frac N{M+1}-H_M\;. $$


$\mathbf{E}(X | m=M,n=N)={F(m) \over m!} + {n \over m+1}$


$F(m)=\begin{cases} F(m-1)*m+(m-1)! &, & m>0\\0&,&m=0 \end{cases}$

This formula is based on experiments in Excel. I constructed the following spreadsheet based on the rules given, and recorded what appeared in B1 (the expected value of X) as I manipulated the initial condition.

Screenshot of spreadsheet where initial condition of urn is (M=6, N=2)

  • The magenta cells are M, the number of remaining black balls.
  • The cyan cells are N, the number of remaining white balls.
  • The red cell is 1, the initial state of the urn consisting of M black and N white balls.
  • The yellow and green cells (M>1,N>1) are the Markov Chain probabilities of arriving at a particular state (m,n).
  • The light blue cells are the probabilities of arriving at each X (between 1 and M+N)
  • The top row of orange cells is each individual X*P(X), used to compute E(X), the black cell.

The formulas for each cell are:

  • A3 : 0
  • A4 : =A3+1 (magenta cells)
  • B2 : 0
  • C2 : =B2+1 (cyan cells)
  • B4 : =C\$2/(C\$2+\$A4)*C4 (yellow cells)
  • C3 : =\$A4/(\$A4+B\$2)*B4 (light blue cells)
  • C4 : =D\$2/(D\$2+\$A4)*D4+\$A5/(\$A5+B$2)*B5 (green cells)
  • C1 : =C2*C3 (orange cells)
  • B1 : =SUM(C1:Z1) (black cell)

I couldn't tell you why the formula comes out the way it does, but it works.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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