# Random walk with 3 possible steps

I have i.i.d. random variables with following distribution:

$$P(\xi_i =1) = p_1, \ P(\xi_i = 0) = p_0, \ P(\xi_i = -1) = p_{-1}; \quad S_n = \sum^n_{i=1}\xi_i.$$

I am interested in probability of $( S_n ) _{n=1}^{\infty}$ reaching some level $-L$ before reaching $L$.

I know the results for standard random walk with only two possible steps: -1 and 1. So my idea is to find the corresponding probability for this adjusted random walk:

$$P(\xi'_i =1) = \frac{p_1}{p_1 + p_{-1}}, \ P(\xi'_i =-1) = \frac{p_{-1}}{p_1 + p_{-1}}; \quad S'_n = \sum^n_{i=1}\xi'_i.$$

And prove that it is the same as probability for my original walk.

I have found an answer for the "adjusted" walk but I am stuck with this proof. Any suggestions would be much appreciated.

-
I think you should say something about the level of rigour you're aiming for, since at a normal level of rigour this is obvious enough not to require a proof; you've just eliminated the zero steps. – joriki Nov 30 '12 at 10:59
I agree with you on that it doesn't require a proof. But as I decided for myself that it is obvious I tried to sketch a proof in my head and realised that all my suggestions can't be used for a rigorous proof. It seems to me that a statement on correspondence between random walks of first and second types should do the job, but I can't think of it. So, I am aiming for a sketch of a rigorous proof or a general idea of such a proof. – grozhd Nov 30 '12 at 11:58

There are at least two ways to make this rigorous. Either one builds a path transform, as follows. Define $\tau_0=0$ and, for every $n\geqslant0$, $\tau_{n+1}=\inf\{k\geqslant\tau_n+1\mid\xi_k\ne0\}$, then $(S_{\tau_n})_{n\geqslant0}$ performs a random walk whose steps are distributed like your $\xi'$ random variables, that is, $(S_{\tau_n})_{n\geqslant0}$ and $(S'_{n})_{n\geqslant0}$ are equidistributed. In particular, $(S_n)_n$ hits $\pm L$ at the same place as $(S_{\tau_n})_n$, and you are done.
Or, one can turn to discrete harmonic analysis and consider, for every $-L\leqslant x\leqslant L$, the probability $h_x$ that $(S_n)_n$ starting from $x$ hits $L$ before $-L$. Then you are after $h_0$ and $(h_x)_{-L\leqslant x\leqslant L}$ is entirely determined by the boundary conditions $h_L=1$, $h_{-L}=0$, and, by the Markov property after one step, for every $-L\leqslant x\leqslant L-1$, $$h_x=p_1h_{x+1}+p_0h_x+p_{-1}h_{x-1}.$$ Likewise, the probabilities $h'_x$ that $(S'_n)_n$ starting from $-L\leqslant x\leqslant L$ hits $L$ before $-L$ are entirely determined by the boundary conditions $h'_L=1$, $h'_{-L}=0$, and, by the Markov property after one step, for every $-L\leqslant x\leqslant L-1$, $$h'_x=p'_1h'_{x+1}+p'_{-1}h'_{x-1}.$$ These two linear systems coincide hence $h'_x=h_x$ for every $-L\leqslant x\leqslant L$, and in particular, $$\mathbb P((S_n)_n\ \text{hits}\ L\ \text{before}\ -L)=h_0=h'_0=\mathbb P((S'_n)_n\ \text{hits}\ L\ \text{before}\ -L).$$