Random Walks
Charles N. Moore Department of Mathematics, Kansas State University Manhattan, KS 66506 U.S.A.

Abstract. We discuss the classical theorem of P´lya on random walks on the integer lattice in o Euclidean space. This is the starting point for much work that has been done on random walks in other settings. We mention a tiny fraction of this work, and discuss in detail “random walks” which can be created using trigonometric functions.

1

P´lya’s Theorem o

Consider the integers {. . . , −2, −1, 0, 1, 2, . . . }. Suppose you are standing at 0. Flip a coin. If the coin comes up heads, move to the right by one step. If it comes up tails, move to the left by one step. Flip the coin again. If it comes up heads, move a step to the right, if it comes up tails, move a step to the left. Repeat and continue this process. Must you come back to zero? Obviously, there is a very good chance of returning to zero: the first two flips could have been head then tail, or tail then head, and these both result in a return to zero. So of the four possible outcomes in the first two flips, half of these take you back to zero. So the probability of returning to zero is at least 1 2 . If you further consider that even if you fail to return to zero in two steps, that after some subsequent flips you might make it back to zero, then clearly the probability of returning to zero is greater than 1 . A natural question arises: 2 What is the probability of returning to zero? The answer was given by Georg P´lya [9] in 1921: o Theorem 1. With probability one, the random walker will return to zero in a finite number of steps. Let us show how to prove P´lya’s theorem. For n = 0, 1, 2, 3, . . . let un = o the probability that the random walker is at 0 after n steps. We make two Figure 1: Georg o simple observations: u0 = 1 (because the walker starts at 0) and un = 0 if P´lya n = 1, 3, 5, 7, . . . , that is, the walker cannot be at 0 after an odd number of steps. For n = 1, 2, 3, . . . , set fn = the probability that the walker returns to 0 for the first time at step n. Set f0 = 0 (being at 0 at step 0 isn’t really a return) and f =
∞

fn . The probability that the

walker returns to 0 is f , the probability of not returning is 1 − f. We now decompose the event that the walker is at 0 at time n, n ≥ 1, into first returns, that is, if the walker is at 0 at time n, then the walker may be back there for the first time or may have

n=0

1

already visited there previously. This gives the relations: u1 = f 0 u1 + f 1 u0 u2 = f 0 u2 + f 1 u1 + f 2 u0 . . . un = f0 un + f1 un−1 + f2 un−2 + · · · + fk un−k + · · · + fn u0 . For example, in the expression for un , the term fk un−k represents the probability that the walker returned to 0 for the first time after k steps and then returned to 0 in n − k more steps. Set U (s) = u0 + u1 s + u2 s2 + . . . and Then U (s)F (s) = u0 f0 + (u0 f1 + u1 f0 )s + (f0 u2 + f1 u1 + f2 u0 )s2 + · · · = U (s) − 1. Lemma 1. If If
∞ n=0 ∞ n=0

F (s) = f0 + f1 s + f2 s2 + . . .

un = ∞ then the probability of returning to 0 is one.

un < ∞ then there is a positive probability of not returning to 0.
N

Proof. Notice that for any N , n=0 un ≤ lim U (s) so if s 1 ∞ n=0

∞ n=0

un = ∞, then lims s 1

1 U (s)

= ∞ and given

the relation U (s)(1 − F (s)) = 1 this forces f = On the other hand, if U (s)(1 − F (s)) = 1 forces
∞ n=0 ∞ n=0 s

fn = lim F (s) = 1.
∞ n=0

un < ∞, then lim U (s) =
1 s 1

un < ∞, which, due to the relation

fn = lim F (s) < 1.

∞ Thus, to determine if our walker returns, we need to compute n=0 un = ∞ u2n . (Recall n=0 un = 0 if n is odd.) If this sum is infinite, the walker returns with probability one, if the sum is finite, there is a positive probability of the walker not returning. Let’s compute u2n . In the first 2n steps, there are a total of 22n different routes which could be taken, each equally likely. How many of these come back to 0? This is a basic combinatorics question. Think of two urns, one labeled left and one labeled right. We want to distribute 2n balls, labeled 1, 2, 3, . . . , 2n (corresponding to the step number) into these two urns. There are 2n ways k to distribute k into one urn and 2n − k into the other; of interest here is the number of ways to put n balls into the urn labeled “left” and n into the urn labeled “right”. Any such distribution of balls corresponds to a route of length 2n which comes back to 0. Thus, there are 2n routes which n lead back to 0. Consequently,

