This is an example from Probability, Random Variables and Stochastic Process by Papoulis
A box contains m white balls and n black balls. Balls are drawn at random one at a time without replacement. Find the probability of encountering a white ball by the kth draw.
$W_k=$ {a white ball is drawn by the kth draw}
$X_i=$ {i black balls followed by a white ball are drawn}
$W_k=X_0\cup X_1\cup… \cup X_{k-1}$
The probability for the first white ball to be drawn is:
$P(X_0)=\dfrac{m}{m+n}$
$P(X_1)=\dfrac{n}{m+n}.\dfrac{m}{m+n-1}$
This is what offered in the book, I try to write down a few more examples to get a grip of it:
$P(X_2)=\dfrac{n}{m+n}.\dfrac{n-1}{m+n-1}.\dfrac{m}{m+n-2}$
$P(X_3)=\dfrac{n}{m+n}.\dfrac{n-1}{m+n-1}.\dfrac{n-2}{m+n-2}.\dfrac{m}{m+n-3}$
The book writes:
$P(X_{k-1})=\dfrac{n(n-1)…(n-k+1)m}{(m+n)(m+n-1)…(m+n-k+1)}.$
I don't understand this part, which is a general form of the above result.
Then the author writes that:
$P(W_k)=\dfrac{m}{m+n}(1+\dfrac{n}{m+n-1}+\dfrac{n(n-1)}{(m+n-1)(m+n-2)}+…\dfrac{n(n-1)…(n-k+1)}{(m+n-1)(m+n-2)…(m+n-k+1)}$
I don't understand this part as well.
By the $(n+1)$st draw, we must have a white ball, hence $P(W_{n+1})=1$
Why is it equal 1, I don't get this part.
The last part of this example is also beyond my understanding:
$1+\dfrac{n}{m+n-1}+\dfrac{n(n-1)}{(m+n-1)(m+n-2)}+…+\dfrac{n(n-1)…2.1}{(m+n-1)(m+n-2)…(m+1)m}=\dfrac{m+n}{m}$
I don't understand this equality, how can the left side is equal to right side?
Best Answer
Your calculations for $\Pr(X_2)$ and $\Pr(X_3)$ are correct.
By definition, $\Pr(X_{k - 1})$ is the probability that $k - 1$ black balls are drawn before a white ball is drawn on the $k$th draw, which is \begin{align*} \Pr(X_{k - 1}) & = \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{n - 2}{m + n - 2} \ldots \frac{n - (k - 2)}{m + n - (k - 2)} \cdot \frac{m}{m + n - (k - 1)}\\ & = \frac{n(n - 1)(n - 2) \ldots (n - k + 2)m}{(m + n)(m + n - 1)(m + n - 2) \ldots (m + n - k + 2)(m + n - k + 1)} \end{align*} since there are $n - (j - 1)$ black balls left from which to choose on the $j$th draw, where $1 \leq j \leq k - 1$, out of $m + n - (j - 1)$ balls in total, and there are $m$ white balls from which to draw out of $m + n - (k - 1)$ balls in total on the $k$th draw.
Therefore, the book appears to have an indexing error.
Since $\Pr(W_k)$ represents the probability that a white ball is drawn by the $k$th draw, \begin{align*} \Pr(W_k) & = \Pr(X_0) + \Pr(X_1) + \Pr(X_2) + \cdots + \Pr(X_{k - 1})\\ & = \frac{m}{m + n} + \frac{n}{m + n} \cdot \frac{m}{m + n - 1} + \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{m}{m + n - 2}\\ & \qquad + \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{n - 2}{m + n - 2} \ldots \frac{n - (k - 2)}{m + n - (k - 2)} \cdot \frac{m}{m + n - (k - 1)}\\ & = \frac{m}{m + n}\left[1 + \frac{n}{m + n - 1} + \frac{n}{m + n - 1} \cdot \frac{n - 1}{m + n - 2} + \ldots \right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{n - (k - 2)}{m + n - (k - 1)}\right] \end{align*} where we have factored out an $m$ from the last term in the numerator and an $m + n$ from the first term in the denominator.
Since there are only $n$ black balls, we are guaranteed to obtain a white ball by the $(n + 1)$st draw. Since $W_{n + 1}$ is the event that we draw a white ball by the $(n + 1)$st draw, $\Pr(W_{n + 1}) = 1$.
Notice that \begin{align*} \Pr(W_{n + 1}) & = \Pr(X_0) + \Pr(X_1) + \Pr(X_2) + \cdots + \Pr(X_{k - 1}) + \Pr(X_n)\\ & = \frac{m}{m + n} + \frac{n}{m + n} \cdot \frac{m}{m + n - 1} + \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{m}{m + n - 2}\\ & \quad + \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{n - 2}{m + n - 2} \ldots \frac{n - (n - 2)}{m + n - (n - 2)} \cdot \frac{m}{m + n - (n - 1)}\\ & \qquad + \frac{n}{m + n} \cdot \frac{n - 1}{m + n - 1} \cdot \frac{n - 2}{m + n - 2} \ldots \frac{n - (n - 2)}{m + n - (n - 2)} \cdot \frac{n - (n - 1)}{m + n - (n - 1)} \cdot \frac{m}{m + n - n}\\ & = \frac{m}{m + n}\left[1 + \frac{n}{m + n - 1} + \frac{n}{m + n - 1} \cdot \frac{n - 1}{m + n - 2} + \ldots \right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{n - (n - 2)}{m + n - (n - 1)}\right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{2}{m + 1} \cdot \frac{1}{m}\right] \end{align*} Substituting $1$ for $W_{n + 1}$ yields \begin{align*} 1 & = \frac{m}{m + n}\left[1 + \frac{n}{m + n - 1} + \frac{n}{m + n - 1} \cdot \frac{n - 1}{m + n - 2} + \ldots \right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{n - (n - 2)}{m + n - (n - 1)}\right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{2}{m + 1} \cdot \frac{1}{m}\right] \end{align*} from which we conclude that \begin{align*} \frac{m + n}{m} & = \left[1 + \frac{n}{m + n - 1} + \frac{n}{m + n - 1} \cdot \frac{n - 1}{m + n - 2} + \ldots \right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{n - (n - 2)}{m + n - (n - 1)}\right.\\ & \qquad \left. + \frac{n}{m + n - 1} \cdot \frac{n - 2}{m + n - 1} \cdot \frac{n - 3}{m + n - 2} \ldots \frac{2}{m + 1} \cdot \frac{1}{m}\right] \end{align*} Having said all that, I agree with the comment posted by JMoravitz. It is also how I approach such problems.