# On Lonely Hearts

The Baron's most recent wager had Sir R----- pay one coin to play and involved separately shuffling the hearts from two decks of cards before turning over the topmost of each set. If the cards matched Sir R----- was to win a prize of fourteen coins from the Baron and the game would then end. If not he should have given the Baron another coin and the next pair of cards should have been overturned and the same rules followed whilst there were unturned cards remaining.

Now, it struck my fellow students and I that the simplest manner to reckon the fairness of this wager was to count, for the $$i^{th}$$ turn of the cards, both the total number of possible outcomes, $$N_i$$, and the number of winning outcomes for Sir R-----, $$M_i$$, and figure the probability of Sir R----- winning on the $$i^{th}$$ turn given that he has not already won, $$p_i$$, by dividing the latter by the former. Note that to do so correctly, we must include every possible arrangement of the remaining unseen cards. Furthermore, if we relabel the cards with their positions in the Baron's pile, then we need pay no further mind to it; a match is made if Sir R-----'s $$i^{th}$$ card is labelled $$i$$.

On turning the first card, there are trivially $$13 \times 12 \times 11 \times \dots \times 2 \times 1$$ possible outcomes, which we write with the factorial symbol as $$13!$$. The number of winning outcomes is simply $$12!$$ since the first card must be labelled $$1$$ and the remaining $$12$$ cards can take any order. So, for the first card we have
\begin{align*} N_1 &= 13!\\ M_1 &= 12!\\ p_1 &= \frac{1}{13} \end{align*}
Now when counting the number of possible outcomes for the second card, we must take into account that Sir R----- could not have made a match with the first, since in that case the game would have ended. It must therefore be the case that they number equal to those for the first card less its number of winning outcomes.
$N_2 = N_1 - M_1 = 13! - 12!$
Similarly, the number of winning outcomes for the second card is given by the number of arrangements in which Sir R-----'s second card is labelled 2 less the number in which the first card is also labelled 1. Since the cards whose positions we have not specified can have any order, the former must be 12! and the latter 11!, yielding
\begin{align*} M_2 &= 12! - 11!\\ p_2 &= \frac{M_2}{N_2} = \frac{12! - 11!}{13! - 12!} = \frac{12 - 1}{13 \times 12 - 12} \times \frac{11!}{11!} = \frac{11}{144} \end{align*}
For the third card, we can count the total number of outcomes in the same manner
$N_3 = N_2 - M_2 = (13! - 12!) - (12! - 11!) = 13! - 2 \times 12! + 11!$
To count the number of winning outcomes, we must exercise a little care however. We are only interested in permutations of cards in which neither the first is labelled 1 nor the second 2, known as a derangement of those cards and much studied by Monsieur Montmort. Indeed, I noted the parallels between this game and the problem posed by Monsieur Montmort to the Baron, but I fear he did not entirely grasp their significance.

