A standard deck of cards is shuffled, and the cards are dealt face down one by one. Just after each card is dealt, you name any card (as your prediction). Let $X$ be the number of cards you predict correctly.
(b) Now suppose that you get partial feedback: after each prediction, you are told
immediately whether or not it is right (but without the card being revealed). Suppose you use the following strategy: keep saying a specific card’s name until you hear that you are correct. Then keep saying a different card’s name until you hear that you are correct (if ever). Continue in this way, naming the same card over and over again until you are correct and then switching to a new card, until the deck runs out. Find the expected value of $X$, and show that it is very close to $e − 1$.
Can anybody give me a hint what the indicator random variable should be? If I let it refer to the $j^{th}$ card in the deck, it's too complicated and I don't know how to compute its expected value. If I let it refer to the $j^{th}$ card that I say, I don't know if I will ever say it.
Best Answer
The indicator variable is, as you suspected, for the event that a given card is guessed correctly. I'll call it $X_i$ for convenience:
For $i=1,\ldots,52$, let
$$X_i = \begin{cases} 1 & \qquad\text{if card $i$ is guessed correctly} \\ 0 & \qquad\text{otherwise} \end{cases}$$
Then, using linearity of expectation,
$$E(X) = E\left(\sum_{i=1}^{52}{X_i}\right) = \sum_{i=1}^{52}{E\left(X_i\right)} = \sum_{i=1}^{52}{P\left(X_i=1\right)}.$$
We seek $P(X_i = 1)$ now. If we denote by Y (N) a correct (incorrect) guess for any particular card then the event "$X_i=1$" can be represented by the set of all possible strings of length $i$ of Ys and Ns ending in Y.
Take such a string and consider its substrings of maximally consecutive Ns and the following Y. For example, YNNYNNNNYYNY has $5$ such substrings (because it has $5$ Ys) of lengths $1,3,5,1,2$. We can calculate the probability of this outcome, given the rules of the game, to be:
$$\frac{1}{52}\;\cdot\;\frac{50}{51}\cdot\frac{49}{50}\cdot\frac{1}{49}\;\cdot\;\frac{49}{50}\cdot\frac{48}{49}\cdot\frac{47}{48}\cdot\frac{46}{47}\cdot\frac{1}{46}\;\cdot\;\frac{1}{49}\;\cdot\;\frac{47}{48}\cdot\frac{1}{47}\;\; = \;\;\frac{1}{52}\cdot\frac{1}{51}\cdot\frac{1}{50}\cdot\frac{1}{49}\cdot\frac{1}{48}$$
$$\\$$ Hopefully, it's not hard to convince yourself of the pattern here that the probability of any given Y-N string is $\dfrac{(52-k)!}{52!}$ where $k$ is the number of Ys in the string.
Now, of all Y-N strings of length $i$ ending in Y, there are $\binom{i-1}{k-1}$ strings with exactly $k$ Ys since we need to choose $k-1$ positions from $i-1$ possibilities for all Ys but the last. And since this $k$ can range from $1$ to $i$, we have,
\begin{eqnarray*} P(X_i = 1) &=& \sum_{k=1}^{i}{\binom{i-1}{k-1} \dfrac{(52-k)!}{52!}}. \end{eqnarray*}
So, \begin{eqnarray*} E(X) &=& \sum_{i=1}^{52}{\left[ \sum_{k=1}^{i}{\binom{i-1}{k-1} \dfrac{(52-k)!}{52!}} \right]} \\ && \\ &=& \sum_{k=1}^{52}{\left[ \dfrac{(52-k)!}{52!} \sum_{i=k}^{52}{\binom{i-1}{k-1}} \right]} \qquad\text{(swapping the order of summation)} \\ && \\ &=& \sum_{k=1}^{52}{\left[ \dfrac{(52-k)!}{52!} \binom{52}{k} \right]} \qquad\text{(using identity $\sum\limits_{r=p}^{q}{\binom{r}{p}} = \binom{q+1}{p+1}$)} \\ && \\ &=& \sum_{k=1}^{52}{\dfrac{1}{k!}} \\ && \\ \end{eqnarray*}
Note now the Taylor expansion: $\;\;e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$.
So, $\;e-1 \;=\; \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots\; = \;\sum\limits_{k=1}^{\infty}{\frac{1}{k!}}$.
We can see $E(X)$ is a partial sum of this series and is extremely close to $e-1$.