For practice, I decided to invent a variation on the problem of the expected number of cards to be drawn until the first ace is found. I would appreciate some feedback and clarification on certain details of my solution, which I describe at the end.
Problem: Given a deck of $52$ standard playing cards, what is the expected value of the highest card seen before drawing the first ace? (Where we set $J = 11, Q = 12, K = 13$, and we say that the value is $0$ if the first card is an ace.)
Solution: Let $H$ be the random variable corresponding to the value of the highest card. We note that the four aces divide the deck into five "boxes". Then, we may observe that:
$$\mathbb{P}(H \le n) = \mathbb{P}( \text{no card of value >} n \text{ is before the first } A )$$
For brevity, I will write this as $\mathbb{P}(S_n)$. We can imagine any permutation of the deck (ignoring permutation of the aces) as inserting cards into the gaps in between previously placed cards (including the aces).
Then, by considering this framing:
$$\mathbb{P}(S_n) = \prod_{k=0}^{4(13-n)-1} \mathbb{P}(\text{highest } (k+1) \text{ cards placed after } A \; | \text{ highest } k \text{ cards placed after } A)$$
$$ = \prod_{k=0}^{4(13-n)-1} \frac{4+k}{5+k} = \frac{4}{4(14-n)} = \frac{1}{14-n}$$
Then, noting that $\mathbb{P}(H = n) = \mathbb{P}(S_n) – \mathbb{P}(S_{n-1})$,
$$\mathbb{E}[H] = \sum_{n=2}^{13} n \bigg(\frac{1}{14-n} – \frac{1}{15-n}\bigg) \approx 10.74$$
Questions
- Why is the probability space above is equivalent to the uniform distribution on all shuffled decks? It seems obvious, but is there a way to justify it more rigorously?
- Why can we ignore the order of the cards when we insert them in the way described above?
The second question in particular may seem inane, but it's still quite difficult for me to determine if and when it's necessary to account for permutations, and I would appreciate an intuitive explanation if there is one.
Best Answer
I am not sure how to answer your second question, but my answer to your first question might be sufficient.
For Question 1, it seems to me that you are asking how to derive the equation $$ \mathbb P(\text{highest $k+1$ cards after $1^\text{st}$ A}\mid \text{highest $k$ cards after $1^\text{st}$ A})=\frac{4+k}{5+k}, $$ directly from the fact that all $52!$ orderings of the deck are equally likely.
Let $E_k$ be the event that the highest $k$ cards come after the first ace. Let $S_k$ be the set of $4+k$ cards consisting of the first $k$ high cards and the four aces. Using the Theorem below, all of the $(4+k)!$ orderings of the cards in $S_k$ that result when you delete the cards not in $S_k$ are equally likely, so each must occur with probability $1/(4+k)!$. Of these orderings, there are exactly $4\cdot (4+k-1)!$ orderings where the first cards is an ace (four choices for the first ace, $(4+k-1)!$ ways to arrange the remaining cards). Therefore, the probability of $E_k$ is $$ 4\cdot (4+k-1)!\times \frac{1}{(4+k)!}=\frac{4}{4+k} $$ You then immediately conclude that $$ P(E_{k+1}\mid E_k)=\frac{4/(5+k)}{4/(4+k)}=\frac{4+k}{5+k}. $$
Theorem: Let $S$ be a nonempty subset of $\{1,\dots,n\}$. When you shuffle a deck of $n$ cards, and delete every card in the ordering which is not a member of $S$, then every permutation of the cards in $S$ is equally likely.
Proof: Repeatedly apply the Lemma.
Lemma: Let $\mathbb U_n$ be the uniform distribution on all $n!$ ways to shuffle a deck of $n$ cards, numbered $1$ to $n$.
Let $\mathbb U_n'$ be the distribution obtained by shuffling a deck of $n+1$ cards numbered $1$ to $n+1$, and then deleting card number $n+1$.
Then $\mathbb U_n=\mathbb U_n'$.
Proof: Let $\pi$ be a particular ordering of the $n$ cards. The probability of $\pi$ with respect to $\mathbb U_n$ is $1/n!$, so we just need to show the the probability of $\pi$ with respect to $\mathbb U_n'$ is also $1/n!$. If $\pi=(\pi_1,\pi_2,\dots,\pi_n)$, there are exactly $n+1$ permutations of the deck of $n+1$ cards which will become $\pi$ when $n+1$ is deleted. Namely, they are $$ (n+1,\pi_1,\dots,\pi_n)\\ (\pi_1,n+1,\dots,\pi_n)\\ \vdots\\ (\pi_1,\dots,\pi_n,n+1)\\ $$ When you uniformly shuffle an $(n+1)$ card deck, the probability of each of these is $1/(n+1)!$. Therefore, the probability $\pi$ occurring in the $\mathbb U_n'$ distribution is $(n+1)/(n+1)!=1/n!$. $\square$