u2n = To get an estimate of u2n we need

2n n 22n

2

Lemma 2. (Stirling’s formula; see e.g. Feller [7] ) As n → ∞, n! ≈ With this estimate, when n is large, u2n Therefore,
∞ n=0 u2n

√ 1 2πnn+ 2 e−n .

√ 1 1 (2n)! 1 2π(2n)2n+ 2 e−2n 1 ≈ √ =√ = n+ 1 −n 2 22n (n!)2 22n πn ( 2πn 2 e )

= ∞ so by Lemma 1, the walker returns with probability one.

2

Many possible directions

P´lya [9] also considered random walks in higher dimensions. Consider the integer lattice in two o dimensional Euclidean space, that is, consider those points with integer coordinates. Start at (0, 0), and toss two coins to determine whether to make a step to either (1, 0), (−1, 0), (0, 1) or (0, −1). Repeat, going one more step, either up, down, left or right, with equal probability. The same question can now be asked: What is the probability this walker returns to (0, 0)? An examination of the proof given in the previous section reveals that the analysis up through Lemma 1 was in no way dependent on the fact that walker was walking in one dimension; this fact only entered into the proof with the computation of u2n . With only slightly more complicated c combinatorics, and again using Stirling’s formula, one can compute that in dimension two, u 2n ≈ n , ∞ as n → ∞, for some constant c. Since then n=0 u2n = ∞, Lemma 1 implies that the walker returns with probability one. The situation changes in dimension three. Here, after some combinatorics and computation, it 3 turns out that u2n ≈ Cn− 2 so that by Lemma 1, there is a positive probability of the walker not returning to the origin. P´lya also showed that this is the case in any dimension greater than or o equal to three. A very drunken man staggers so as to simulate a random walk. Thus, P´lya’s theorem implies o that if he staggers out of a bar into a very narrow long alley, he will certainly return to the door of the bar. Similarly, if he finds himself in the middle of a large plaza, he will eventually stagger and return, with probability one, to the center of the plaza. Birds, however, should be cautioned against drunken behavior, as a drunken bird has a positive probability of not returning to the nest. The walks we’ve discussed above are called symmetric random walks because at each step, each of the possible directions to go was equally likely. Going back to dimension one, let’s consider the situation where we use a weighted coin to determine the direction of travel. This coin has probability p of turning up heads (so that the walker goes right) and probability 1 − p of turning up tails. To determine if a walker using this coin returns to 0, we reason as before and compute u2n . As before, a random walk returns to zero if there are as many steps to the left as to the right, so that u2n = pn (1 − p)n 2n . Here again we may use Stirling’s formula to obtain: n u2n = p (1 − n (2n)! p)n (n!)2

≈ p (1 − p)

n

n

√

2π(2n)2n+ 2 e−2n 1 = (4p(1 − p))n √ . √ 1 πn ( 2πnn+ 2 e−n )2

1

If p = 1 then 4p(1 − p) < 1, hence ∞ u2n < ∞ and by Lemma 1, there is a positive probability n=0 2 of the walker not returning to 0. In fact, 4p(1 − p) < 1 exactly when p = 1 and so ∞ u2n n=0 2 1 converges if and only if p = 2 . Thus, the walker returns to the origin with probability one if and only if p = 1 . This is not surprising– a gambler who continually plays a game with the odds against 2 him can expect to eventually lose his initial stake.

3

