Thursday, April 9, 2020

When will High Society end?

In High Society, there are 16 cards that could be auctioned off, but the game ends as soon as the fourth red card is drawn (without auctioning it). When will the game end?

Well, we know that there will be at least 3 auctions (if the red cards are the first four cards) and at most 15 auctions (if the last card is a red card). So this boils down to which position is the last red is in. There will be a number of auctions equal to one less than it's position. That is, if the fourth red card is the 10th card of the deck, there will be 9 auctions.

Symmetry gives a convenient way to analyze this. Instead of looking at the position of the fourth red card from the top, we can instead look at the position of the first red card from the bottom. They are one and the same, since there are exactly four red cards. For simplicity, let's just consider red cards and non-red cards. All the cards below the last red card are necessarily non-red. Let's call $X$ the position of the last red card counting from the top of the deck, and $Y$ the position of the first red card counting from the bottom. Because there are 16 cards, and these must describe the same position, we can see that $Y$ must be inversely proportional to $X$. When $X=16$, $Y=1$, thus,
Y = 17 - X.
If we considered shuffling up the deck and constructing it from the bottom, we can compute the probability that the bottom $Y-1$ cards are non-red and that the $Y$-th card is red. Four red cards out of 16 means that there are 12 non-red cards. Thus the probability of the first card being non-red is $12/16$. For putting the next card in, there is one less card total, and one less non-red card in particular. Thus, the probability of the second card being non-red is $11/15$, given that the first was non-red. Inductively, we can see that the probability that the $n$-th card is non-red, given that all the previous cards were also non-red is,
P(n \text{ non-red}|\text{all previous non-red}) = \frac{13-n}{17-n}.
Note, by $n$ non-red, I really mean that and all previous are non-red. So I suppose I should go through and change "all previous non-red" to "$n-1$ non-red".

Using another layer of induction, we can chain these together, finding that the probability that the $n$-th card is non-red is equal to the product of these conditional probabilities. Recall that $P(A) = P(A|B) \cdot P(B)$. In this case, this means,
P(n \text{ non-red}) = P(n \text{ non-red}|\text{all previous non-red}) \cdot P(\text{all previous non-red}).
Now, we already stated the probability for the first card, which is a special case not depending on previous probabilities. We can thus build a non-recurive equation based on this.
P(1 \text{ non-red}) = \frac{12}{16}
This matches the conditional probability above, of $\frac{13-n}{17-n}$ for $n=1$.
P(n \text{ non-red}) &= \prod_{i=1}^nP(i \, \text{non-red}|\text{all previous non-red}) \\
P(n \text{ non-red}) &= \prod_{i=1}^n\frac{13-i}{17-i} \\
P(n \text{ non-red}) &= \frac{12 \cdot 11 \cdot 10 \cdot \ldots \cdot (13-n)}{16 \cdot 15 \cdot 14 \cdot \ldots \cdot (17-n)}
Then the probability that the $Y$-th card is red, given that the cards below it are all non-red is equal to 4 divided by the number of cards remaining. That is,
P(Y \text{ red} | \text{all previous non-red}) = \frac{4}{17 - Y}.
Putting this all together, we get,
P(Y \text{ red}) &= P(Y \text{ red}|\text{all previous non-red}) \cdot P(Y-1 \text{ non-red}) \\
P(Y \text{ red}) &= \frac{4}{17-Y} \cdot \frac{12 \cdot 11 \cdot 10 \cdot \ldots \cdot (13-(Y-1))}{16 \cdot 15 \cdot 14 \cdot \ldots \cdot (17-(Y-1))}
Recall that $Y = 17-X$, so
P(X \text{ last red}) &= \frac{4}{X} \cdot \frac{12 \cdot 11 \cdot 10 \cdot \ldots \cdot (13-((17-X)-1))}{16 \cdot 15 \cdot 14 \cdot \ldots \cdot (17-((17-X)-1))} \\
P(X \text{ last red}) &= \frac{4}{X} \cdot \frac{12 \cdot 11 \cdot 10 \cdot \ldots \cdot (X-3)}{16 \cdot 15 \cdot 14 \cdot \ldots \cdot (X+1)} \\
P(X \text{ last red}) &= \frac{4 \cdot 12 \cdot 11 \cdot 10 \cdot \ldots \cdot (X-3)}{16 \cdot 15 \cdot 14 \cdot \ldots \cdot X} \\
P(X \text{ last red}) &= \frac{4 \cdot 12! / (X-4)!}{16! / (X-1)!}\\
P(X \text{ last red}) &= \frac{4 \cdot 12! \cdot (X-1)!}{16! \cdot (X-4)!}\\
P(X \text{ last red}) &= \frac{4 \cdot (X-1)!}{16 \cdot 15 \cdot 14 \cdot 13 \cdot (X-4)!}\\
P(X \text{ last red}) &= \frac{(X-1)!}{4 \cdot 15 \cdot 14 \cdot 13 \cdot (X-4)!}\\
To get the number of auctions, $N$, we need subtract one from the position of the last red card $X$.
N &= X-1 \\
P(N = n) &= P(n \text{ last red}) \\
P(N = n) &= \frac{n!}{4 \cdot 15 \cdot 14 \cdot 13 \cdot (n-3)!}\\

