We give a series of random variables $(X_i)_{i \geq 1}$ of i.i.d Bernouil law of parameter $p$ and we denote by $(\Omega, \mathcal{F}, \mathbb{P})$ the probability space. Alice and Bob has a game : if pattern $(1, 1, 0)$ appears before $(1,0,1)$, then Alice wins, otherwise Bob wins. So, what is the probability that Alice wins the game ?
If it is the first time that one meets this question, it may be difficult. If one has met the similar problem, we define $\tau_{110}$ and $\tau_{101}$ for the two patterns, then in the case $p = 1$, a well known result is that $\mathbb{E}[\tau_{110}] = 6$ and $\mathbb{E}[\tau_{101}] = 5$, thus one may guess that $(1,0,1)$ appears at first.
However, it is not the case. And a more amazing result is that, for any $p \in (0,1)$ Alice always has a bigger probability to win the game ! One direct method to do it is to decompose the probability as
the sum
$$\mathbb{P}[\tau_{110} < \tau_{101}] = p_{00} + p_{01} + p_{10} + p_{11}$$ where we define that $$p_{00} = \mathbb{P}[\tau_{110} < \tau_{101}, X_1 = 0, X_2 = 0].$$ And then, we use the fact that the event is only locally correlated, which means using strong Markov property, when conditionned all the history, we only have to keep the last two runs. Then we have a big recursive equation that $$ \left[ {\begin{array}{c} p_{00} \\ p_{01} \\ p_{10} \\ p_{11} \end{array}} \right] = \left[ {\begin{array}{cccc} 1-p& 1-p& 0& 0\\ 0& 0& 1-p& 1-p\\ p& 0& 0& 0\\ 0& 0& 0& p\\ \end{array}} \right] \left[ {\begin{array}{c} p_{00} \\ p_{01} \\ p_{10} \\ p_{11} \end{array}} \right] + \left[ {\begin{array}{c} 0 \\ 0 \\ 0\\ p^2(1-p) \end{array}} \right]$$
Thus, we can solve the equation and obtain that $$\mathbb{P}[\tau_{110} < \tau_{101}] = \frac{1}{2-p}$$.
From the formula, we get that Alice always has bigger probability to win. (And it is like this I find this amazing result.) But does it have a more natural explication why Alice can win ? In fact, we see that Alice and Bob have to wait for a $1$ to win the game. Once it happens, in the following two round, we have $(0,0), (0,1), (1,0), (1,1)$ 4 types of configurations, and $(0,1),(1,0)$ have the same probability. If $(0,0)$ happens, they have to restart the game. If $(1,1)$ happens, we see that stochasticly Alice has bigger probability to win under this condition. That explains the reason.
