Random walks. I
Donald S. Ornstein · Transactions of the American Mathematical Society · 1969
By a random walk we will mean sums of independent, identically distributed random variables.Recently Spitzer discovered a class of limit theorems for random walks on the integers (or the points with integer coordinates in Euclidean space) and important contributions to this theory were made later by Kesten.The original work was motivated to a great extent by potential theory.However if we look at the results solely from the point of view of probability theory, they are of very great interest because they are the first theorems to be discovered that are natural, deep, and hold for any random walk on the integers.This is very much in keeping with the original spirit of probability theory which tries to make precise statements about the outcome of an experiment with a minimum of knowledge about its mechanism.The purpose of this paper is to generalize some of these theorems to random walks on the line and to introduce some new methods in the case of the integers.We will restrict ourselves to the line although everything works in higher dimensions and the proofs even simplify considerably.From here on when we speak of a random walk on the line we will assume that it is nonarithmetic, i.e., it does not live on an arithmetic progression containing 0.(A) Let hx{A, B) be the probability of hitting A before B starting at x.If A and B are finite intervals, then lim*.,«,hx{A, B) and limx__M hx{A, B) exists.The above theorem implies that the distribution of the first hit in an interval tends to a limit as the starting point tends to +00 or -00 and this distribution can be shown to be nonsingular with respect to Lebesgue measure.In the transient case this is essentially the Blackwell-Feller-Orey renewal theorem.[hx{A, B) + hx{B, A) = hx{A u B, ).This and the nonsingularity of the distribution of the first hit gives us that the expected number of times we hit the interval {x, x+1) starting at 0 tends to a limit as x -> 00 and x -> -00].We get a variant of (A) by "reversing" the walk, namely: Let HX{A, B) be the expected number of times we hit A before hitting B, starting at x.If A and B are finite intervals, then lim^ ± M HX{A +y, B) both exist.This is also analogous to the renewal theorem which states (in our terminology): limî/_±œ Hx{A+y,) both exist.Our method gives a new proof of (A) in the integer case and of the renewal theorem in this transient case.The essential ideas in the proof of (A) are contained in §1 where we prove a slightly weaker theorem.§2 contains a proof of (A) and also a proof of the variant mentioned above.