Other lattices may be considered. Our walker could start at the vertex of a hexagonal lattice in R2 . At each step there are three possible directions to go; we could consider a walk where each of these directions is equally likely (it can be shown the walker will return) or a walk where these are not. In fact, we could consider a walk on any lattice, regular or not, in Euclidean space, and ask the same questions. See P. G. Doyle and J. L. Snell [5] for a detailed study of random walks on lattices in Rn as well as an excellent exposition of the connection between random walks and the theory of electrical networks. Another possibility is to consider a sequence of identically distributed independent random variables X1 , X2 , X3 , . . . . Setting S1 = X1 , S2 = X1 + X2 , S3 = X1 + X2 + X3 , . . . we may ask about {Sn (ω)} for points ω in the underlying Figure 2: Hexagprobability space. Here the Xi may take on discrete values or may take values onal lattice in R. In the first case, this allows, say, for walks on an integer lattice in which the walker may jump several steps in a single move. In the case where the Xi take values in R the walker may never get back exactly to 0, but we can ask if he gets arbitrarily close. See K. L. Chung [4] for a treatment of random walks in this generality. Consider a group G with a subset S which generates G. Assume S has the property that s ∈ S implies s−1 ∈ S. The Cayley graph of G is constructed with vertices the elements of G and an edge from x to y if and only if there exists an element s ∈ S such that x = sy. Thus, the Cayley graph depends on G and the generating set S (which is not unique). A walker starts from a vertex of this graph, and at each stage, takes a step along an adjacent edge, chosen uniformly from among the adjacent edges with equal probability. What is the probability the walker returns to the starting point?

3

Return to P´lya’s theorem; trigonometric walks o

Consider the function f (x) = 1 −1 if x ∈ [0, 1 ) 2 if x ∈ [ 1 , 1) 2

Extend this to a 1-periodic function on the real line, and continue to call this extension f. Now consider the functions f (x), f (2x), f (4x), . . . , f (2n x), . . . , restrict these to the interval [0, 1) and call the resulting functions r1 (x), r2 (x), r3 (x), . . . , rn (x), . . . . These are called the Rademacher functions, after Hans Rademacher who introduced these in a paper in 1922. With the possible exception of x which are dyadic points, that is, points of the form x = 2jn , where n = 1, 2, 3, . . . , j ∈ {0, 1, . . . , 2n } we may write rn (x) = sgn(sin(2n πx)) where sgn is defined as sgn(x) = 1 if x ≥ 0 and sgn(x) = −1 if x < 0. (The set of dyadic points is countable, hence of measure zero, and therefore negligible for our purposes. So we could define the rn either way and obtain the same results.) Set s0 (x) = 0, s1 (x) = r1 (x), s2 (x) = r1 (x) + r2 (x), s3 (x) = r1 (x) + r2 (x) + r3 (x), etc. 1 Take x ∈ [0, 1). If x ∈ [0, 1 ) then s1 (x) = 1, if x ∈ [ 2 , 1), then s1 (x) = −1. So for half the 2 x s in [0, 1), s1 (x) takes the value 1, and for half it takes the value −1. Now if x ∈ [0, 1 ), then 4 1 1 s2 (x) = r1 (x)+r2 (x) = 1+1 = 2; if x ∈ [ 4 , 2 ) then s2 (x) = r1 (x)+r2 (x) = 1+−1 = 0; if x ∈ [ 1 , 3 ), 2 4 then s2 (x) = r1 (x) + r2 (x) = −1 + 1 = 0; if x ∈ [ 3 , 1) then s2 (x) = r1 (x) + r2 (x) = −1 + −1 = −2. 4 Each of these four cases, occurring on exactly one-fourth of the unit interval, corresponds to the first two steps of a random walk. Continuing in this way, we have created a model of P´lya’s random o walk on the integers: There is a 1-1 correspondence between {x ∈ [0, 1)| x is not of the form 2jn } 4

and the set of random walks, where x corresponds to the random walk {s n (x)}∞ . In fact, if you n=1 express such an x ∈ [0, 1) in binary and change all the 1 s in the binary representation to −1 s and all the 0 s to 1 s, then sn (x) is just the sum of the first n digits of this string of −1 s and 1 s.
1
1
1

0.5

0.5

0.5

0

0

0

0.25

0.5

0.75

1
-0.5

0

0.25

0.5

0.75

1

0

0

0.25

0.5

0.75

1

-0.5

-0.5

-1

-1

-1

