Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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). $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.