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$?
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).$$