Now if we denote the set of outcomes in which the $$i^{th}$$ card is labelled $$i$$ with $$A_i$$, then the size of the set of winning outcomes for the third card is given by
$M_3 = \left|A_3\right| - \left|\left(A_3 \cap A_2\right) \cup \left(A_3 \cap A_1\right)\right|$
where the vertical bars represent the number of elements in the set between them, $$S \cap T$$ the intersection of the sets $$S$$ and $$T$$ containing every element that is in both of them and $$S \cup T$$ their union containing every element that is in either or both of them. Now we cannot simply add the sizes of those sets to recover the size of the union since we should double count elements that are in both if we do so. We must therefore subtract the number of shared elements, yielding
$|S \cup T| = |S| + |T| - |S \cap T|$
For our set of winning outcomes this implies that
\begin{align*} M_3 &= \left|A_3\right| - \left|A_3 \cap A_2\right| - \left|A_3 \cap A_1\right| + \left|A_3 \cap A_2 \cap A_3 \cap A_1\right|\\ &= \left|A_3\right| - \left|A_3 \cap A_2\right| - \left|A_3 \cap A_1\right| + \left|A_3 \cap A_2 \cap A_1\right|\\ &= 12! - 11! - 11! + 10!\\ &= 12! - 2 \times 11! + 10! \end{align*}
and hence
$p_3 = \frac{M_3}{N_3} = \frac{12! - 2 \times 11! + 10!}{13! - 2 \times 12! + 11!} = \frac{12 \times 11 - 2 \times 11 + 1}{13 \times 12 \times 11 - 2 \times 12 \times 11 + 11} \times \frac{10!}{10!} = \frac{111}{1,463}$
Rather more fiddlesome is avoiding double counts in the number of winning outcomes for the $$i+1^{th}$$ card, given by
$M_{i+1} = \left|A_{i+1}\right| - \left|\left(A_{i+1} \cap A_i\right) \cup \left(A_{i+1} \cap A_{i-1}\right) \cup \dots \cup \left(A_{i+1} \cap A_2\right) \cup \left(A_{i+1} \cap A_1\right)\right|$
Fortunately we can greatly simplify its calculation by exploiting the principle of inclusion and exclusion which states that for sets $$S_i$$
$\left|S_1 \cup S_2 \cup \dots \cup S_n\right| = \sum_i \left|S_i\right| - \sum_{i<j} \left|S_i \cap S_j\right| + \sum_{i<j<k} \left|S_i \cap S_j \cap S_k\right| - \dots + (-1)^{n+1} \left|S_1 \cap S_2 \cap \dots \cap S_n\right|$
For the right hand side of the expression for $$M_{i+1}$$, the number of terms in each sum is equal to the number of ways in which we can pick the indices and the size of the intersections in each term is simply the factorial of the number of cards whose label has not been specified
\begin{align*} M_{i+1} &= 12! - \sum_{j=1}^i (-1)^{j+1} \times {^iC}_j \times (12-j)!\\ &= \sum_{j=0}^i (-1)^j \times {^iC}_j \times (12-j)! \end{align*}
where $$^nC_r$$ is the number of combinations of $$r$$ from $$n$$ objects, $$\frac{n!}{r!(n-r)!}$$, counting the number of ways in which we can choose them if their order is ignored.

Following similar reasoning we also have
\begin{align*} N_{i+1} &= 13! - \left|A_i \cup A_{i-1} \cup \dots \cup A_2 \cup A_1\right|\\ &= \sum_{j=0}^i (-1)^j \times {^iC}_j \times (13-j)! \end{align*}

and consequently
\begin{align*} p_{i+1} &= \frac{M_{i+1}}{N_{i+1}}\\ &= \frac{\sum_{j=0}^i (-1)^j \times {^iC}_j \times (12-j)!}{\sum_{j=0}^i (-1)^j \times {^iC}_j \times (13-j)!}\\ &= \frac{\sum_{j=0}^i (-1)^j \times {^iC}_j \times (12-j)!}{\sum_{j=0}^i (-1)^j \times {^iC}_j \times (13-j) \times (12-j)!} \times \frac{(12-i)!}{(12-i)!}\\ &= \frac{\sum_{j=0}^i (-1)^j \times {^iC}_j \times {^{12-j}P}_{i-j}}{\sum_{j=0}^i (-1)^j \times {^iC}_j \times (13-j) \times {^{12-j}P}_{i-j}} \end{align*}
where $$^nP_r$$ is the number of ways that we can choose $$r$$ from $$n$$ objects whilst noting their order, the number of permutations, $$\frac{n!}{(n-r)!}$$.

