# An elementary statistics problem from Hearthstone

In Hearthstone, a popular online card game, there is a minion called C’Thun which deals damage equal to its attack value, one damage at a time. This prompted a popular streamer named Trump (not the insufferable presidential candidate) to ask the following question once on his channel: when playing a C’Thun with 12 attack (hence, it will deal 12 damage one at a time), what is the probability that it will kill a 6 health minion when played, with no other minions on the board?

To those who don’t know how Hearthstone works, one can think of the question as follows: suppose you flip a coin 12 times in a row. Each time you flip the coin, you record down whether you got heads or tails. As long as you have fewer than 6 heads, the coin is fair and you have equal probability of getting heads or tails on your next flip. However, as soon as you hit 6 heads, then the coin becomes unfair and you can only get tails after. The question that Trump (real name Jeffrey Shih) asks is then equivalent to “what is the probability that you get 6 heads”.

To calculate this probability, we can ask the reverse question: what is the probability that we don’t get six heads? If we don’t get 6 heads, then the probability distribution is the same as if we always had a fair coin, and so the probability is the same. The probability of getting at most five heads when flipping a fair coin 12 times is given by

$\displaystyle 2^{-12} \sum_{k=0}^5 \binom{12}{k}.$

The well-known binomial theorem tells us that

$\displaystyle 2^{-12} \sum_{k=0}^{12} \binom{12}{k} = 1.$

This shows that the probability of getting at most 5 heads is equal to

$\displaystyle \frac{1}{2} - 2^{-13} \binom{12}{6} = \frac{793}{2048}.$

Therefore, the probability of getting 6 heads in the original game is equal to

$\displaystyle 1 - \frac{793}{2048} = \frac{1255}{2048},$

or roughly $61.28\%$. Thus it is far more likely that C’Thun will kill a 6 health minion with only 12 damage than too many shots going to face.

# Some statistics for hearthstone

This took a bit longer than I would care to admit, but I have finally computed the expected gain of stars per game. The answer depends a little bit on information available and interpretation.

Let $p$ denote the probability of you winning a game, which is considered to be constant. If you are on a win streak, meaning you’ve won the previous two games, then the expected winning of your next game is $2p - 1(1-p) = 3p-1$. The probability that you’ve won your previous two games is $p^2$, so this case contributes $p^2(3p-1)$ to the total expected value. Otherwise, the expected winning is $p - (1-p) = 2p-1$. The probability of this is $1 - p^2$, so the contribution for this case is $(1-p^2)(2p-1)$. Summing, we obtain that the total expected value of the gain of stars is

$3p^3 - p^2 + 2p - 1 - 2p^3 + p^2 = p^3 + 2p - 1.$

Thus, if you win half the time (so that $p = 1/2$), you should expect to gain roughly one star every 8 games or so.

Another Hearthstone related problem, which I worked out with my officemate, is to ask what is the probability of you getting the card you need on turn 1 assuming you are going first and that you are willing to discard all other cards in your initial draw in order to get the card that you want. First, the probability that the card you need will appear in the initial draw of three cards is

$\displaystyle \frac{\binom{2}{1} \binom{28}{2} + \binom{2}{2} \binom{28}{1}}{\binom{30}{3}}.$

If you did not get either copy of the card that you need, then you may discard all three cards and try again, knowing that the three cards you tossed cannot come back. In this case, the probability of you getting the card you need is the product of the probability of you not getting the card you want in the initial draw and the probability of getting at least one copy of the card that you need in the second draw.

$\displaystyle \frac{\binom{28}{3}}{\binom{30}{3}} \cdot \frac{\binom{2}{1} \binom{25}{2} + \binom{2}{2} \binom{25}{1}}{\binom{27}{3}} .$

Adding these, we get some pretty neat cancelations and end up with the simple expression of $p = 1/5$.

However, we have not yet accounted for the random card that you top deck after your initial draw on turn 1. The only remaining case that needs to be considered is when you failed to get the card you need after tossing all of your cards on the initial draw. In this case, the probability of getting the card you need is

$\displaystyle \frac{\binom{27}{3}}{\binom{30}{3}} \cdot \frac{\binom{25}{3}}{\binom{27}{3}} \cdot \frac{2}{27}$

which is about 0.041963. Adding, the total probability is about $0.241963$, or slightly less than one in four.