One account could look at the expected value of the number of useful cards you'll get on this turn. Drawing the face-up wild it's clear that you'll always get one useful card (assuming you're still going to build something). But what if you draw off the top? You might get something good, you might not. Moreover, since you'll draw two cards there's even a middling outcome. For simplicity, let's consider cards to be either useful or useless for you. Thus, you could end up better or worse than drawing the face-up wild. The probability of each case depending on how many cards are useful to you. We'll assume that $c$ colors are useful to you. For simplicity, let's also assume that at least two cards of any useful color are useful. We've certainly put a lot of caveats and assumptions in, which is often necessary to get a first clean result.
Now let's look at the composition of the deck. In Ticket to Ride there are 110 cards: 12 of each of 8 colors plus 14 locomotives (wilds). (Most versions have this deck composition, but the Märklin edition is different.) In reality, you'll know a lot of information about cards in your hand, other cards available to draw, cards in the discard pile, maybe even some you remember that are in other players' hands. However, we're going to look at the general case where almost none of that is taken into account. This averages our result across all possibilities. Given the fact that the deck has over 100 cards and we're drawing only two, these effects don't often have large impacts. The number of useful cards, $n$, is 14 cards, which are always useful (wilds), plus 12 for each useful suit.
\begin{align}
n = 12 \cdot c + 14
\end{align}
We can simplify the answer by approximating the probabilities of the card draws as independent. Thus, for each of the two cards drawn, the probability that it's useful is approximately,
\begin{align}
P(\text{useful}) &= \frac{n}{110} \\
&= \frac{12\cdot c + 14}{110}
\end{align}
Let's consider the scale of the error some of our assumptions and approximations are introducing. We're ignoring the five cards face up and the first card drawn when considering the second. Thus, the true probability can fall within the following range.
\begin{align}
\frac{n-6}{110-6} \leq p \leq \frac{n+6}{110-6}
\end{align}
That's actually a bit loose. We just tacitly assumed that these six cards could be either useful or not. However, we know that's not true. Specifically, we know that of the face-up cards, the only useful ones are wild cards, of which there can be at most two (given the rules about clearing the display for three). Given the choice we're making, we know there's at least one face-up wild card. Taking this into account, we can update our approximate probability assuming one face-up wild card. We know five of the 110 cards, and that one of them is useful.
\begin{align}
P(\text{useful}) &= \frac{n-1}{110-5} \\
&= \frac{12\cdot c + 13}{105}
\end{align}
Note that we're not assuming that 105 cards are in the draw pile. Instead, we're saying that we don't know anything about where any of them are. If some are in the discard pile and some are in other players' hand, but we don't know what cards they are, the probability is the same. Taking this into account, we can see the approximation error from assuming that the card draw probabilities are independent is small. The probability of the second card given the first would be one of the following two.
\begin{align}
P(\text{second useful} | \text{first useful}) &= \frac{12\cdot c + 13 -1 }{105 -1} \\
&= \frac{12 \cdot c + 12}{104} \\
P(\text{second useful} | \text{first useless}) &= \frac{12\cdot c + 13 + 1 }{105 -1} \\
&= \frac{12 \cdot c + 14}{104}
\end{align}
From we these we can find the approximation errors.
\begin{align}
\epsilon_1 &= P(\text{useful}) - P(\text{second useful} | \text{first useful}) \\
&= \frac{12\cdot c + 13}{105} - \frac{12 \cdot c + 12}{104} \\
&= \frac{ 104 \cdot (12 c + 13) - 105 \cdot (12c + 12)}{104 \cdot 104} \\
&= \frac{ -12 c + 92}{10920} \\
&= \frac{ -3 c + 23}{2730} \\
&\approx -0.0011c + 0.0084
\end{align}
Since the number of useful colors can range from 1 to 7, this first error can range from about 0.0007 to 0.0073, less than 1% in either case. Similarly for the other case.
\begin{align}
\epsilon_2 &= P(\text{useful}) - P(\text{second useful} | \text{first useless}) \\
&= \frac{12\cdot c + 13}{105} - \frac{12 \cdot c + 13}{104} \\
&= \frac{ 104 \cdot (12 c + 13) - 105 \cdot (12c + 13)}{104 \cdot 104} \\
&= \frac{ -12 c -13}{10920} \\
&\approx -0.0023c - 0.0012
\end{align}
Here the error can be somewhat larger in magnitude, ranging from $-0.012$ to $-0.0089$, but still less than 1%.
I go through this exercise to make clear that we can make simplifications like this. I've probably used more words justifying it than I would have taking the full probabilities into consideration. To quickly check or bound the error for yourself is much faster.
Knowing the probability that each draw is useful, we can look at the distribution of the number of useful cards when drawing from the top here. This is another binomial distribution, although with two draws it's pretty transparent. If the number of useful cards we draw is the random variable $U$, then we can express the probabilities as follows.
\begin{align}
P(U = 0) & = \left ( 1 - P(\text{useful}) \right ) ^2 \\
&= \left ( 1 - \frac{12 \cdot c + 13}{105} \right ) ^2 \\
&= \left ( \frac{104 - (12c + 13)}{105} \right ) ^2 \\
&= \left ( \frac{92 - 12c}{105} \right ) ^2 \\
P(U = 1) & = 2 \cdot P(\text{useful}) \cdot \left ( 1 - P(\text{useful}) \right ) \\
&= 2 \cdot \frac{12 \cdot c + 13}{105} \cdot \left ( 1 - \frac{12 \cdot c + 13}{105} \right ) \\
&= 2 \cdot \frac{12 \cdot c + 13}{105} \cdot \frac{92 - 12c}{105} \\
P(U = 2) &= P(\text{useful}) ^2 \\
& = \left ( \frac{12 \cdot c + 13}{105} \right ) ^2
\end{align}
Each of these are plotted as a function of the number of useful colors in Fig. 1. As there are three possibilities, it's not necessarily clear what we should make of this. All three probabilities are second-order functions of $c$, which we can see in their parabolic shape. Two alternative ways are the probability of getting one or more useful card and the expected value of the number of useful cards, respectively.
 |
