Random walk on integers keeping direction with prob $p$ and changing direction with prob $1-p$ 
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.
 A: $\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*}
A: 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) $$
