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$ – Guilherme Thompson 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

$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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