This is plotted below. It's not necessarily apparent from the equation, but this is a rapidly increasing function. $P(16\text{ last red}) = P(15\text{ auctions}) = 0.25$. It's monotonically increasing. The end-point is a good check that we haven't made simple errors. The probability that the first card from the bottom is red is $4/16=0.25$, as there are four red cards out of a total of sixteen, matching out equation above and plot below. The probability of s short game is very small; $P(3\text{ auctions}) \approx 0.00055$. Does this also match expectation? For a game to have three auctions, the first four cards must be red. The probability of which is,
P(\text{first four red}) &= \frac{4}{16} \cdot \frac{3}{15} \cdot \frac{2}{14} \cdot \frac{1}{13} \\
P(\text{first four red}) & \approx 0.00054945. \\
That looks like the same number, but is it actually equal? If we evaluate $P(N = 3)$, we find that they are.
P(N = 3) &= \frac{3!}{4 \cdot 15 \cdot 14 \cdot 13 \cdot (3-3)!} \\
P(N = 3) &= \frac{3\cdot 2 \cdot 1}{4 \cdot 15 \cdot 14 \cdot 13 \cdot (0)!} \\
P(N = 3) &= \frac{4 \cdot 3\cdot 2 \cdot 1}{16 \cdot 15 \cdot 14 \cdot 13 \cdot 1} \\
P(N = 3) &= \frac{4 \cdot 3\cdot 2 \cdot 1}{16 \cdot 15 \cdot 14 \cdot 13} \\
P(N = 3) &= P(\text{first four red}) \\
Obviously these have to be equal, as they are equivalent, but they confirm that we haven't made a mistake in the algebra or something.

High Society Game Length

\text{# Auctions} & \text{Approximate Probability} \\ \hline
3 & 0.00054945 \\
4 & 0.0021978 \\
5 & 0.00549451 \\
6 & 0.01098901 \\
7 & 0.01923077 \\
8 & 0.03076923 \\
9 & 0.04615385 \\
10 & 0.06593407 \\
11 & 0.09065934 \\
12 & 0.12087912 \\
13 & 0.15714286 \\
14 & 0.2 \\
15 & 0.25
While not necessarily apparent from the equation at first glance, we see from the plot that the probabilities increase rapidly over the valid range of game lengths. It even looks somewhat exponential. But is it? It's certainly not linear. By recalling the earlier equation,
P(\text{bottom } n \text{ non-red}|\text{all previous non-red}) = \frac{13-n}{17-n},
we can see that it is not exponential. That is, there is not a constant multiplicative relationship between the probabilities of different game lengths. However, it is a slow-changing constant for longer game-lengths.

Hat tip to Ludology episode 155, from which I got the idea to analyze this game.

No comments:

Post a Comment