Figuring the probabilities for the first few cards, we have
\begin{align*} p_1 &= \frac{(-1)^0 \times {^0C}_0 \times {^{12}P}_0}{(-1)^0 \times {^0C}_0 \times 13 \times {^{12}P}_{0}} = \frac{1}{13}\\ p_2 &= \frac{\left((-1)^0 \times {^1C}_0 \times {^{12}P}_1\right) + \left((-1)^1 \times {^1C}_1 \times {^{11}P}_0\right)}{\left((-1)^0 \times {^1C}_0 \times 13 \times {^{12}P}_{1}\right) + \left((-1)^1 \times {^1C}_1 \times 12 \times {^{11}P}_{0}\right)} = \frac{12 - 1}{13 \times 12 - 12} = \frac{11}{144}\\ p_3 &= \frac{\left((-1)^0 \times {^2C}_0 \times {^{12}P}_2\right) + \left((-1)^1 \times {^2C}_1 \times {^{11}P}_1\right) + \left((-1)^2 \times {^2C}_2 \times {^{10}P}_0\right)}{\left((-1)^0 \times {^2C}_0 \times 13 \times {^{12}P}_2\right) + \left((-1)^1 \times {^2C}_1 \times 12 \times {^{11}P}_1\right) + \left((-1)^2 \times {^2C}_2 \times 11 \times {^{10}P}_0\right)}\\ &= \frac{12 \times 11 - 2 \times 11 + 1}{13 \times 12 \times 11 - 2 \times 12 \times 11 + 11} = \frac{111}{1,463} \end{align*}
which are reassuringly equal to the probabilities that we have reckoned thus far.
Carrying on in the same fashion we find that
\begin{align*} p_4 &= \frac{1,019}{13,520} & p_5 &= \frac{8,425}{112,509}\\ \\ p_6 &= \frac{61,959}{832,672} & p_7 &= \frac{398,959}{5,394,991}\\ \\ p_8 &= \frac{2,203,319}{29,976,192} & p_9 &= \frac{10,146,321}{138,864,365}\\ \\ p_{10} &= \frac{37,401,155}{514,872,176} & p_{11} &= \frac{103,459,471}{1,432,413,063}\\ \\ p_{12} &= \frac{190,899,411}{2,657,907,184} & p_{13} &= \frac{176,214,841}{2,467,007,773} \end{align*}
Sir R-----'s expected winnings on the turn of the last card are simply
$e_{13} = p_{13} \times 14 + (1 - p_{13}) \times -1 = p_{13} \times 15 - 1 = \frac{176,214,842}{2,467,007,773}$
For the penultimate turn we must ensure that we include these expected winnings on the last turn
$e_{12} = p_{12} \times 14 + (1 - p_{12}) \times \left(-1 + e_{13}\right) = p_{12} \times 15 + \left(1 - p_{12}\right) \times e_{13} - 1 = \frac{381,798,823}{2,657,907,184}$
We can thus proceed backwards, calculating Sir R-----'s expected winnings at each preceding turn of the card in a likewise fashion with
$e_i = p_i \times 15 + \left(1 - p_i\right) \times e_{i+1} - 1$
My fellow students and I can attest as to just how tedious this procession actually is, so I shall spare you its misery by simply reporting our results
\begin{align*} e_{13} &= \frac{176,214,842}{2,467,007,773} & e_{12} &= \frac{381,798,823}{2,657,907,184} & e_{11} &= \frac{620,756,827}{2,864,826,126}\\\\ e_{10} &= \frac{897,627,721}{3,089,233,056} & e_9 &= \frac{1,217,558,521}{3,332,744,760} & e_8 &= \frac{1,586,389,681}{3,597,143,040}\\\\ e_7 &= \frac{2,010,753,361}{3,884,393,520} & e_6 &= \frac{2,498,186,881}{4,196,666,880} & e_5 &= \frac{3,057,264,001}{4,536,362,880}\\\\ e_4 &= \frac{3,697,747,201}{4,906,137,600} & e_3 &= \frac{4,430,764,801}{5,308,934,400} & e_2 &= \frac{5,269,017,601}{5,748,019,200} \end{align*}
and finally
$e_1 = \frac{6,227,020,801}{6,227,020,800}$
Now, to figure Sir R-----'s expected winnings for the game we must finally subtract the coin that was his cost to play
$\frac{6,227,020,801}{6,227,020,800} - 1 = \frac{1}{6,227,020,800}$
Being a profit for Sir R-----, albeit a rather meagre one, I should have had no compunction in advising him to take up the Baron's wager.

Now, I could not help but notice that Sir R-----'s payoff is equal to
$\frac{1}{13!}$
This struck me as highly unlikely to be purely coincidental, so I set to calculating the expected winnings for similar games with less than all thirteen hearts and found that, for $$n$$ cards and a prize for a match of $$n+1$$ coins, they were
$\mathrm{E}_n = (-1)^{n+1} \frac{1}{n!}$
which I feel strongly suggests that there is a much easier way to reckon the outcome of this wager, although for the life of me I cannot fathom it!
$$\Box$$