Intuitively, why does it make sense to go second in dice game to maximize chance of winning

combinatoricsdicegamblingmarkov chainsprobability

Here's a question from a probability book I am working through:

Let's add more fun to the triplet game. Instead of fixed triplets for the two players, the new game allows both to choose their own triplets. Player $1$ chooses a triplet first and announces it; then player $2$ chooses a different triplet. The players toss the coins until one of the two triplet sequences appears. The player whose chosen triplet appears first wins the game.

If both player $1$ and player $2$ are perfectly rational and both want to maximize their probability of winning, would you go first (as player $1$)? If you go second, what is your probability of winning?

There's $8$ possible triplets sequences for each player:

HHH, HHT, HTH, HTT, THH, THT, TTH, TTT

The players can't have the same triplet, hence there being $64 – 8 = 56$ probability outcomes to calculate for player $2$ winning. After spending half an hour tediously calculating all $56$, it turns out that player $2$ can always choose a triplet, dependent on what player $1$ picked, as to win with probability at least ${2\over3}$. However, I am wondering if there is an intuitive way to see that without tediously doing all $56$ computations.

Or if seeing that player $2$ can always win with probability at least ${2\over3}$ is too much to ask for of an intuitive heuristic, how can we see that player $2$ can always win with probability at least ${1\over2}$?

Edit: Since the problem statement is referring to earlier parts of the problem, I am reproducing those problem statements here as well:

Part A. If you keep on tossing a fair coin, what is the expected number of tosses such hat you have $HHH$ (heads heads heads) in a row? What is the expected number of tosses to have $THH$ (tails heads heads) in a row?

Part B. Keep flipping a fair coin until either $HHH$ or $THH$ occurs in the sequence. What is the probability that you get an $HHH$ subsequence before $THH$?

Best Answer

Edit:* Yes, the probability can be computed for a general pattern. See below the figure.

Intuitive explanation of winning edge:

Given the other player picks any pattern, say HHH, the player who goes second can pick a pattern which has the beginning of the opponents' pattern as a suffix.

So the second player would fix THH in this case. This means that except for the case that HHH occurs as the first 3 tosses, he can win.

More generally, given an arbitrary pattern, say $X_1,\ldots,X_n$ pick a pattern of the form $A, X_1,\ldots,X_{n-1}.$

By doing this, the first player is forcing the other player to typically win at a depth one more than herself, except if their pattern occurs in the beginning.

Here is a pictorial illustration of another example showing the depth of winning states. The first player (opponent) picks HTH and the second player (you) pick HHT.

There is a neat way of computing the winning probability in this Penney-Ante game which was first mentioned by John H. Conway.

Given two $q-$ary words (from a finite alphabet of $q$ letters) $X=(x_1,\ldots,x_n)$ and $Y=(y_1,\ldots,y_m),$ define the correlation of $X$ and $Y$ as $$ C[X,Y;z]=\sum_{i=0}^{n-1} f(n-i) z^i, $$ where $f(i)=1$ if and only if the partial word $(x_i,\ldots,x_n)$ is a prefix of the word $(y_1,\ldots,y_m),$ otherwise $f(i)=0.$ In general, $[X,Y]\neq [Y,X].$ Then the odds that word $Y$ beats word $X$ in this game is given by the expression $$ \frac{C[X,X;q]-C[X,Y;q]}{C[Y,Y;q]-C[Y,X;q]}, $$ though the proof was not given by Conway and was supplied much later by Guibas and Odlyzko.

Note that if the odds are $o$ the probability of winning is $$o/(1+o).$$

Related Solutions

[Math] Probability about a coin games

There's a nice discussion of Penney's game in Section 8.4 of Concrete Mathematics. Using the techniques described there, the answers I get (confirming joriki's) are

(a) $(1 + p + p^2)q$, which is $0.657$ when $p = 0.7$, $q = 0.3$.

(b) $\frac{1-pq}{2-p}$, which is $\frac{79}{130} \approx 0.608$ when $p = 0.7, q = 0.3$.

I'll work through part (b) to show you how the techniques in Concrete Mathematics work.

Suppose Player A chooses HTH and Player B chooses THH. Let $S_A$ be the sum of the winning configurations for Player A, so that $$S_A = \text{HTH + HHTH + THTH + HHHTH + HTHTH + TTHTH} + \cdots$$ Similarly, the sum of the winning configurations for Player B is $$S_B = \text{THH + TTHH + HTTHH + TTTHH} + \cdots$$ One advantage of doing this is that if we let $H = 0.7$ and $T = 0.3$ in these two equations $S_A$ and $S_B$ give the probabilities that Player A and Player B win, respectively.

Then, let $N$ denote the sum of the sequences in which neither player has won so far: $$N = 1 + \text{H + T + HH + HT + TH + TT + HHH + HHT + HTT + THT + TTH + TTT} + \cdots$$ Now, we look for a set of equations relating $S_A, S_B,$ and $N$. First, we can write the sum of all configurations in two different ways, so they must be equal: $$1 + N(\text{H + T}) = N + S_A + S_B.$$ Adding HTH to any configuration in $N$ results in a win for $A$, a win for $A$ followed by TH, or a win for $B$ followed by a TH, so $$N \text{ HTH} = S_A + S_A \text{ TH} + S_B \text{ TH}.$$ Finally, adding THH to a configuration in $N$ results in a win for $A$ followed by an H or a win for $B$, so we have $$N \text{ THH} = S_A \text{ H} + S_B.$$ Letting $H = p$ and $T = q$ and solving the last three equations, I get $S_A = \frac{1-pq}{2-p}$ and $S_B = \frac{1-p+pq}{2-p}$. With $p = 0.7$, this yields $S_A = \frac{79}{130} \approx 0.608$ and $S_B = \frac{51}{130} \approx 0.392$.

For another example of the use of this technique, see a question related to two competing patterns in coin tossing.

Probability of winning 3 out of 5 games (with different winning chance on each game)

You do not have to run one million simulations to estimate the probability of winning exactly three games. What you would have to do, is calculate the probability of each of the possible scenarios. Since you need to win three out of five games, the number of valid combinations equals ${5 \choose 3} = 10$. The following Python program takes care of this:

from itertools import permutations


def unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p
            yield p

        
p_win = [0.5, 0.6, 0.05, 0, 0.4]
p_tot = 0
for t in unique_permutations([1, 1, 1, 0, 0]):
    p = 1
    for i in range(5):
        p *= p_win[i] if p[i] else 1 - p_win[i]
    p_tot += p
print(p_tot)

Overall, we find that the probability of winning exactly three games equals $0.133$.

Best Answer

Related Solutions

[Math] Probability about a coin games

Probability of winning 3 out of 5 games (with different winning chance on each game)

Related Question