Produce a sequence of random variables $\left\{X_{n}\right\}_{n \geq 0}$ as follows: Let $X_{0}$ and $X_{1}$ be some fixed constants. For $i>1,$ let $X_{i}=X_{i-1}+X_{i-2}$ with probability $1 / 2$ and $X_{i}=\left|X_{i-1}-X_{i-2}\right|$ with probability $1 / 2$
- Suppose that $X_{0}=0$ and $X_{1}=1 .$ Find the probability $$\mathbb{P}\left(\exists n \text { such that } X_{n}=3 \text { and } X_{i} \neq 0 \text { for all } 1 \leq i<n\right)$$ (This is the probability of the sequence $\left\{X_{n}\right\}$ reaching 3 before returning to the starting point $\left.0 .\right)$
- Now suppose that $X_{0}=1$ and $X_{1}=2 .$ Find the probability $$\mathbb{P}\left(\exists n \text { such that } X_{n}=X_{n+1}=1\right)$$
I have no idea and can anyone help me?