Chapter 9RANDOM WALKS, LARGEDEVIATIONS, ANDMARTINGALES9.1 IntroductionDefinition 9.1.1. Let {Xi; i  1} be a sequence of IID random variables, and let Sn=X1+ X2+ ··· + Xn. The integer-time stochastic process {Sn; n  1} is called a randomwalk, or, more precisely, the one-dimensional random walk based on {Xi; i  1}.For any given n, Snis simply a sum of IID random variables, but here the behavior ofthe entire random walk process, {Sn; n  1}, is of interest. Thus, for a given real number↵ > 0, we might want to find the probability that the sequence {Sn; n  1} contains anyterm for which Sn ↵ (i.e., that a threshold at ↵ is crossed) or to find the distribution ofthe smallest n for which Sn ↵.We know that Sn/n essentially tends to E [X] = X as n ! 1. Thus if X < 0, Snwill tendto drift downward and if X > 0, Snwill tend to drift upward. This means that the resultsto be obtained depend critically on whether X < 0, X > 0, or X = 0. Since results forX > 0 can be easily found from results for X < 0 by considering {Sn; n  1}, we usuallyfocus on the case X < 0.As one might expect, both the results and the techniques have a very di↵erent flavor whenX = 0, since then Sn/n essentially tends to 0 and we will see that the random walk typicallywanders around in a rather aimless fashion.1With increasing n, Snincreases aspn (forX both zero mean and non-zero mean), and this is often called di↵usion.21When X is very close to 0, its behavior for small n resembles that for X = 0, but for large enough nthe drift becomes significant, and this is reflected in the major results.2If we view Snas our winnings in a zero-mean game, the fact that Sn/n ! 0 makes it easy to imaginethat a run of bad luck will probably be followed by a run of good luck. However, this is a fallacy, since theXnare assumed to be independent. Adjusting one’s intuition to understand this at a gut level should beone of the reader’s goals in this chapter.421422 CHAPTER 9. RANDOM WALKS, LARGE DEVIATIONS, AND MARTINGALESThe following three subsections discuss three special cases of random walks. The first two,simple random walks and integer random walks, will be useful throughout as examples,since they can be easily visualized and analyzed. The third special case is that of renewalprocesses, which we have already studied and which will provide additional insight into thegeneral study of random walks.After this, Section 9.2 shows how a major application area, G/G/1 queues, can be viewed interms of random walks. This section also show why questions related to threshold crossingsare so important in random walks.Section 9.3 then develops the theory of threshold crossings for general random walks andSection 9.4 extends and in many ways simplifies these results through the use of stoppingrules and a powerful generalization of Wald’s equality known as Wald’s identity.The remainder of the chapter is devoted to a rather general type of stochastic process calledmartingales. The topic of martingales is both a subject of interest in its own right and alsoa tool that provides additional insight into random walks, laws of large numbers, and otherbasic topics in probability and stochastic processes.9.1.1 Simple random walksSuppose X1, X2, . . . are IID binary random variables, each taking on the value 1 withprobability p and 1 with probability q = 1 p. Letting Sn= X1+ ···+ Xn, the sequenceof sums {Sn; n  1}, is called a simple random walk. Note that Snis the di↵erence betweenpositive and negative occurrences in the first n trials, and thus a simple random walk islittle more than a notational variation on a Bernoulli process. For the Bernoulli process, Xtakes on the values 1 and 0, whereas for a simple random walk X takes on the values 1 and-1. For the random walk, if Xm= 1 for m out of n trials, then Sn= 2m  n, andPr{Sn= 2m  n} =n!m!(n  m)!pm(1 p)nm. (9.1)This distribution allows us to answer questions about Snfor any given n, but it is not veryhelpful in answering such questions as the following: for any given integer k > 0, what isthe probability that the sequence S1, S2, . . . ever reaches or exceeds k? This probability canbe expressed as3Pr{S1n=1{Sn k}} and is referred to as the probability that the randomwalk crosses a threshold at k. Exercise 9.1 demonstrates the surprisingly simple result thatfor a simple random walk with p  1/2, this threshold crossing probability isPr(1[n=1{Sn k})=✓p1 p◆k. (9.2)3This same probability is often expressed as as Prsupn1Sn k . For a general random walk, theeventSn1{Sn k } is slightly di↵erent from supn1Sn k , since supn1Sn k can include samplesequences s1, s2, . . . in which a subsequence of values snapproach k as a limit but never quite reach k. Thisis impossible for a simple random walk since all skmust be integers. It is possible, but can be shown tohave probability zero, for general random walks. It is simpler to avoid this unimportant issue by not usingthe sup notation to refer to threshold crossings.9.2. THE QUEUEING DELAY IN A G/G/1 QUEUE: 423Sections 9.3 and 9.4 treat this same question for general random walks, but the results arefar less simple. They also treat questions such as the overshoot given a threshold crossing,the time at which the threshold is crossed given that it is crossed, and the probability ofcrossing such a positive threshold before crossing any given negative threshold.9.1.2 Integer-valued random walksSuppose next that X1, X2, . . . are arbitrary IID integer-valued random variables. We canagain ask for the probability that such an integer-valued random walk crosses a thresholdat k, i.e., that the eventS1n=1{Sn k} occurs, but the question is considerably harderthan for simple random walks. Since this random walk takes on only integer values, it canbe represented as a Markov chain with the set of integers forming the state space. In theMarkov chain representation, threshold crossing problems are first passage-time problems.These problems can be attacked by the Markov chain tools we already know, but thespecial structure of the random walk provides new approaches and simplifications that willbe explained in Sections 9.3 and 9.4.9.1.3 Renewal processes as special cases of random walksIf X1, X2, . . . are IID positive random variables, then {Sn; n  1} is both a special caseof a random walk and also the sequence of arrival epochs of a renewal counting pro cess,{N(t);