Probability about a coin games
Independent flips of a biased coin that lands on heads with probability is 0.7 are made. Each of two players, A and B has chosen one out of the eight triplets HHH, HHT, HTH, HTT, THH, THT, TTH and TTT, and the player whose triplet occurs first wins. For example, suppose A had chosen HHT and B had chosen THT. Then if the flipped coin shows the sequence HHHT....., A wins, and if the flipped coin shows the sequence TTTHT..., B wins. Since the coin is biased towards heads, the triplet HHH seems to be a good choice.
a) What is the probability that the pattern THH occurs before the pattern HHH?
b) What is the probability that the pattern HTH occurs before the pattern THH?
c) What is the probability that the pattern HHH occurs before the pattern HTH?
Solution 1:
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$.
(c) $\frac{p}{1+pq}$, which is $\frac{70}{121} \approx 0.579$ 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.
Solution 2:
a) The pattern THH always occurs before the pattern HHH unless the pattern HHH occurs right away. The probability for it to occur right away is $0.7^3=0.343$, so the probability for THH to occur first is $1-0.343=0.657$.
b) Mike has already provided a nice solution for this part. Here's another approach:
Note that the two patterns always alternate at getting a chance to be completed by an H: If HT fails to be completed to HTH, we have TT, and after some number of Ts we will end up with TH. That gives a chance to complete THH with an H, and if that fails, we have HT, which starts the cycle over.
Now if two players have alternating chances of winning with probability $q=0.7$, the probability of the player going first winning is
$$q+(1-q)^2q+\dotso=\frac q{1-(1-q)^2}=\frac q{2q-q^2}=\frac1{2-q}\;.$$
Now the HT chance comes up first if the first flip is an H, with probability $q$, whereas if the first flip is a T, with probability $1-q$, the TH chance comes up first. Thus the probability for HTH to come first is
$$ q\frac 1{2-q}+(1-q)\left(1-\frac1{2-q}\right) =\frac {q+(1-q)(1-q)}{2-q} =\frac {1-q+q^2}{2-q}\;. $$
With $q=0.7$, this is $79/130\approx0.608$.
c) Let $p$ denote the probability for HHH to come first. Let's find an equation for $p$ by tracing how the chances for completing the patterns evolve. First we have to wait for an H. Then with probability $1-q$ we get a T, and HHH loses unless this is followed by another T, again with probability $1-q$. Then we're back where we started, so this branch contributes a winning probability $(1-q)^2p$. On the other hand, with probability $q$ the first H is followed by another H. Then we have probability $q$ for another H to complete HHH, and probability $1-q$ for a T, in which case, as before, we must have another T, with probability $1-q$, to avoid HTH and get back to where we started; so this branch contributes a winning probability $q(q+(1-q)^2p)$. In total, we have
$$p=(1-q)^2p+q(q+(1-q)^2p)\;,$$
and solving for $p$ yields
$$p=\frac q{1+q-q^2}\;.$$
For $q=0.7$, this is $70/121\approx0.579$.
Collecting the results, we find that THH beats HHH with probability $0.657$, HTH beats THH with probability $0.608$, and HHH beats HTH with probability $0.579$. Thus, if we restrict the game to these three choices, there is no pure-strategy Nash equilibrium: Whichever two of these three patterns have been chosen, it pays for one of the two players to switch to the remaining pattern.
Solution 3:
After reading the above answers I propose the following systematic procedure for such problems:
Assume that Alice has chosen $HTH$ and Bob has chosen $THH$. Draw a graph with vertex set $V$ the initial segments of winning positions for this game: $$V=\{S, H,T, HH, HT, TH, TT, HTH, THH\}$$ where $S$ (for "start") denotes the empty segment. From each vertex other than $HTH$ and $THH$ there are two directed edges to the next possible positions, e.g. from $HT$ there is an edge to $HTH$ and to $TT$. The edges carry a probability factor $0.7$, resp. $0.3$. Each vertex $v\in V$ is assigned a variable (unknown) $p_v$ which denotes the probability that Alice wins when the game is in state $v$. Right away one has $p_{HTH}=1$ and $p_{THH}=0$, and for each nonterminal $v\in V$ one has an equation relating $p_v$ to the $p_{v'}$s one edge length downstream.$\ $ E.g., $$p_{HT}={0.7}p_{HTH}+{0.3}p_{TT}={0.7}+{0.3}p_{TT}\ .$$ Solving the resulting (sparse) system of linear equations we finally arrive at the value $p_S$ giving the a priori probability that Alice wins the game.
Solution 4:
My part b working:
let $$ a = P(HTH \text{ before }THH\text{ given first two tosses are }HT) = P(HTH\text{ before }THH\text{ given first two tosses are }HH) $$
For the case of $HH$, there will be no chances, until the next $T$ comes in, i.e. same as starting with $HT$.
Similarly, let $$ b = P(HTH\text{ before }THH\text{ given first two tosses are }TH) = P(HTH\text{ before }THH \text{ given first two tosses are }TT) $$
We have: $$a = 0.7 + 0.3\times 0.3a$$ i.e. $HT$ followed by $H$ (0.7 here), or $HT$ followed by a $T$ (0.3 here) plus $TTTTH$ and then a $T$ (0.3 here). The number of $T$ in between does not matter as it must finally becomes $TH$. so $a = \frac{10}{13}$
Similarly, $$b = 0.3\times 0.7 + 0.3\times 0.3b$$ i.e. $TH$ followed by $T$ (0.3 here) and then $H$ (0.7 here) to win, or $TH$ followed by $T$ (0.3 here) $TTTTH$ and then $T$ (0.3 here). so $b = \frac{3}{13}$
$$\text{the required probability} = [P(HH)+P(HT)]\times a + [P(TT)+P(TH)]\times b = 79/130$$
Another way to solve for a and b (probably easier to understand):
$$a = 0.7 + 0.3b $$ $HT$ followed by $H$ (0.7) to win, or $HT$ follow by $T$ (0.3) to become the case of starting with $TT$.
Similarly, $$b = 0.3 \times a $$ $TH$ followed by $T$ (0.3) and it becomes the case of starting with $HT$