Figure 3: The functions r1 (x), r2 (x) and r3 (x). Thinking in this way, we can rephrase P´lya’s theorem: o Theorem 2. For a.e. x ∈ [0, 1), the sequence sn (x), n = 1, 2, 3, . . . returns to 0 in a finite number of steps. Actually, a little more can be said. Given any integer m, it can be shown that with probability one, the walker will land on m in a finite number of steps. Thinking now of m as a starting point, then with probability one, the walker will return to this position in a finite number of steps. Once the walker has returned, there is no memory of the past, so now the situation is as if the walker is starting for the first time. So with probability one, the walker returns again to m. This continues and consequently, we may conclude: Theorem 3. For a.e. x ∈ [0, 1), the sequence sn (x), n = 1, 2, 3, . . . visits every integer an infinite number of times. Now consider the interval [−π, π] and the functions sin(x), sin(2x), sin(4x), . . . , sin(2 n x), . . . and the sums s1 (x) = sin(x), s2 (x) = sin(x) + sin(2x), s3 (x) = sin(x) + sin(2x) + sin(4x), . . . , n sn (x) = j=1 sin(2j−1 x), . . . .
1 0.5 0 -0.5 -1 1 0.5 0 -0.5 -1 1 0.5 0 -0.5 -1

-3.14

-1.57

0

1.57

3.14

-3.14

-1.57

0

1.57

3.14

-3.14

-1.57

0

1.57

3.14

Figure 4: The functions sin(x), sin(2x), and sin(4x) on [−π, π]. Given the resemblance of each of the functions sin(2n x) to rn (x), it seems natural to investigate the “random walks” {sn (x)}∞ for x ∈ [−π, π]. Here of course, sums of the rn (x) will always be n=1 integer valued, whereas sums of the sin(2n x) certainly are not. And certainly, for any fixed x, the sequence {sn (x)} is countable, so it could not visit every element in an uncountable set such as the real numbers. The correct analogue to Theorem 3 is that it visits every neighborhood of every point an infinite number of times, or what is equivalent, the sequence {sn (x)} is dense in R. In fact, we can be a little more general: 5

Theorem 4. (Grubb and Moore [8].) Let n sn (x) = j=1 aj sin(nj x + θj )

where the aj , θj , are real, |aj | ≤ 1 for every j and the nj are positive integers which satisfy nj+1 |aj |2 = ∞. Then for a.e. x ∈ [−π, π], {sn (x)} is dense in R. nj ≥ λ > 1. Suppose also that It is easy to verify that the sequence s1 (x) = sin(x), s2 (x) = sin(x) + sin(2x), . . . discussed above satisfies the hypotheses of this theorem. Note that we must have |aj |2 = ∞; otherwise, the sequence of functions {sn (x)} converges in L2 and couldn’t satisfy the conclusion. Previously, D. Ullrich [14] had shown this result under the assumption that |aj | = 1 for every j and the proof of Theorem 4 (which we describe below) borrows many ideas from his work. Series of the form ∞ aj z nj where nj+1 /nj ≥ λ > 1, or their real counterparts such as in j=0 Theorem 4, are called lacunary series, gap series, or often Hadamard series. They arise in the study j of analytic continuation: for example, the series ∞ z 2 represents an analytic function on the j=0 unit disk which cannot be extended to an analytic function on any larger domain. They are also of interest due to the fact, evidenced by this theorem among many others, that the partial sums n nj behave like sums of independent random variables (which they are not). In particular, j=0 aj z we mention here the central limit theorems for lacunary trigonometric series of R. Salem and A. Zygmund [11], the central limit theorem of P. Erd¨s and I. S. G´l [6] and the laws of the iterated o a logarithm of Salem and Zygmund [12] and M. Weiss [15]. The proof of Theorem 4 is not difficult. A theorem due to Zygmund [16], vol. 1, p. 205 shows that the set of x where the sequence {sn (x)} is bounded above or below is of measure zero. Thus, fixing an α ∈ R and an x at which {sn (x)} bounded neither above nor below, then for an infinite number of n (which depend on x) we must have sn (x) on one side of the real number α and sn+1 (x) on the other; that is, in the real line the sequence sn (x) crosses α an infinite number of times. With a little more work it can then be shown that sn (x) must visit any neighborhood of α an infinite number of times. See [8] for details. What about such “trigonometric random walks” in higher dimensions? In analogy to P´lya’s o theorem in two dimensions, we could consider n sn (θ) = k=1 ak eink θ

nk+1 ≥ λ > 1, ak ∈ C, and θ ∈ R. (If each nk is an integer, each sn (θ) is 2πnk periodic, so it suffices to consider θ ∈ [−π, π].) Fix a θ. Each term, ak eink θ can be thought of as a vector, so that s1 (θ) = a1 ein1 θ represents one step of a random walk in C, s2 (x) = a1 ein1 θ + a2 ein2 θ represents two steps of a random walk, etc. Two important results concerning such random walks are due to J.M. Anderson and L. Pitt [1], [2]. To discuss these we make some definitions. Let ε > 0 be fixed, θ ∈ R and suppose that for each z∈C lim inf |sn (θ) − z| ≤ ε. where, as above, n→∞ In this case we say {sn (θ)} is ε-recurrent. If {sn (θ)} is ε-recurrent for almost all θ then we say {sn } is ε-recurrent. If {sn } is ε-recurrent for each ε > 0 we say that {sn } is recurrent.

6

Theorem 5. (Anderson and Pitt [1].) Suppose {λk }∞ is a sequence of positive numbers such that 1 λk+1 ∞ is a sequence of complex numbers satisfying {a } ≥ q > 1 for all k. Suppose {ak }k=1 k ∞ ≡ λk n 2q ∞ ak eiλk θ . Then for ε ≥ {ak } ∞ the sesupk |ak | < ∞ and k=1 |ak |2 = ∞. Set sn (θ) = q−1 k=1 quence {sn } is ε-recurrent. The proof uses tools from complex analysis. For certain types of sums, more can be said: n Theorem 6. (Anderson and Pitt [2].) Let sn (θ) = is recurrent. k=1 eia

kθ

where a ≥ 2 is an integer. Then {sn }

The proof of this is difficult and requires complex analysis, probability and number theory. None of the theorems 4, 5, 6 can be shown to be best possible, most likely because they probably are not the best possible. In [3] J. Bretagnolle and D. Dacunha-Castelle present an extensive study of random walks created from sums of independent random variables. Consider partial sums n sn (ω) = k=1 ak Xk (ω) where the Xk are real-valued independent identically distributed mean zero random variables. The hypotheses of their results are too numerous to mention explicitly, but they make several assumptions on the distribution of Xk and several technical assumptions of the 1 n 2 2 → ∞, they show recurrence occurs ak . Then, under these assumptions, and if σn = k=1 ak precisely when ∞ σ1 = ∞. (Of course, one needs to be precise about what recurrence means n=1 n here: if the Xk are integer valued and the ak are integers, then recurrence could only occur in the integers; if the Xk are real valued then recurrence could be in the reals or in some other subgroup of the reals.) Here’s a very rough sketch of the proof: By using the central limit theorem, they c obtain the estimate Prob(sn ∈ I) = σI + o( σ1 ), where I ⊂ R is any interval, and cI is a constant n n depending only on I. The proof is completed by the Borel-Cantelli lemma (actually variations of this) and other fairly standard techniques. Reasoning in this way gives an idea as to what the correct version of Theorems 4, 5 and 6 should be in the trigonometric case, but it won’t give us a proof. Sequences of functions such as {sin(2k x)} or {eiλk θ } are not independent random variables, yet as amply illustrated by many theorems, they do behave much like sequences of random variables. Consider, for example, series of
1 the form sn (θ) = n ak sin(2k−1 θ), where the ak are real. Set σn = 2 n a2 2 and suppose k=1 k=1 k σn that an = o( log log σn ) as n → ∞. Under these hypotheses the central limit theorem for lacunary s trigonometric series of Salem and Zygmund [11] states that the distribution function of σn tends n to that of a Gaussian with mean zero and variance one. That is, as n → ∞,
1

m {θ ∈ [−π, π] :

sn (θ) < λ} σn

1 →√ 2π

λ

e
−∞

−t2 2

dt,
2

