AN INTRODUCTION TO RANDOM WALKS

1 AN INTRODUCTION TO RANDOM WALKSDEREK this paper, we investigate simple RANDOM WALKS inn-dimensionalEuclidean Space. We begin by defining simple RANDOM walk ; we give particularattention to the symmetric RANDOM walk on thed-dimensional integer latticeZd. We proceed to consider returns to the origin, recurrence, the level-crossingphenomenon, and the Gambler s Introduction12. Simple RANDOM walk onZd23. Returns to the Origin24. number of Equalizations onZd85. The Level-Crossing Phenomenon86. Gambler s , a RANDOM walk is a path that is created by some stochastic a simple example, consider a person standing on the integer line who flips a coinand moves one unit to the right if it lands on heads, and one unit to the left if itlands on tails.

2 The path that is created by the RANDOM movements of the walkeris a RANDOM walk . For this paper, the RANDOM WALKS being considered are Markovchains. A Markov chain is any system that observes the Markov property, whichmeans that the conditional probability of being in a future state, given all paststates, is dependent only on the present short, Section 2 formalizes the definition of a simple RANDOM walk on thed-dimensional integer latticeZd, since most of this paper will deal with randomwalks of this sort.

3 Section 3 considers returns to the origin, first returns to theorigin, and the probability of an eventual return to the origin. Section 4 considersthe number of returns to the origin that will occur on a RANDOM walk of infinitelength. Section 5 focuses on the level-crossing phenomenon. Section 6 examinesthe Gambler s Ruin problem, which involves 1-dimensional RANDOM WALKS that haveimposed boundary : August 5th, RANDOM walk onZdConsider thed-dimensional integer latticeZd. Leteidenote thed-dimensionalstandard basis vector with 1 in itsithcoordinate and 0 elsewhere.

4 DefineXjtobe a RANDOM vector with image eifor somei {1,..,d}. AssumeX1,X2,X3,..are independent and identically distributed. Thesimple RANDOM walkofnsteps,denoted bySn, is defined by( )Sn=x+n i= ,xdenotes the position on the lattice at timen= 0, andXjrepresents themovement from timejto timej+ 1. In particular, ifPr(Xi=ei) = Pr(Xi= ei) =12d, i= 1,2,..,d,then the RANDOM walk is other words, on asymmetric simple RANDOM walk , the walker can move oneunit in any one of the 2dpossible directions, and is equally likely to move in anyone direction.

5 Unless otherwise indicated, the initial positionxwill be the originonZd, denoted by to the OriginOne of the earliest questions that arises in the study of RANDOM WALKS concernsthe probability of returning to the initial position. How likely is it for the walkerto return to the origin? We begin by giving a rigorous definition of a return to a simple RANDOM walkSnonZd. A return to the origin,often referred to as anequalization, occurs whenSnequals 0 for somengreater than0. If an infinite number of equalizations occur, then the walk is calledrecurrent.

6 Ifonly a finite number of equalizations occur, then the walk is will first consider a simple RANDOM walk onZ, and develop a number of ideasthat we will generalize for higher dimensions a RANDOM walk onZ,Pr(S2n+1= 0) = 0andPr(S2n= 0) =(2nn)2 second equation follows from the fact that the RANDOM alli, so that each possible path is equally likely, and by the fact that inorder to reach the origin, the walker must take an equal number of positive andnegative steps in each direction [3]. Now we develop some important relationships between first-returns and a RANDOM walk onZ, define the eventf2nto be the event thatthe first equalization occurs at time 2n.

7 That is,f2noccurs ifS2n= 0, andS2k6= 0for allk= 1,..,n 1. For notational convenience, we writePr(f0) = INTRODUCTION TO RANDOM WALKS3 Lemma 1,( )Pr(S2n= 0) =n k=0Pr(f2k)Pr(S2(n k)= 0)Lemma is proved in [4, p. 3]. the collection of paths intonsets, depending on when the firstequalization occurs. Now the number of paths that have the first equalization attime 2kand another equalization at time 2nis given byPr(f2k)22kPr(S2n 2k=0)22n 2k, since it amounts to considering a path that has its first equalization attime 2kfollowed by a path that has an equalization at time 22n 2k.

8 Here we haveused the independence overk= 1,..,n, we have the union of thensets, which gives thetotal number of paths that have an equalization at time 2n. Therefore,Pr(S2n= 0)22n=n k=0Pr(f2k)22kPr(S2n 2k= 0)22n by 22nfinishes the proof. The following lemma establishes a formula forPr(f2n).Lemma 1,( )Pr(f2n) =Pr(S2n= 0)2n 1 Lemma is proved in [4, p. 4]. the functionsS(x) = n=0Pr(S2n= 0)xnF(x) = n=0Pr(f2n)xndefined on the intervalx ( 1,1). Note that the coefficients in the series arein the interval [0,1], so that the sums converge absolutely and the functions arewell-defined.

9 Thus, Lemma shows that( )S(x) = 1 +S(x)F(x)The first term on the right hand side follows from Pr(S0= 0) = 1. Therefore,F(x) =S(x) 1S(x)Note that these manipulations are justified by absolute Lemma and the definition ofS(x), we knowS(x) = n=0(2nn)2 2nxn,which can be rewritten asS(x) = n=0(2nn)(x4) JOHNSTONU sing the Binomial Theorem, it can be shown that n=0(2nn)rn=1 1 4rso thatS(x) =1 1 ,F(x) =S(x) 1S(x)= 1 1S(x)= 1 1 taking the derivitive ofF(x), we obtainF (x) = (1/2)(1 x) 1/2= (1/2)S(x).In order to find the coefficients of the series forF(x), we integrate the series of12S(x).

10 We findPr(f2n) =Pr(S2n 2= 0)2mFinally, it follows from Lemma thatP r(S2n 2=0)2m=P r(S2n=0)(2m 1), which completesthe proof. We are almost ready to investigate equalization probabilties onZd, but beforewe begin, we must acknowledgeStirling s Formula, which states that asn ,n! 2 nn+1/2e nwhere means that the ratio of the two sides tends to 1. We will not derive thisformula here, but a detailed derivation of the formula can be found in Lawler sbook [3, ].Letfd2nbe the event that the first equalization of a RANDOM walk onZdoccursat time 2n.