1
$\begingroup$

Consider a standard deck of cards. We draw cards from the top until we get either a King or an Ace.

1.Write a lower bound for the expected value of the number of Kings drawn before the first Ace.

The solution given in this problem is 1/2.

I'm not sure how they arrive at this solution. I assumed that both Kings and Aces are equally likely to be drawn so shouldn't the # of kings being drawn before first Ace appear be $n* \frac {1}{52}$ ?

2. Find the expected value of the number of Kings drawn before the first Ace.

Here since the number of kings in a deck is 4 and there are 52 cards in total shouldn't the expected number of kings drawn before the first Ace be $n* \frac {4}{52}$ ?

$\endgroup$
2
  • 2
    $\begingroup$ What is $n$ in your answers? There is none in the statement of the exercise... The expected value of the number of Kings drawn before the first Ace is 4 times the probability that the King of Hearts is drawn before all four Aces. By symmetry this last probability is one fifth hence the answer to 2. is 4/5. (Note that Question 1. is not understandable and that the sentence "We draw cards from the top until we get either a King or an Ace" is misleading as well.) $\endgroup$
    – Did
    Jul 8, 2018 at 8:55
  • $\begingroup$ sorry, I just thought of n as an arbitrary draw number $\endgroup$
    – pino231
    Jul 8, 2018 at 15:19

3 Answers 3

2
$\begingroup$

A lower bound is any value that is certainly bellow E(X), you cold say $0$, it would be a right answer. They provided a bit less obvious answer 1/2, since there is probability of 0.5 you will find an ace first and same probability you will find a king first, so 0.5*0+0.5*1=0.5. But there may be more kings after that first so expected value is certainly above 0.5

For the expected value you just have to play with the permutations of KKKKAAAA. There is total of $8\choose 4$=70 permutations.

With all 4 kings first - 1 permutation.

With 3 kings first and then an ace - 4 permutations (KKKA+KAAA or AKAA or AAKA or AAAK =$4\choose 1$).

With 2 kings first and then an ace $5\choose 2$=10 permutations.

With 1 king followed by ace $6\choose 3$=20 permutations

So E(X)=(4*1+3*4+2*10+1*20)/70=56/70=0.8

$\endgroup$
1
$\begingroup$

The cards other than kings or aces can be ignored, since they don't affect the order of kings and aces.

Hence, we can regard the deck as a shuffled deck with only kings and aces.

Let $e(k)$ be the expected number of kings that occur before the first ace, assuming the deck has $k+4$ cards, with $k$ kings, and $4$ aces.

Our goal is to find $e(4)$.

Then we have the recursion $$ \begin{cases} e(0)=0\\[4pt] e(k)=\left({\large{\frac{k}{k+4}}}\right)\bigl(1+e(k-1)\bigr),\;\text{if}\;k > 0\\ \end{cases} $$ Claim:$\;$For all $k\ge 0$, we have $e(k)={\large{\frac{k}{5}}}$.

To prove it, proceed by induction on $k$.

For $k=0$, we have $e(0)=0={\large{\frac{0}{5}}}$, so the base case is verified.

Suppose the claim holds for some nonnegative integer $k$. \begin{align*} \text{Then}\;\; e(k+1)&=\left(\frac{k+1}{k+5}\right)\bigl(1+e(k)\bigr)\\[4pt] &=\left(\frac{k+1}{k+5}\right)\left(1+\frac{k}{5}\right)\\[4pt] &=\left(\frac{k+1}{k+5}\right)\left(\frac{k+5}{5}\right)\\[4pt] &=\frac{k+1}{5}\\[4pt] \end{align*} which completes the induction.

In particular, we have $e(4)={\large{\frac{4}{5}}}$.

$\endgroup$
1
  • 1
    $\begingroup$ I like the intuition that you pointed out that all the non Kings and Aces cards are irrelevant in this case $\endgroup$
    – pino231
    Jul 8, 2018 at 15:46
1
$\begingroup$

Part 2. For the purpose of analysis, we may pretend the deck consists only of four kings and four aces. Let $X$ be the number of kings before the first ace.

Then $P(X>0)$ is the probability that the first card is a king, so $P(X>0) = \frac{4}{8}$.

$P(X > 1)$ is the probability that the first two cards are kings, so $P(X>1) = \frac{4}{8} \cdot \frac{3}{7}$.

Similarly, we see that $P(X>2) = \frac{4}{8} \cdot \frac{3}{7} \cdot \frac{2}{6}$, and $P(X>3) = \frac{4}{8} \cdot \frac{3}{7} \cdot \frac{2}{6} \cdot \frac{1}{5}$.

So $$E(X) = P(X>0) + P(X>1)+P(X>2)+P(X>3) = 0.8$$

Here we have made use of the theorem that $$E(X) = \sum_{n=0}^{\infty} P(X>n)$$ which holds for any random variable $X$ which takes on only values in $\{0, 1, 2, 3, \dots \}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .