Cards from an ordinary deck are turned face up one at a time. Compute the expected number of cards that need to be turned face up in order to obtain

(a) 2 aces;

(c) all 13 hearts.

This is a homework problem straight from a chapter on Expectation from a probability textbook. The textbook has a section on finding the expected value of a negative binomial random variable, and says $E[X] = E[X_1]+ E[X_2[ \dots + E[X_r] = \frac{r}{p}$.

(The textbook defines the negative binomial distribution as the probability that $n$ trials are required until $r$ successes occur. It is assumed that $r$ is constant and $n$, the value of the negative binomial random variable, is unbounded i.e. may go to $\infty$. $$P(X = n) = \binom{n-1}{r-1}p^r (1-p)^{n-r}\ \ \ \ \text{for}\ r \le n \lt \infty$$

The problem (a) here seems to want the expectation of a negative binomial random variable, however, the above equation for $E[X]$ assumes that $r \le n \lt \infty$, but in the case of this problem, only up to $50$ cards may actually be selected such that $2$ are aces (there are $48$ non-aces, so the next $49$th, $50$th cards must be aces). In other words, for this problem $2 \le n \le 50$.

So instead of following the textbook's equation for $E[X]$, I tried to find $E[X]$ for (a), given $r = 2, p = \frac{4}{52}$ as

$$E[X] = \sum_{n=2}^{50} n \binom{n-1}{2-1} \left(\frac{4}{52}\right)^2\left(\frac{48}{52}\right)^{n-2} \approx 19.8134 $$

If I follow the textbook, I get $E[X] = \frac{r}{p} = 2 \left(\frac{48}{52}\right)^{-1} = 26$.

Are either of these answers correct? And is problem (c) essentially the same as solving (a)?


Using the identity $$ \sum_{k=a}^{n-b}\binom{k}{a}\binom{n-k}{b}=\binom{n+1}{a+b+1}\tag{1} $$ here is how I would approach (c):

The number of arrangements which get all $13$ hearts in exactly $k$ draws is $\binom{k-1}{12}\binom{52-k}{0}$; that is, the number of arrangements, with the $k^\text{th}$ draw being a heart, to arrange the other $12$ hearts in the previous $k-1$ draws and none in the remaining $52-k$ draws. The total number of arrangements is therefore $$ \sum_{k=13}^{52}\binom{k-1}{12}\binom{52-k}{0}=\binom{52}{13}\tag{2} $$ and the expected number of draws would be $$ \begin{align} \frac1{\binom{52}{13}}\sum_{k=13}^{52}k\binom{k-1}{12}\binom{52-k}{0} &=\frac1{\binom{52}{13}}\sum_{k=13}^{52}13\binom{k}{13}\binom{52-k}{0}\\ &=\frac{13\binom{53}{14}}{\binom{52}{13}}\\ &=\frac{13\cdot53}{14}\\[12pt] &\doteq49.214\tag{3} \end{align} $$ Since André Nicolas has given a complete answer to both parts of this, I will show how to use $(1)$ to handle (a):

The number of arrangements which attains $2$ aces in exactly $k$ draws is $\binom{k-1}{1}\binom{52-k}{2}$; that is, the number of arrangements, with the $k^\text{th}$ draw an ace, to have one ace in the first $k-1$ draws and the other two aces in the remaining $52-k$ draws. The total number of arrangements is therefore $$ \sum_{k=2}^{52}\binom{k-1}{1}\binom{52-k}{2}=\binom{52}{4}\tag{4} $$ and the expected number of draws would be $$ \begin{align} \frac1{\binom{52}{4}}\sum_{k=2}^{50}k\binom{k-1}{1}\binom{52-k}{2} &=\frac1{\binom{52}{13}}\sum_{k=2}^{52}2\binom{k}{2}\binom{52-k}{2}\\ &=\frac{2\binom{53}{5}}{\binom{52}{4}}\\ &=\frac{2\cdot53}{5}\\[12pt] &=21.2\tag{5} \end{align} $$

Identity $(1)$ is proven using negative binomial coefficients in this answer. Let's give a generating function approach here. $$ \begin{align} \frac{(1+x)^{n+1}-(1+y)^{n+1}}{x-y} &=\frac{(1+x)^{n+1}-(1+y)^{n+1}}{(1+x)-(1+y)}\\ &=\sum_{k=0}^n(1+x)^k(1+y)^{n-k}\\ &=\sum_{k=0}^n\sum_{i=0}^k\binom{k}{i}x^i\sum_{j=0}^{n-k}\binom{n-k}{j}y^j\\ &=\sum_{i=0}^k\sum_{j=0}^{n-k}x^iy^j\sum_{k=0}^n\binom{k}{i}\binom{n-k}{j}\tag{6} \end{align} $$ Thus, the sum in $(1)$ is the coefficient of $x^ay^b$ in the right hand side of $(4)$. Let's compute the left hand side of $(4)$ in a different manner. $$ \begin{align} \frac{(1+x)^{n+1}-(1+y)^{n+1}}{x-y} &=\sum_{k=0}^{n+1}\binom{n+1}{k}\frac{x^k-y^k}{x-y}\\ &=\sum_{k=0}^{n+1}\binom{n+1}{k}\sum_{j=1}^kx^{j-1}y^{k-j}\tag{7} \end{align} $$ The sole occurrence of $x^ay^b$ in $(5)$ is when $j=a+1$ and $k-j=b$; that is, $k=a+b+1$. Therefore, the coefficient of $x^ay^b$ is $\binom{n+1}{a+b+1}$. Thus, combining $(6)$ and $(7)$ yields $(1)$.

  • $\begingroup$ I have seen some combinatorial identities, but not that one. Where did you find it? $\endgroup$ – NaN Dec 6 '13 at 14:27
  • 1
    $\begingroup$ @FoF: I have amended my answer with a proof and a link to another proof. $\endgroup$ – robjohn Dec 6 '13 at 17:04
  • $\begingroup$ I saw the proof but got lost on how to interpret binomial coefficients where the values are clearly negative. I posted a question about this here $\endgroup$ – NaN Dec 7 '13 at 12:32
  • 1
    $\begingroup$ @FoF: all of the binomial coefficients have positive indices here. It is only in the linked proof that negative binomial coefficients are used. This is why I added the alternate proof here, which uses only positive indices. $\endgroup$ – robjohn Dec 7 '13 at 12:38
  • $\begingroup$ while rereading your answer, I think the $\mathbb (1) \implies (2)$ could be a little clearer. Although it is clear to the reader that $n = 52$, one might not see how or why we reached $\binom{52}{13}$ (2) for $\binom{n+1}{a+b+1}$(1), and not $\binom{52+1}{12+0+1}=\binom{53}{13}$. This has to do with $\binom{k-1}{a} \ne \binom{k}{a}$ when we compare the binomial coefficients of (1, 2), correct? A line of explanation could help make the proof read smoother. I did not downvote, and maintain my upvote. $\endgroup$ – NaN Dec 11 '13 at 12:10

We solve the first problem in detail. The second is basically the same, so that solution will be very brief.

First problem: Let $X$ be the number of cards drawn until the second Ace is drawn. We find $E(X)$.

There are $4$ Aces, and $48$ non-Aces. Label the non-Aces $1,2,3,\dots, 48$.

Define random variable $Y_i$ to be $1$ if non-Ace labelled $i$ is drawn before $2$ Aces are drawn, and $Y_i=0$ otherwise.

Let $Y=Y_1+Y_2+\cdots+Y_{48}$. Then $Y$ is the number of non-Aces drawn before $2$ Aces are drawn, and therefore $$X=2+Y_1+Y_2+\cdots+Y_{48}.$$ By the linearity of expectation, we have $$E(X)=2+E(Y_1)+E(Y_2)+\cdots +E(Y_{48}).$$ It remains to find the expectations of the $Y_i$. These are all the same.

Consider the $5$ cards consisting of the $4$ Aces and non-Ace $i$. The probability that $X_i=1$ is the probability that $i$ occupies one of the first $2$ positions among the $5$ cards. This probability is $\frac{2}{5}$.

It follows that $E(Y_i)=\frac{2}{5}$ and therefore $$E(X)=2+48\cdot \frac{2}{5}=\frac{106}{5}.$$

Second problem: Let $X$ be the number of cards drawn until the $13$-th heart is drawn. Label the non-hearts $1,2,3,\dots,39$, and let $Y_i=1$ if non-heart $i$ is drawn before the $13$ hearts. Then by reasoning very similar to the one in the first problem, we have $$E(X)=13+39E(Y_i).$$ We have $E(Y_i)=\frac{13}{14}$, and therefore $E(X)=\frac{689}{14}$.

Remark: The relevant distribution is usually called the negative hypergeometric. Suppose that we have $g+b$ cards, $g$ of them good and $b$ bad. They are drawn in order without replacement. Let $X$ be the total number of cards drawn until the $r$-th good is drawn. Exactly the same reasoning as the one above can be used to find $E(X)$.

The method of indicator random variables that we used is quite powerful. There are a number of situations where it quickly yields the expectation, while working with the distribution is more difficult.

  • $\begingroup$ @AndréNicolas, after I read your answer, I thought it was reasonable (correct, I'm sure :)) and understandable. It seems to me that this problem is open to many possible approaches to the correct solution; while I can read your solution and say "ok...looks correct", I do not see why my approach did not work out. Is there a fundamental reason why this problem cannot be modeled with the negative binomial distribution, as I have attempted? $\endgroup$ – NaN Dec 7 '13 at 3:23
  • $\begingroup$ @AndréNicolas I now noticed that same labeling of random variables was used in my textbook here $\endgroup$ – NaN Dec 7 '13 at 4:18
  • $\begingroup$ The method of indicator random variables is widely useful. The first easy application is expectation of a binomial. Next is expectation of the htpergeometric. There are many other examples, such as coupon-collecting problem. About your earlier question, we cannot use negative binomial because the distribution is not negative binomial, we are sampling without replacement. $\endgroup$ – André Nicolas Dec 7 '13 at 4:19
  • $\begingroup$ @AndréNicolas, sorry, had a bad link. Please try the link now. Comment edited. $\endgroup$ – NaN Dec 7 '13 at 4:20
  • $\begingroup$ I got something the first time. Now it wants me to sign in, which I am unwilling to do (friend's computer, don't want to infect!). $\endgroup$ – André Nicolas Dec 7 '13 at 4:24

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.