Calculating the hitting probability using the strong markov property ** This problem is from Markov Chains by Norris, exercise 1.5.4.**
A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are known, taking $F_{n+1}$ to be either the sum or the difference of $F_{n-1}$ and $F_n$, each with the probability $1/2$.  Is $(F_n)_{n\ge0}$ a Markov chain?
(a) By considering the Markov chain $X_n=(F_{n-1},F_n)$, find the probability that $(F_n)_{n\ge0}$ reaches $3$ before first returning to $0$.
(b) Draw enough of the flow diagram for $(X_n)_{n\ge0}$ to establish a general pattern.  Hence, using the strong Markov property, show that the hitting probability for $(1,1)$, starting from $(1,2)$, is $(3-\sqrt{5})/2$.
(c) Deduce that $(X_n)_{n\ge0}$ is transient.  Show that, moreover, with probability $1$, $F_n \rightarrow \infty$ as $n \rightarrow \infty$.

My attempt for (b): From $(1,2)$ the chain looks like $(1,2)\rightarrow (2,3)$ or $(1,2)\rightarrow (2,1)$ each with probability 1/2. From $(2,1)$ we can reach $(1,1)$. I want to calculate the probability generating function using the strong markov property $\phi(s)=\mathbb{E}_{(1,2)}(s^{H_{(1,2)}^{(1,1)}})$ where $H_{(1,2)}^{(1,1)}=\inf \{n\geq 0\colon X_n=(1,1) \text{ starting from } (1,2)\}$. I thought that if we start in $(2,3)$ and we want to reach $(1,1)$ we at least have to go trough $(1,2)$ again and then from $(1,2)$ to $(1,1)$. So I believe that $\mathbb{E}_{(2,3)}(s^{H_{(2,3)}^{(1,1)}})=\phi(s)^2$, but I am not sure if this true
I really need help with this exercise.
Thank you.
 A: I also stumbled upon this problem.  I did not solve (a) and (c) so far, but for you specific questions I have the answer.
