Random walk on integers keeping direction with prob $p$ and changing direction with prob $1-p$

Question

An insect moves on the integers in steps $\pm 1$, in a way that it keeps its direction with prob $p$ and changes direction with prob $1-p$. Its position at time $t=0$ is $0$ (coming from $-1$).

(1) Define a Markov chain that describes the insect's movement and find the transition probabilities.

(2) Find the probability the insect reaches state $N$ before it reaches $-N$.

Attempt. Let $X_n$ be the insect's position after $n$ steps. Then $X_n$ takes values on integers and if fact $X_{2n}$ takes values $-2n,\ldots,-2,0,2,\ldots,2n$ (for example $$P(X_2=+2)=p^2,~P(X_2=0)=(1-p)p+(1-p)^2,~P(X_2=-2)=(1-p)p)$$ and $X_{2n+1}$ takes values $-2n-1,\ldots,-1,1,\ldots,2n+1$. As for the transition probabilities, if $X_{2n}=2k$ then the probability $X_{2n+1}=2k+1$ equals: $$p\times \textrm{number of ways to reach position $2k$ from left in $2n$ steps}~+$$ $$(1-p)\times \textrm{number of ways to reach position $2k$ from right in $2n$ steps}~~~(\star).$$ Of course $$P(X_{2n+1}=2k-1\mid X_{2n}=2k)=1-P(X_{2n+1}=2k+1\mid X_{2n}=2k),$$ $$P(X_{2n}=2k\mid X_{2n-1}=2k-1)=\ldots~(\textrm{as above}),$$ $$P(X_{2n}=2k-2\mid X_{2n-1}=2k-1)=1-P(X_{2n}=2k\mid X_{2n-1}=2k-1).$$

I have stuck on evaluating the above number of ways in ($\star$).

Thanks in advance for the help.

Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$For the first question, denote $q = 1 - p$ and define $X_n \in \{1, -1\}$ to be the $n$-th move for $n \geqslant 0$, then $X_0 = 1$ and\begin{gather*} P(X_{n + 1} = 1 \mid X_1, \cdots, X_n) = P(X_{n + 1} = 1 \mid X_n)\\ = p \cdot \frac{1 + X_n}{2} + q \cdot \frac{1 - X_n}{2},\\ P(X_{n + 1} = -1 \mid X_1, \cdots, X_n) = P(X_{n + 1} = -1 \mid X_n)\\ = p \cdot \frac{1 - X_n}{2} + q \cdot \frac{1 + X_n}{2}, \end{gather*} which means $\{X_n\}$ is a Markov chain with respect to $\{\mathscr{F}_n\}$ where $\mathscr{F}_n = σ(X_1, \cdots, X_n)$.

Now for the second question, define $S_0 = 0$, $S_n = \sum\limits_{k = 1}^n X_k$ for $n \geqslant 1$, $τ_a = \min\{n \geqslant 0 \mid S_n = a\}$, where $\min\varnothing := \infty$, and $τ = τ_N \land τ_{-N}$. It is easy to prove that $P(τ < \infty) = 1$. Note that the probability to be found is $P(τ_N < τ_{-N})$. Denote $c = \dfrac{p - q}{2q}$, then for $n \geqslant 0$,\begin{align*} &\peq E(S_{n + 1} + cX_{n + 1} \mid \mathscr{F}_n) = S_n + (1 + c) E(X_{n + 1} \mid \mathscr{F}_n)\\ &= S_n + (1 + c)(pX_n + q(-X_n)) = S_n + cX_n, \end{align*} which implies $\{S_n + cX_n\}$ is a martingale. Note that for any $n \geqslant 0$, there is $|S_{τ \land n}| \leqslant N$ and $|X_{τ \land n}| = 1$, thus $\{S_{τ \land n} + cX_{τ \land n}\}$ is a bounded martingale. By the optional stopping time theorem,$$ E(S_τ + cX_τ) = E(S_0 + cX_0) = c. $$ Note that$$ E(S_τ + cX_τ) = E((S_{τ_N} + cX_{τ_N}) I_{\{τ_N < τ_{-N}\}}) + E((S_{τ_{-N}} + cX_{τ_{-N}}) I_{\{τ_N > τ_{-N}\}}). $$ Because $S_{τ_N} = N$ and $X_{τ_N} = 1$ on $\{τ_N < \infty\}$, and $S_{τ_{-N}} = -N$ and $X_{τ_{-N}} = -1$ on $\{τ_{-N} < \infty\}$, then\begin{gather*} c = E(S_τ + cX_τ) = (N + c) P(τ_N < τ_{-N}) + (-N - c) P(τ_N > τ_{-N}),\\ 1 = P(τ_N < τ_{-N}) + P(τ_N > τ_{-N})\\ \Longrightarrow P(τ_N < τ_{-N}) = \frac{N + 2c}{2N + 2c} = \frac{qN + (p - q)}{2qN + (p - q)}. \end{gather*}

Answer 2

It seems that your Markov chain should have two states per each position $n$, one for the case when the insect is looking left ($n_l$) and another for the opposite case ($n_r$). Then, by definition, in the basis $(\ldots,-1_l,-1_r,0_l,0_r,1_l,1_r,2_l,2_r,\ldots)$ the transition matrix will be (denote $q=1-p$): $$ \left(\begin{array}{rrrrrrrrrr} \ddots&.&.&.&.&.&.&.&.&.\\ .&0&0&p&q&0&0&0&0&.\\ .&0&0&0&0&0&0&0&0&.\\ .&0&0&0&0&p&q&0&0&.\\ .&q&p&0&0&0&0&0&0&.\\ .&0&0&0&0&0&0&p&q&.\\ .&0&0&q&p&0&0&0&0&.\\ .&0&0&0&0&0&0&0&0&.\\ .&0&0&0&0&q&p&0&0&.\\ .&.&.&.&.&.&.&.&.&\ddots\\ \end{array}\right) $$