6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Commented May 27, 2019 at 2:33
  • $\begingroup$ @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}$ $\endgroup$
    – VitaminC
    Commented May 27, 2019 at 7:27

1 Answer 1

1
$\begingroup$

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<a-k$ 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}}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .