hitting time of one of two barriers Let's consider a one-dimensional Random Walk. At each time the walker moves of one step to the right with probability $p$ and to the left with probability $q$, with $p+q=1$. The walk is not symmetric, then $p \neq q$
How can I find the explicit formula of the probability to hit for the first time one of the two walls located in $x=n$ and $x=-n$ at time $t$, given that the walk started from $x=0$ at time $t=0$?
 A: In order for the walker to reach position $x$ at time $t$. A necessary condition is $x \equiv t \pmod 2$. Assume this is true, the walker have make $s = \frac{t+x}{2}$ steps forward and $t - s = \frac{t-x}{2}$ steps backward.
In the absence of walls, the probablity for the walker to be at position $x$ is given by
$$P_{free}(x,t) = \operatorname{Prob}\left[\,X(t) = x\,\right]
=\binom{t}{\frac{t+x}{2}} p^{\frac{t+x}{2}} q^{\frac{t-x}{2}}
$$
In the presence of walls, the probability for the walker at position $x$ and never hit the walls before will be modified to:
$$\begin{align}
P(x,t)  &= \operatorname{Prob}\left[\,X(t) = x : -n < X(t') < n,\,\forall t' < t\,\right] \\&=\sum_{r = \lceil\frac{x-t}{2n}\rceil}^{\lfloor\frac{x+t}{2n}\rfloor} (-1)^{r} \binom{t}{\frac{t+x-2rn}{2}} p^{\frac{t+x}{2}} q^{\frac{t-x}{2}}
\end{align}$$
The formula can be derived using reflection principle. It is equivalent to start the random
walk at time $t = 0$ with $(-1)^r$ phantom walker at position $\pm 2rn$ for each $r \in \mathbb{N}$. The range of summation over $r$ in above formula is limited to those which will actually contribute to $P(x,t)$ at time $t$.  
For the walker to hit the wall $\pm n$ at time $t$, we again require $t \equiv n \pmod 2$. Furthermore, the walker must be at position $\pm (n-1)$ at time $t - 1$. In next move,


*

*(case $X(t-1) = n - 1$) the walker has a probability $p$ to turn right and hit the right wall.

*(case $X(t-1) = 1 - n$) the walker has a probability $q$ to turn left and hit the left wall.


This implies the probability for first hit (assume $t \equiv n \pmod 2$) is given by:
$$\begin{align}
P_{hit}(t) &= p P(n-1,t-1) + q P(-n+1,t-1)\\
&= \sum_{r = \lceil\frac{n-t}{2n}\rceil}^{\lfloor\frac{n+t-2}{2n}\rfloor} (-1)^{r} \binom{t-1}{\frac{n+t-2rn}{2} - 1} \left( p^{\frac{t+n}{2}} q^{\frac{t-n}{2}} +  q^{\frac{t+n}{2}} p^{\frac{t-n}{2}} \right)
\end{align}$$
For $t = n + 2k$, we can simplify this to:
$$P_{hit}(n+2k) = \sum_{-\lfloor\frac{k}{n}\rfloor}^{\lceil\frac{k}{n}\rceil}(-1)^r\binom{n+2k-1}{nr+k}(p^n + q^n) (pq)^k$$
A: The idea is to compute $u(s,x)=\mathbb E_x(s^T)$ for every integer  $|x|\leqslant n$ and complex number $|s|\leqslant1$, where $T$ is the first hitting time of $\pm n$. Then $u(s,0)$ is the generating function of the sequence of general term $\mathbb P_0(T=k)$, that is, $u(s,0)=\sum\limits_k\mathbb P_0(T=k)s^k$.
Each family $(u(s,x))_{|x|\leqslant n}$ solves a recursion based on the Markov property of the random walk after one step. More precisely, $u(s,x)=s(pu(s,x+1)+qu(s,x-1))$ for every $|x|\leqslant n-1$. For each fixed $s$ this is a second order linear recursion hence $u(s,x)=av^x+bw^x$ for every $|x|\leqslant n$, where $v$ and $w$ solve the characteristic equation $\xi=s(p\xi^2+q)$. Using the boundary conditions $u(s,\pm n)=1$, one gets
$$
a=\frac{w^{-n}-w^n}{v^nw^{-n}-v^{-n}w^n},
\quad
b_n=\frac{v^{n}-v^{-n}}{v^nw^{-n}-v^{-n}w^n}.
$$
Thus, $u(s,0)=a+b$, that is, after some simplifications,
$$
\sum\limits_k\mathbb P_0(T=k)s^k=\frac{1+v^nw^n}{v^n+w^n}=\frac{1+(q/p)^n}{v^n+w^n},\quad v,w=\frac{1\pm\sqrt{1-4pqs^2}}{2ps}.
$$
Thus,
$$
\sum\limits_k\mathbb P_0(T=k)s^k=s^n\frac{p^n+q^n}{x_n(4pqs^2)},
$$
with
$$ 
x_n(t)=\frac1{2^n}\left(\left(1+\sqrt{1-t}\right)^n+\left(1-\sqrt{1-t}\right)^n\right).
$$
Note that $x_n$ is a polynomial with degree $\lfloor n/2\rfloor$ and constant term $1$, hence expanding $1/x_n(t)$ as a series  yields every coefficient $\mathbb P_0(T=n+2k)$ for $k\geqslant0$ (the others being zero). More explicitly,
$$
x_n(t)=\frac1{2^{n-1}}\sum_{i\geqslant0}{n\choose 2i}(1-t)^i=\sum_{j\geqslant0}(-1)^j\left(\sum_{i\geqslant j}\frac1{2^{n-1}}{n\choose 2i}{i\choose j}\right)t^j=1-z_n(t),
$$
hence
$$
\mathbb P_0(T=n+2k)=(p^n+q^n)(4pq)^k\times\text{the coefficient of $t^k$ in}\sum_{\ell=0}^kz_n(t)^\ell.
$$
