The question:
A person playing a game randomly chooses a number, $1$ or $0$. He keeps choosing them, creating a number made of $1$s and $0$s.
For example, choosing $1$, then five $0$s and then two $1$s gives the number $10000011$
If at any point the last four digits of the number are $0010$, he wins. If the last four digits are $1001$, he loses.
Find the probability that he wins.
At first I thought to build a Markov chain with the 16 states from $0000$ to $1111$, but then finding out the probabilities would require a lot of matrix multiplication. Also the number can go on indefinitely with series of a single digit, which makes things difficult. (Vectors of hitting probability also have the same problem)
So I thought to use conditional probability. Let the probability that he wins, given the first choice is a $1$, be $x$, and for $0$, $y$.
Here something cool happens. Long series of $1$s and $0$s, specifically of length more than $3$, can be treated as having length $3$ anyway. For example, say the choices are $1$, and then the choice keeps being zeroes. Since a $1$ has to be chosen again eventually (because otherwise the game never ends) this is the same as $1000$.
One could also say that choosing a long string of $0$s is equivalent to starting a game with a choice of $001$.
So I can calculate the probability of winning after $1000..._{\{\text{some amount of 0s}\}}...0$. Since a 1 must eventually come, we are left with the last three digits $001$. Here the probability of choosing $0$ and winning is $\frac12$. The probability of choosing $1$ is $\frac12$, and this is equivalent to starting a game with a first choice as $1$, in which the probability of winning is already defined as $x$. Thus giving the probability of winning after $1000...0$ to be $\frac12+\frac x2$.
I cannot see how to go further.
Please help.
Labelling the start as $s$, and other sequences (states) as below:
$0=a,\quad 00=b,\quad 001=c,\quad 1=d,\quad 10=e,\quad 100=f$
Tracing the route to $0010$ victory, we get the equations
$s=.5(a+d), \;\; a=.5(b+d),\;\; d=.5(e+d),\;\;b=.5(c +b),\;\; e= .5(f+d)$
$c=.5(d+1)\;\;$[The $+1$ to ensure victory for $0010$]
$f=.5(b+0)\;\;$[The $+0$ to ensure defeat for opponent]
Solving the equations gives $P(0010)$ wins $= \dfrac{5}{12}$