Expected minimum value of weird coin/card problem?

Question

I am quite boggled by the following question:

You are given a deck of cards with integers from 1 to 100 and 2 boxes labelled H and T. Flip a fair coin 100 times, and place the $i^\text{th}$ card in the box labelled H if the $i^\text{th}$ flip is heads, and likewise in the box labelled T if the flip is tails. Find the expected minimum card in the box with the $100^\text{th}$ card.

I am unclear on two fronts:

1) How do we condition on which box has the 100th card? Is that just assigning a probability of $\frac12$ or begin given the 100th card to each box, and does it even matter? (My gut says no due to symmetry, but I’m not sure how to formally tie this down.)

2) How do we find the expected minimum card? I feel like standard conditional expectation gives us the average value of the card, but not the expected minimum.

Help is greatly appreciated!

Answer 1

Let $X$ denote the minimal number of card in the box with the $100^{\text{th}}$ card. Let $A$ be the event that the $100^{\text{th}}$ flip of the coin is heads. Then for $k=1,\ldots,99$ $$ \mathbb P(X=k)=\mathbb P(A)\mathbb P(X=k\mid A)+\mathbb P(A^c)\mathbb P(X=k\mid A^c)=\frac12 P_1(k)+\frac12 P_2(k)$$ where $P_1(k)$ is the probability that the first $k-1$ cards are in box $T$ and $k^{\text{th}}$ card is in box $H$. $$ P_1(k)=\mathbb P(\underbrace{T \ldots T}_{k-1} H\mid 100^{\text{th}}=H)=\frac1{2^k}. $$ And $P_2(k)=P_1(k)$ due to the symmetry. So $$ \mathbb P(X=k)=\frac1{2^k},\quad k=1,\ldots,99. $$ For $k=100$ $$\mathbb P(X=100)=\frac12\mathbb P(\underbrace{T\ldots T}_{99}\mid 100^{\text{th}}=H)+\frac12\mathbb P(\underbrace{H\ldots H}_{99}\mid 100^{\text{th}}=T)=\frac1{2^{99}}.$$ You need to find $$ \mathbb E[X]=\sum_{k=1}^{99} k\cdot \frac1{2^k}+100\cdot \frac{1}{2^{99}}. $$ Another way is to find for $k=1,\ldots,100$ $$ \mathbb P(X\geq k) = \frac12\mathbb P(\underbrace{T\ldots T}_{k-1}\mid 100^{\text{th}}=H)+\frac12\mathbb P(\underbrace{H\ldots H}_{k-1}\mid 100^{\text{th}}=T)=\frac1{2^{k-1}} $$ and then $$ \mathbb E[X]=\sum_{k=1}^{100}\mathbb P(X\geq k)=\sum_{k=1}^{100} \frac1{2^{k-1}} = \sum_{k=0}^{99} \frac1{2^k} = 2-\frac{1}{2^{99}}. $$