If drawing the flow diagram of the Markov chain up to 4 steps from $(1,2)$ (i.e., about $2^4$ states can be reached), one notices, that one step into the wrong direction (e.g., from $(1,2)$ to $(2,3)$ requires 2 steps back.
An example: $(1,2) \rightarrow (2,3)$ requires 2 steps $(2,3) \rightarrow (3,1) \rightarrow (1,2)$ to get back to the initial position.  This holds true for any state.  With this observation in mind, we can write down the hitting probability of $(1,1)$ starting from $(1,2)$ denoted as $h_{(1,2)}^{(1,1)} := h_{(1,2)}$:
$$h_{(1,2)} = \frac{1}{2} h_{(2,3)} + \frac{1}{2} h_{(2,1)},$$
and
$$h_{(2,3)} = h_{(2,3)}^{(1,2)} h_{(1,2)} = h_{(1,2)} h_{(1,2)} = h_{(1,2)}^2,$$
because $h_{(2,3)}^{(1,2)}$ has the same distribution as $h_{(1,2)}$.  A similar argument can be used to derive
$$h_{(2,1)} = \frac{1}{2-h_{(1,2)}}.$$
Putting this together, we end up at
$$0 = h_{(1,2)}^3 + 4h_{(1,2)}^2 - 4h_{(1,2)} + 1.$$
In this case, the only valid solution to this equation is $h_{(1,2)}=\frac{3-\sqrt{5}}{2}$.
A: I'm self-studying this book recently. I'm not so sure about my answer. 
Part (a)
The probability is $\frac{3}{7}$.
Define $$h_{i,j} = \mathbb P(F_0 = i, F_1 = j, (F_n)_{n\geq 0} \textrm{ a Markov Chain reaches 3 before returning to 0})$$
Then all we need to figure out is:
$$ h_{0,1} = h_{1,1} = \frac{1}{2}h_{1,2}+\frac{1}{2}h_{1,0}$$
$$ = \frac{1}{4}h_{2,3}+\frac{1}{4}h_{2,1}+\frac{1}{2}h_{1,0}$$
$$ = \frac{1}{4}h_{2,3}+\frac{1}{8}h_{1,3}+\frac{1}{8}h_{1,1}+\frac{1}{2}h_{1,0}$$
$$ \Rightarrow \frac{7}{8}h_{1,1} = \frac{1}{4}h_{2,3}+\frac{1}{8}h_{1,3}+\frac{1}{2}h_{1,0}$$
$$ = \frac{1}{4}+\frac{1}{8}$$
$$ h_{0,1} = h_{1,1} = \frac{3}{7}$$
Part (b) by Dominik Scherempf is clear but I don't know why $h^{(1,2)}_{(2,3)}$ has the same distribution as $h^{(1,1)}_{(1,2)}$. Can we explain by the fact that they start from $(a,b)$ and end at $(b, a+b)$?
Part (c) to be solved. 
A: Let $\mathcal{S}\subset \mathbb{N}^2$ be the set of states reachable from $(0,1)$ and $\mathcal{S}^*=\mathcal{S}\setminus \{(0,1),(1,0)\}$. It is not hard to see that $\mathcal{S}^*$ is just the set of all co-prime pairs. On the one hand, if $(x,y)\neq (1,1)$ are co-prime then both $(y,x+y)$ and $(y,|x-y|)$ are co-prime. On the other hand, any co-prime $(x,y)$ can be reached from $(1,1)$ through a "reverse" Euclidean algorithm.
Define the sum operator to be $s$ and difference operator to be $d$ on $\mathcal{S}$ such that $s(x,y)=(y,x+y)$ and $d(x,y)=(y,|x-y|)$. We use some natural abbreviations on the compositions of operators such as writing $s\circ d$ as $sd$ and $s\circ s$ as $s^2$.
For example, $ssdds(0,1)=ssdd(1,1)=ssd(1,0)=ss(0,1)=s(1,1)=s(1,2)=(2,3)$.
As Dominik Schrempf mentioned, we have $dds=\mathrm{id}$, the identity function, since $dds(x,y)=dd(y,x+y)=d(x+y,x)=(x,y)$. Thus for any state $S\in\mathcal{S}^*$, we can write it in an "irreducible form" as $S=s^{a_1}(ds)^{b_1}\ldots s^{a_k}(ds)^{b_k}(1,1)$ where $a_i$s and $b_i$s are non-negative integers and for any $i\in[k]$, $a_i+b_i\geq 1$.  The key observation is that, every state has a unique such representation. This is because,  $s(x,y)=(y,x+y)$ and $ds(x,y)=d(y,x+y)=(x+y,x)$ and when $x,y\geq 1$, we have $x+y>y$ and $x+y>x$. Thus you can recover the  "irreducible form" of any state in $\mathcal{S}^*$ step by step.
For example, given state $(7,3)$, since $7>3$, it must be a $ds$, i.e. $(7,3)=ds(3,4)$. Since $3<4$, we can only write $(3,4)=s(1,3)$, and so on. Finally, we get the unique "irreducible form" $(7,3)=(ds)s^2(ds)(1,1)$.
Now denote $s$ as $a$ and $ds$ as $b$ and we can represent each state in $\mathcal{S}^*$ by a binary string. For example, $aba=s(ds)s(1,1)=(1,4)$. The Markov chain is translated to the binary string version as follows. For any binary string $w$, $aw$ goes to $bw$ and $aaw$ with equal probability; $bw$ goes to $w$ and $abw$ with equal probability. From this view, we see the distribution of the hitting time from $aw$ to $w$ is identical for all $w$ and the same is true for $bw$.
Now for Question (b), note that $(1,1)=\emptyset$, $(1,2)=s(1,1)=a$, $(2,3)=ss(1,1)=aa$, $(2,1)=ds(1,1)=b$. Let $\phi(s)=\mathbb{E}(s^{H_{a}^{\emptyset}})$ and $\psi(s)=\mathbb{E}(s^{H_{b}^{\emptyset}})$. Thus we have
$$\phi(s)=\mathbb{E}(s^{H_{a}^{\emptyset}})=\frac{s}{2}(\mathbb{E}(s^{H_{b}^{\emptyset}})+\mathbb{E}(s^{H_{aa}^{\emptyset}}))=\frac{s}{2}(\psi(s)+\phi(s)^2)$$
and
$$\psi(s)=\mathbb{E}(s^{H_{b}^{\emptyset}})=\frac{s}{2}(\mathbb{E}(s^{H_{\emptyset}^{\emptyset}})+\mathbb{E}(s^{H_{ab}^{\emptyset}}))=\frac{s}{2}(1+\phi(s)\psi(s)).$$
Organizing the equations one gets
$$s\phi(s)^3-4s\phi(s)^2+4\phi(s)-s^2=0.$$
Let $s$ goes to $1$ from above and one gets the probability of hitting $(1,1)$ from $(1,2)$ as a solution of $$x^3-4x^2+4x-1=0$$ which gives $x=(3-\sqrt{5})/2$ as the only valid solution.
