# Random Walk $\mathbb P(T_0>n$ and $S_n=a) = \mathbb P(T_a=n) =\frac{a}{n} \mathbb P(S_n=a)$

Consider the random Walk $$S_n$$ on $$\mathbb Z$$ starting in $$x=0$$. Let $$a\in \mathbb Z$$. Define $$T_a(\omega)=\min\{n\in \mathbb N : S_n(\omega)=a\}$$.

Show for $$a> 0$$

$$\mathbb P(T_0>n$$ and $$S_n=a) = \mathbb P(T_a=n) =\frac{a}{n} \mathbb P(S_n=a)$$

I tried looking the different possible paths that lead to the different outcomes i.e. $$T_0>n$$ and $$S_n=a$$ or $$T_a=n$$ and it seems reasonable but in no way am I able to rigorously proof this. I am sorry if this is something very basic to show but when I googled "random walk" or similar terms I only found more complicated models and nothing similar to this particular statement.

• Do we have any information about the distribution of the increments of the random walk? ($S_{n} - S_{n-1}$) The increments are at least symmetric and i.i.d. right? Commented May 27, 2019 at 2:33
• @forgottenarrow Yes, we can assume they are iid and for simplicity $\mathbb P(S_n-S_{n-1}=1)=\mathbb P(S_n-S_{n-1}=-1)=\frac{1}{2}$ Commented May 27, 2019 at 7:27

## 1 Answer

For the first equality, note that $$\Bbb{P}(S_n=a, T_0>n)=\Bbb{P}(S_n=a, S_i\neq0 \text{ for } 1\leq i < n)$$ means that after $$n$$ steps we are at $$a$$, but we have not reached $$0$$ before.

$$\Bbb{P}(T_a=n)=\Bbb{P}(S_n=a, S_i \neq a \text{ for } 1\leq i < n)$$

Why are those two the same? Because the first is a random walk from $$0$$ to $$a$$ without returning to $$0$$ and the second is a walk from $$0$$ to $$a$$, which can be regarded as a walk from $$a$$ to $$0$$, since every walk from $$0$$ to $$a$$ can be walked backwards, so there is an obvious $$1:1$$ correspondence.

During this walk forwards, we have not reached $$a$$ before, so when walking back, we will not reach $$a$$ again after starting from it! So both are walks of length $$n$$, which do not return to their origin before reaching a number that is $$|a|$$ away from the origin. Thus the events are equivalent and their probabilities the same.

As for the second equality, note that

$$\Bbb{P}(T_a=n)=\Bbb{P}(T_a=n, S_n=a)$$

because if the first time we reach $$a$$ is after $$n$$ steps, then obviously after $$n$$ steps we are in $$a$$.

Conditional probability gives us

$$\Bbb{P}(T_a=n, S_n=a)=\Bbb{P}(T_a=n|S_n=a)\Bbb{P}(S_n=a)$$

The first factor is asking: Given that we are at $$a$$ after $$n$$ steps, what is the probability we are here for the first time?

Let $$W_n(0,a)$$ be the set of all walks from $$0$$ to $$a$$ of length $$n$$ and $$D_n(0,a)$$ be the set of direct paths from $$0$$ to $$a$$ of length $$n$$, that is paths that don't visit $$a$$ before the $$n$$-th step.

We get that $$\Bbb{P}(T_a=n|S_n=a)=\frac{|D_n(0,a)|}{|W_n(0,a)|}$$

Now if we have arrived at $$a$$ after $$n$$ steps, that means that we have $$a$$ more $$+1$$ than $$-1$$. After taking $$a$$ of the $$+1$$ away, half of the rest is $$-1$$. This gives us $$\frac{n-a}{2}$$ of $$-1$$, which means that $$\frac{n+a}{2}$$ are $$+1$$.

We get that $$|W_n(0,a)|= {{n}\choose{\frac{n+a}{2}}}$$

as we can distribute our $$+1$$ freely on the $$n$$ steps.

For the direct paths we once again use that any walk can be regarded as a backwards walk and some more technical resources.

$$|D_n(0,a)|=|D_n(a,0)|=|D_{n-1}(a-1,0)|=|W_{n-1}(a-1,0)|-|W_{n-1}(a+1,0)|=$$

$${{n-1}\choose{\frac{n+a}{2}}-1} - {{n-1}\choose{\frac{n+a}{2}}}={{n}\choose{\frac{n+a}{2}}}(\frac{n+a}{2n}-\frac{n-a}{2n})={{n}\choose{\frac{n+a}{2}}}\frac{a}{n}$$

So overall

$$\Bbb{P}(T_a=n|S_n=a)=\frac{|D_n(0,a)|}{|W_n(0,a)|}=\frac{a}{n}$$

and with that $$\Bbb{P}(T_a=n)=\frac{a}{n}\Bbb{P}(S_n=a)$$

The first equality uses that we can walk backwards. The second equality uses that the first step is forced, as if we walked to $$a+1$$ we would have to cross $$a$$ again to get to $$0$$.

The third equality uses the mirroring principle, also called reflection principle, which says that every random walk from $$a-k$$ to $$p that reaches $$a$$ again corresponds bijecitvely to a walk from $$a+k$$ to $$p$$, because all of those pass through $$a$$ and then are identical to some walk that returned to $$a$$.

It is easiest visualised if you imagine walks $$W$$ from $$1$$ to some $$a>0$$. For every walk $$W$$ that touches $$0$$ at step $$t$$, we have a walk $$W*$$ that was a mirror image of $$W$$ until $$t$$ and then is identical. It is also a random walk and also reaches $$a$$. It is crucial to note that in that way we cover all the walks touching $$0$$ and all random walks from $$-1$$ to $$a$$, because all of them have to pass through $$0$$! So we get a correspondence of ALL walks from $$1$$ to $$a$$ that touch $$0$$ at step $$t$$ and all walks from $$-1$$ to $$a$$ that pass through $$0$$ at $$t$$.

(source: sdunbar1 at www.math.unl.edu)

The fourth equality uses our counts for the walks, the fifth is just throwing in some factors where you need them. Set $$\frac{n+a}{2}=x$$:

$${{n-1}\choose{\frac{n+a}{2}}-1} - {{n-1}\choose{\frac{n+a}{2}}}= {{n-1}\choose{x-1}} - {{n-1}\choose{x}}=\frac{(n-1)!}{(x-1)!(n-1-(x-1))!}-\frac{(n-1)!}{x!((n-1)-x)!}=\frac{(n-1)!}{(x-1)!(n-x))!}-\frac{(n-1)!}{x!((n-1)-x)!}=\frac{nx(n-1)!}{nx(x-1)!(n-x)!}-\frac{n(n-x)(n-1)!}{n(n-x)x!((n-1)-x)!}=(\frac{x}{n}-\frac{n-x}{n})\frac{n!}{x!(n-x)!}=(\frac{2x-n}{n}){{n}\choose{x}}=\frac{a}{n}{{n}\choose{x}}$$