Random Walk (1): Reflection Principle

by tzy9393

Consider a simple random walk ${\left\{S_{i}\right\}_{i=1}^{\infty}:=\sum_{i=1}^{\infty}X_{i}}$ on ${\mathbb{Z}}$ with ${\mathbb{P}(X_{i}) = \left\{ \begin{array}{lr} p & : X_{i}=1\\ 1-p & : X_{i}=-1 \end{array} \right. }$ for all ${i}$ which implies ${X_{1}, X_{2}, ..., X_{n}}$ are independent.

We are interested in finding the distribution of the first passage time to a point ${a\in\mathbb{Z}}$ , denoted by ${T_{a}:=\mathrm{inf}\left\{n\ge 1| X_{n}=a\right\}}$ . Namely, we want to find the probability measure assigned to the event ${\left\{T_{a}=n\right\}}$ . We note that ${\left\{T_{a}=n\right\}=\left\{T_{a}>n-1\right\}\cap\left\{S_{n}=a\right\}=\left\{T_{a}>n-1\right\}\cap\left\{S_{n}=a-1\right\}\cap\left\{X_{n}=1\right\}}$ where the last equality follows from the fact that when the first passage time to ${a}$ is greater then ${n-1}$ , the walk reaches ${a}$ at time ${n}$ if and only if it moves up at step ${n-1}$ from ${a-1}$ , so

$\displaystyle \mathbb{P}(T_{a}=n)=\mathbb{P}(T_{a}>n-1\&S_{n}=a) = p\cdot\mathbb{P}(T_{a}>n-1 \& S_{n-1}=a-1)$

Here in the last equality we use the independence between ${\left\{X_{n}=1\right\}}$ and ${\left\{S_{n-1}=a-1\right\}}$ . Hence the problem now is reduced to finding the distribution of ${\left\{T_{a}>n-1 \& S_{n-1}=a-1\right\}}$ . In order to do so, recall that for any particular path reaching ${a-1}$ at time ${n-1}$ , its probability is ${p^{\frac{n+a}{2}-1}(1-p)^{\frac{n-a}{2}}}$ . Then if we are able to count the number of all paths which reach ${a-1}$ at time ${n-1}$ and never pass ${a}$ at all previous steps, i.e. ${T_{a}>n-1}$ , then the problem is solved. Denote the number of all paths by ${N(n,a)}$ . We have the probability

$\displaystyle \mathbb{P}(T_{a}=n)= p\cdot N(n,a)p^{\frac{n+a}{2}-1}(1-p)^{\frac{n-a}{2}}=N(n,a)p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}$

Note that the number of paths such that ${S_{n-1}=a-1}$ is ${\binom{n-1}{\frac{n+a}{2}-1}}$ . Now we look at the number of paths such that ${S_{n-1}=a-1}$ and ${S_{i}\ge a}$ for some ${1\leq i\leq n-1}$ , ${N^{c}(n,a)}$ . Observe that we have ${\binom{n-1}{\frac{n+a}{2}-1}=N(n,a)+N^{c}(n,a)}$ , so ${N(n,a)= \binom{n-1}{\frac{n+a}{2}-1}-N^{c}(n,a)}$ . To compute ${N^{c}(n,a)}$ is a rather easy task where we are going to employ an elegent argument, the reflection principle. Notice that for any particular path such that ${S_{n-1}=a-1}$ and ${S_{i}\ge a}$ , the walk has passed ${a}$ for some time. Look at the first time it reaches ${a}$ , and denote it by ${\ell}$ . Then we reflect the walk by the following: ${\hat{S}_{i}=S_{i}}$ for ${1\leq i\leq \ell}$ and ${\hat{S}_{i}=2a-S_{i}}$ for ${\ell\leq i\leq n-1}$ . The reflection comes from ${2a-S_{i}}$ which equals ${a}$ plus the distance between ${a}$ and ${S_{i}}$ , i.e. ${a-S_{i}}$ . Note that there must exist a bijection between the original walk and the reflected walk. In fact, the reflecting process is itself the bijection since if we reflect any walk twice we get the identity. Hence the number of original paths must equal to the number of reflected paths. It is fairly easy to compute the latter. The latter is just the set of paths such that ${S_{i}\ge a}$ for some ${1\leq i\leq n-1}$ and ${S_{n-1}=2a-(a-1)=a+1}$ . Then, we don’t really need the condition ${S_{i}\ge a}$ for some ${1\leq i\leq n-1}$ as ${S_{n-1}=a+1}$ . Therefore, it is just the set of paths such that ${S_{n-1}=a+1}$ which we already how to count. There are ${\binom{n-1}{\frac{n+a}{2}}}$ of them. So

$\displaystyle N^{c}(n,a)=\binom{n-1}{\frac{n+a}{2}}$

Finally, we have

$\displaystyle \begin{array}{lll} \mathbb{P}(T_{a}=n) & = & N(n,a)p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}\\ & = & \left[\binom{n-1}{\frac{n+a}{2}-1}-\binom{n-1}{\frac{n+a}{2}}\right]p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}\\ &=& \frac{a}{n}\binom{n}{\frac{n+a}{2}}p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}} \\ &=& \frac{a}{n}\mathbb{P}(S_{n}=a) \end{array}$

Some Math