# Card Matching: expected value of correctly predicted cards with partial feedback

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.

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$.

Let there be an ordering that you've imagined o1, o2, o3, o4, ..., o5.

E(X) = P(X1) * 1 + P(X2) * 2 + P(X3) * 3 + .... + P(X52) * 52,                                            ...................... (1)
where P(Xk) = Probability of exactly k matches.

Now P(Xk) = k / (k + 1)!, since if we take first k + 1 elements from our already pre-determined sequence:
o1, o2, o3, o4, ... , ok, ok+1

The probability that first k terms occur in order and the last k+1th term occur out of order is k / (k + 1)!

Examples:
ok+1, o1, o2, o3, o4, ... ok
o1, ok+1, o2, o3, o4, ... ok
o1, o2, ok+1, o3, o4, ... ok

Now, from (1), we clearly have E(X) = ∑151 k2 / (k + 1)! and a residual term R = 52 / 52!

Breaking down the sum easily gives ∑151 1 / (k + 1)!.

Which is approximately e - 1.

• For some basic information about writing mathematics at this site see, e.g., here, here, here and here. Commented Sep 26, 2022 at 5:37

I did it with just the defintion of expectation if someone is having trouble understanding the above with I.R.Vs.

First I rephrased the problem, imagine we have the numbers 1 to n and we want to count the expected length we get guessing 1 then 2 then 3 etc..

For n! orderings of the numbers 1-n how long is the average number of digits that are in consecutive "order" starting at 1 counting from 1 to n.

Ex for n=5:

13452 (this has 2 in "order" if we look for 1 then 2)

15243 (this has 3 in "order" if we look for 1 then 2 then 3)

23451 (this has 1 in "order" at the end)

In words think about choosing k to be in "order" as defined above then the rest go wherever. This will give use the probability we have a string $$S$$ with $$k$$ or more in order.

$$\begin{eqnarray*} P(S >= k) &=& {\binom{n}{k} \dfrac{(n-k)!}{n!}} &=& \dfrac{1}{k!} \end{eqnarray*}$$

So

$$\begin{eqnarray*} P(S = k) &=& \dfrac{1}{k!}- \dfrac{1}{k+1!} \end{eqnarray*}$$

Then lets calculate expectation

$$\begin{eqnarray*} E(S_k) &=& \sum_{k=0}^{n} k *( \dfrac{1}{k!}- \dfrac{1}{k+1!}) \end{eqnarray*}$$

Using Taylor Series and $$\frac{k}{(k+1)!} = \frac{1}{k!} - \frac{1} {(k+1)!}$$

$$\begin{eqnarray*} E(S_k) &=& e - 1 \end{eqnarray*}$$