# Urn Probability Problem (conditional replacement)

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.

• I would start by looking at the case $M=1$, and then $M=2$, to see if that helps with the general case. Dec 14 '15 at 8:40
• 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.
– BGM
Dec 14 '15 at 8:43
• 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} Dec 14 '15 at 8:45
• Note that $Y-X=M$ so you only really have to calculate one of them 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}$

where

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