Random Walk (1): Reflection Principle
Consider a simple random walk on with for all which implies are independent.
We are interested in finding the distribution of the first passage time to a point , denoted by . Namely, we want to find the probability measure assigned to the event . We note that where the last equality follows from the fact that when the first passage time to is greater then , the walk reaches at time if and only if it moves up at step from , so
Here in the last equality we use the independence between and . Hence the problem now is reduced to finding the distribution of . In order to do so, recall that for any particular path reaching at time , its probability is . Then if we are able to count the number of all paths which reach at time and never pass at all previous steps, i.e. , then the problem is solved. Denote the number of all paths by . We have the probability
Note that the number of paths such that is . Now we look at the number of paths such that and for some ,. Observe that we have , so . To compute 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 and , the walk has passed for some time. Look at the first time it reaches , and denote it by . Then we reflect the walk by the following: for and for . The reflection comes from which equals plus the distance between and , i.e. . 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 for some and . Then, we don’t really need the condition for some as . Therefore, it is just the set of paths such that which we already how to count. There are of them. So
Finally, we have