Random Walk (1): Reflection Principle
by tzy9393
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