| Figure 1: Probabilities when top-decking in Ticket to Ride |
The probability of getting one or more card is the sum of the probabilities of getting one and two cards.
\begin{align}
P(U \geq 1) &= P(U = 1) + P(U = 2) \\
&= 2 \cdot \frac{12 \cdot c + 13}{105} \cdot \frac{92 - 12c}{105} + \left ( \frac{12 \cdot c + 13}{105} \right ) ^2 \\
&= 2\cdot \frac{-144c^2+948c +1196}{105^2} + \frac{144c^2+312c+169}{105^2} \\
&= \frac{-288c^2+1896c +2392 + 144c^2+312c+169}{105^2} \\
&= \frac{-144c^2+2208c +2561}{105^2}
\end{align}
This function is also plotted in Fig. 1. This indicates that when two or more colors are useful, you're more likely than not to get at least one useful card. On the other hand, it's still quite likely that you'll get nothing useful.
 |
| Figure 2: Expected useful cards when top-decking in Ticket to Ride |
Recall the expected value is the weighted average of a random variable, and given here by,
\begin{align}
\mathbb{E} U = \sum_u u \cdot P(U=u).
\end{align}
This ends up being the sum of just the two possible non-zero terms.
\begin{align}
\mathbb{E} U &= 1 \cdot P(U = 1) + 2 \cdot P(U = 2) \\
&=2 \cdot \frac{12 \cdot c + 13}{105} \cdot \frac{92 - 12c}{105} + 2 \cdot \left ( \frac{12 \cdot c + 13}{105} \right ) ^2 \\
&= 2\cdot \frac{-144c^2+948c +1196}{105^2} + 2\cdot\frac{144c^2+312c+169}{105^2} \\
&=2\cdot\frac{1260c+1365}{105^2} \\
&=2\cdot\frac{12c+13}{105}
\end{align}
Alternatively, we can do the algebra at a higher level of abstraction, where we're less prone to arithmetic mistakes.
\begin{align}
&= 2 \cdot P(\text{useful}) \cdot \left ( 1 - P(\text{useful}) \right ) + 2 \cdot P(\text{useful}) ^2 \\
&= 2 \cdot P(\text{useful}) - \require{cancel}\cancel{2 \cdot P(\text{useful}) \cdot P(\text{useful})} + \cancel{2 \cdot P(\text{useful})^2} \\
&= 2 \cdot \frac{12 \cdot c + 13}{105}\\
&= \frac{24 \cdot c + 26}{105}\\
&\approx 0.23 c + 0.25
\end{align}
We see that the quadratic terms canceled out and we're left with a linear equation, as shown in Fig. 2. This makes sense. Given that we approximated the two draws as independent, the expected value of the number of useful cards when drawing two cards should be twice that as when drawing one card. Expectation is linear. The expected value for a single draw, $U_1$, should be proportional to the number of useful cards available in the deck.
\begin{align}
\mathbb{E} U_1 &= 0 \cdot P(U_1 = 0) + 1 \cdot P(U_1 = 1) \\
&= P(U_1 = 1) \\
&= P(\text{useful}) \\
&= \frac{12\cdot c + 13}{105} \\
&\approx 0.11 c + 0.12
\end{align}
According to the plot, when four or more colors are useful we expect to get more than one useful card. Looking at the earlier result, we see that there's still a pretty substantial chance that you'll get nothing useful, $P(\text{0 useful cards} | c = 4) \approx 0.2$. Which is the correct way to think about it? They're both useful. The expected value essentially tells you what you'd get on average if you repeated this an infinite number of times. This is known from the strong law of large number, which states that the sample average converges almost surely to the mean as the sample size goes to infinity. Here almost surely has the specific meaning that it occurs with probability 1. Note that this is distinct from always happening and is perhaps best understood with continuous-valued random variables which tend not to come up for us here. A nice property is that it takes into account the benefit of sometimes getting two useful cards. So as a general strategy, it makes sense to look at the expected value.
However, using the expected value breaks down in two ways here. First, it violates the approximating assumption that the card draws are independent. That's a reasonable approximation for two cards, but becomes less so as more cards are drawn. So our approximate expected value is really only the average of a single draw across many separate games. Second, the number of times that this comes up in a game isn't that large. For many values of $c$, the probabilities of getting either no useful cards and two useful cards are both substantial. Thus, you'd expect to see scenarios where you come up empty-handed and others where you do much better drawing from the top. On the other hand, drawing the wild card is more reliable. It's the low variance play.
No comments:
Post a Comment