Simple Random Walk

iid RV

can occur iff

The sequence of is a sample path of the Simple Random Walk

is RW visits at step

where is the number of distinct paths that starts at 0 and end at at time where is the number of distinct paths that starts at 0 and end at at time and stays above axis up to time n-1

Convention: if is not an integer

The method of images

and Then # of paths from to that intersecting the axis= # paths from and

Consider any path from to that intersects the x-axis :=smallest index for which Reflect the segment from A to about the axis to obtain a mirror path from A to . to get a path from to

Corollary

:=p( =0)=

Even where 1st return to 0 occurs after step and

: Fix where does the RW achieve its first max up to time index at which the walk over steps achieve its maximum for 1 sth time Let the even in be for

1. only depends on

2. only depends on

Key Idea

Consider reversed random walk from X_m let

as are iids

if or