where m denotes the probability measure dθ/2π on [−π, π].
2ε √ . 2π s So by this central limit theorem, if ε > 0, and n is large, then Prob(| σn | < ε) ≈ n

Replace ε in this last equation by

ε σn

√1 2π

ε −t 2 ε e

- this is, of course, quite incorrect, as the choice of n

dt ≈

large depends on ε. Assuming such a step were correct, we would obtain Prob(|s n | < ε) ≈ which is analogous to the estimate of Bretagnolle and Dacunha-Castelle above. Then, 2ε Prob (|sn | < ε) ≈ √ 2π n=1 7
∞ ∞ n=1

√2 ε , 2π σn

1 , σn

so that if ∞ σ1 < ∞, then the so-called easy half of the Borel-Cantelli lemma (see e.g. Feller [7], n=1 n Volume 1, Chapter VIII, section 3) implies that for a.e. x eventually |sn | > ε, so that recurrence doesn’t occur in any neighborhood of 0. Similar reasoning could then be used to show that recurrence doesn’t occur at any point of R. If, in addition, the functions sin(2k x) were independent (which is another false assumption) then the Borel-Cantelli lemma (the so-called harder half) would imply that if ∞ σ1 = ∞ then a.e. x is in an infinite number of the sets {|sn | < ε}, that is, recurrence n=1 n occurs at 0. Again, similar reasoning could be applied to show that there is recurrence at any point of R. Of course, this is all specious reasoning, but yet it seems to lead to some central issues, and gives an indication what conjectures to pose. So in the case of trigonometric random walks, there is still much work to be done. Thus, despite the fact there are already thousands of papers and dozens of books written on random walks, there are still many directions left to go.

References
[1] Anderson, J. M., and Pitt, Loren D., On recurrence properties of certain lacunary series. I. General results., J. Reine Angew. Math. 377 (1987), 65–82. [2] Anderson J. M. and Pitt, L. D., On recurrence properties of certain lacunary series. II. The series n exp(iak θ), J. Reine Angew. Math. 377 (1987), 83–96. k=1 [3] Bretagnolle, Jean, and Dacunha-Castelle, Didier, Th´or´mes limites a distance finie pour e e ´ les marches al´atoires, Ann. Inst. H. Poincar´ (1968), 25-73. e e [4] Chung, Kai, Lai, A Course in Probability Theory, Academic Press, New York, 1974. [5] Doyle, Peter G., and Snell, J. Laurie, Random walks and electric networks, Carus Mathematical Monographs, 22, Mathematical Association of America, Washington, DC, 1984. [6] Erd¨s, P., and G´l, I.S., On the law of the iterated logarithm, I,II, Nederl. Akad. Wetensch. o a Proc. Ser. A 58 (1955), 65-84. [7] Feller, William, An Introduction to Probability Theory and Its Applications, Volumes I and II, John Wiley and Sons, New York, 1950, 1966. [8] Grubb, D. J., and Moore, Charles N., Certain lacunary cosine series are recurrent, Studia Math. 108 (1994), no. 1, 21–23. ¨ [9] P´lya, Georg, Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt o im Strassennetz, Math. Ann. 84, 149-160, 1921. [10] Rudnick, Joseph, and Gaspari, George, Elements of the Random Walk, Cambridge University Press, Cambridge, 2004. [11] Salem, R. and Zygmund, A., On lacunary trigonometric series, Proc. N.A.S. 33 (1947), 333-338. [12] Salem, R., and Zygmund A., La loi du logarithme it´r´ pour les s´ries trigonom´triques e e e e lacunaire, Bull. Sci. Math. 74 (1950), 209-224. [13] Spitzer, Frank, Principles of Random Walk, Second Edition, Springer-Verlag, New York, 1976. 8

[14] Ullrich, David C., Recurrence for lacunary cosine series, The Madison Symposium on Complex Analysis, Contemporary Math. 137 (1992), 459-467. [15] Weiss, Mary, The law of the iterated logarithm for lacunary series, Trans. Amer. Math. Soc. 91 (1959), 444-469. [16] Zygmund, Antoni, Trigonometric Series, Cambridge University Press, Cambridge, 1959. email address: cnmoore@math.ksu.edu

9