# The distribution of hitting time of a random walk

Suppose we have a random walk $X_n=X_0+\sum_{k=1}^n \xi_k$ where $\xi_k, k=1,2,3,...$ are i.i.d. Bernoulli random variables whose distribution is $P(\xi_k=1)=p$ and $P(\xi_k=-1)=1-p=q$, and $X_0$ is an integer. Let $a<X_0<b$ and $\tau = \inf\{n:X_n \in \{a,b\} \}$, and set the filtration $\mathscr{F}_n = \sigma(\xi_k, k=1,2,3,...)$. I want to compute the distribution of $\tau$.

Let $u(x)=E[z^{\tau}|X_0=x]$, where $|z|<1$. Then we have: \begin{cases} u(x)=(pu(x+1)+qu(x-1))z \\ u(a)=u(b)=1 \end{cases} I generally have two questions:

1. I know $u(x)=(pu(x+1)+qu(x-1))z$ is right, and generally we should have $E[z^{\tau}|X_k=x]=z^k E[z^{\tau}|X_0=x]=z^k u(x)$. But I need a rigorous "proof" to convince my self. I tried this: \begin{align} u(x) &= E[z^{\tau}|X_0=x]\\ &= E[z^{\tau}|X_0=x, X_1= x + 1]P(X_1= x + 1) + E[z^{\tau}|X_0=x, X_1= x - 1]P(X_1= x - 1)\\ &=pE[z^{\tau}|X_0=x, X_1= x + 1] + qE[z^{\tau}|X_0=x, X_1= x - 1]\\ &=pE[z^{\tau}|X_1= x + 1] + qE[z^{\tau}|X_1= x - 1]\\ &=(pE[z^{\tau-1}|X_1= x + 1] + qE[z^{\tau-1}|X_1= x - 1])z\\ &=(pE[z^{\tau}|X_0= x + 1] + qE[z^{\tau}|X_0= x - 1])z\\ &=(pu(x+1)+qu(x-1))z \end{align} How to justify $E[z^{\tau}|X_0=x, X_1= x + 1] = E[z^\tau |X_1=x+1]$? I guess it is because $X_n$ is markovian, but just don't know how to justify that equation step by step. And, for $E[z^{\tau-1}|X_1= x + 1] = E[z^{\tau}|X_0= x + 1]$, I know it is very obvious to explain it in words. Is there any way to prove it rigorously in math?

2. How to solve the equation? It seems we have the boundary condition, and we can start from boundary. But I still don't know what is the right direction.

Thank you for any help!