New York Journal of Mathematics

New York J. Math. 3A (1998) 81–87.

Perturbed Random Walks and Brownian Motions, and Local Times

Burgess Davis

Abstract. This paper is based on two talks given by the author in the Albany meeting in the summer of 1997. The first of these, which dealt with perturbed Brownian motion and random walk, is discussed in Section 1, and the second, which involved Brownian local times, is the subject of Section 2.

Contents

1. Some Self-interacting Random Walks 81 2. Brownian Local Times 86 References 87

1. Some Self-interacting Random Walks

This section concerns some self-interacting random walks and the continuous processes which are their weak limits. We encountered the random walks as special cases of reinforced random walk, in [4]. To our knowledge, Le Gall was the first person to have thought about the continuous processes, as a limit of some other self-interacting continuous time processes, in the eighties.

These self-interacting random walks are integer valued stochastic processes, 0 = X_{0}, X_{1}, X_{2}, … which satisfy |X_{i+1} − X_{i}| = 1, and which will be defined by giving their transition probabilities P (X_{n+1} = j + 1|X_{i}, i ≤ n, X_{n} = j) and P (X_{n+1} = j − 1|X_{i}, i ≤ n, X_{n} = j). While most processes described by giving their transition probabilities are Markov processes, here these probabilities depend on the entire past, albeit in a very simple way. Let 0 < p < 1, and 0 < q ≤ 1 be the parameters of our walks. The two transition probabilities above are both one half unless n > 0 and either j + 1 has never been visited (that is, does not belong to {X_{i} : i ≤ n}) in which case they are p and 1−p respectively, or j −1 has never been visited, in which case they are q and 1 − q respectively. This process behaves like fair random walk except at all time highs and all time lows. Think of a weird stock market where investors are listless until they hear that an all time high or low has been reached, when at least some of them alter their strategies. When p < 1/2 and q > 1/2,

\begin{matrix}c \\ ◯ \end{matrix}1998 State University of New York ISSN 1076-9803/98

Received December 31, 1997.

Mathematics Subject Classification. 60F05, 60J15, 60J65, 82C41.

Key words and phrases. Reinforced random walk, peturbed Brownian motion.

the process is self-attracting, in that it prefers to jump to integers it has already visited rather than to those it has not visited. Other choices of p and q make it self-repelling. The simplicity of the description of these walks, which will here be called pq-walks, does not carry over to much of their analysis, especially when both p and q are far away from 1/2.

Although the walks studied in this paper are not Markov, it is natural to ask those questions about them which are asked about Markov processes and random walks. Paramount among these questions are whether the processes are recurrent, i.e., do they visit every state infinitely often with probability one, whether they satisfy the strong law of large numbers, and weak convergence, either at fixed times or as a process: a central limit and invariance question respectively, except that the limits will usually not involve the normal distribution. Recurrence and the strong law are relatively easy for pq-walks. If a pq-walk is, say, at a maximum at some time n ≥ 1, it immediately makes a geometric (parameter p) number of consecutive jumps of 1, each to a new maxima, followed by a jump of −1, after which it behaves like a fair random walk until it hits the edge of the already visited integers, whereupon it makes a geometric number of consecutive jumps each to new extrema, and so on. The width of the interval of visited states after the nth geometric variable has been observed is O(n), because all the geometric variables are one of two parameters, either p or 1 − q, and so the chance that the next extrema hit after the nth geometric variable is observed is different (i.e., maxima as opposed to minima) than the one observed during this variable is O(1/n). Once maxima and minima are far apart, the times spent between hitting extrema are close in distribution to the time it takes fair random walk started at 0 to hit 1, which of course has infinite expectation. Elementary arguments based on these considerations prove both recurrence and the strong law.

The proof of weak convergence of X_{n}/\sqrt{n}, as n goes to infinity, where X_{n}, n ≥ 0, is a pq-walk, or more generally weak convergence of the scaled walk to a process, is much more difficult than the proofs of recurrence and the strong law, mirroring the relative difficulties of the proofs of the corresponding results for ordinary fair random walk. Probably no one who thought about this question very long was left with any doubt that weak convergence holds, which indeed it does. This has been shown in two very different ways. For the author, in [5, 6], the approach was first to construct and study the process which seems certain to be the limiting process, and then to use this process and what has been proved about it to establish weak convergence. The other method, of Toth [10, 11], and Toth-Werner [12], is based on occupation times, and shows first the convergence of finite dimensional distributions, etc. While weak convergence is not shown in these papers, it is announced there that it will be in a forthcoming paper, which will deal with a broad range of self-interacting walks. Here we will describe the approach of the author.

The process which is the limit of a scaled pq-walk behaves like Brownian motion except where it is at its maximum, where it gets a push up if p > 1/2 or a push down if p < 1/2, and when it is at its minimum, where it gets a push down if q < 1/2 or a push up if q > 1/2, the extreme case being when q = 1, when the process reflects up at 0. The next order of business is to formulate these push specifications more precisely.

The cases where there is a push at the maximum but not at the minimum are particularly simple to understand, and we treat them first. These “one sided” cases have been under study for quite a while. For an extensive account see Yor [14]. We will be much briefer. Let θ > −1 designate the parameter of our processes. For a continuous function f(t), t ≥ 0, we put f^{∗}(t) = max_{0≤s≤t} f(s). All functions will be continuous and vanish at 0 unless otherwise specified. Let b_{t}, t ≥ 0, be standard Brownian motion started at 0, and define w_{t}, t ≥ 0, by

w_{t} = b_{t} + θb_{t}^{∗}, t ≥ 0. (1_{θ})

Note that w_{t} = w_{t}^{∗} if and only if b_{t} = b_{t}^{∗}, so that the increments of w and of b are exactly the same over intervals on which w does not attain a maximum, while, if θ > 0, w has a larger increment than b over intervals where the maximum of b (or equivalently of w) increases, and if θ < 0, the increment is smaller. Werner [13] has shown that this process is the weak limit of scaled p0-walk, with θ = (2p−1)/(1−p). The proof is not difficult, and is based on the continuous mapping theorem, the continuous function being the one that maps a function f to the function f + θf^{∗}.

Given the success of this approach, it is natural to try to construct the limit of the general candidate limit process in the same way: that is, to define a map from C_{0}[0, ∞) to itself, and then to construct our process by taking the image of a Brownian motion under this map. The situation where there is reflection up at zero of the continuous process — these processes will be the weak limits of p1-walks — illustrates almost all the difficulties faced, and has the advantage of there being only one parameter, which will again be designated θ, to keep track of. For this reason we discuss only this situation until almost the end of the paper. Let θ > −1. Given r ≥ 0 and a function f with f(0) = r, we look for a function (solution) g satisfying

i) g(0) = r
ii) g(t) − g(s) = f(t) − f(s) + θ max_{s≤y≤t}[f(y) − f(s)],
if g(y) > 0, s < y < t and g(s) = g^{∗}(s), and
iii) g(t) − g(s) = f(t) − f(s) − min_{s≤y≤t}[f(y) − f(s)],
if g(y) < g^{∗}(s), s < y < t, and g(s) = 0.

(2_{θ,r})

We are primarily interested in these equations when r = 0, but they are more tractable when r > 0. We are going to use the r > 0 case to study the r = 0 case, an approach pioneered in Le Gall-Yor [8], where these equations were encountered in a study of the windings of three dimensional Brownian motion.

We investigate whether there exist unique solutions of these equations for all functions f. Following Le Gall and Yor, we note that if r > 0, (2_{θ,r}) permits the construction of an obviously unique solution g for any f. For ii) defines g on [0, T_{1}], where T_{1} is the smallest t such that g(t) = 0, and then iii) defines g on [T_{1}, T_{2}], where T_{2} is the smallest t > T_{1} such that g(t) = g^{∗}(T_{1}), and so on. This procedure fails if r = 0, as it is unclear how to get started, for some functions f. However, it is not hard to see that the zero function is the unique solution of (2_{θ,0}) for the zero function, for all θ. And it also is not too hard to show that f + θf^{∗} is the unique solution if f is a monotone increasing function. Piecewise linear functions can similarly be shown to have unique solutions.

If f(0) = 0, and r > 0, we designate by g_{r,θ} = g_{r} the solution of (2_{θ,r}) for the function f + r, and investigate what happens when r approaches 0. The collection g_{r}, r > 0 is equicontinuous on all compact intervals, and so there is a subsequence g_{r_{n}} where r_{n} decreases to 0, which converges uniformly to a limit which satisfies (2_{θ,0}). This proves existence of a solution. It is also easy to see that if there is an f with f(0) = 0 such that the corresponding g_{r} do not converge uniformly on compact intervals, then for that f, the solution of (2_{θ,0}) is not unique, since two subsequences of the g_{r} can be found which converge uniformly on compact intervals to two different solutions of (2_{θ,0}).

In fact, there is uniqueness in (2_{θ,0}) exactly when θ ≤ 1. The following proposition gives an idea why, when θ > 1, there are functions f such that the corresponding g_{r} do not converge uniformly as r approaches 0.

Proposition 1. Given 0 < y < s and θ > 1, there is a function f (depending on y and s) with f(0) = 0, such that if g_{r} is as defined above, g_{y}(t) − g_{s}(t), t ≥ 0, is unbounded both above and below.

Proof. The function f is defined inductively on intervals. The graph of f has slope −1 on (0, s). We have g_{a}^{∗}(s) = s, g_{y}^{∗}(s) = y, and g_{a}(s) = g_{y}(s) = 0. The slope of f is +1 on (s, 2s). Then g_{y} = g_{s} on (s, s + y), but on (s + y, 2s), g_{s} has slope 1, while g_{y} has slope 1+θ, as (2_{θ,y}) ii) comes into play for g_{y} at time s+y. We have g_{s}^{∗}(2s) = s, while g_{y}(2s) = s + θ[s − y], that is, the absolute difference between g_{s} and g_{y} has been multiplied by θ between times 0 and 2s, while the sign of the difference has switched. This procedure can be iterated, the end of the second iteration coinciding with an absolute difference of θ^{2} times the original absolute difference, and the sign of the difference switched again so that it is what it was at time 0, and so on. □

Because the functions f above depend on y and s, this proposition does not prove non-uniqueness. The function h = h_{θ}, θ > 1, constructed in Davis [5], for which uniqueness does not hold in (2_{θ,0}), has slope alternating between +1 and −1, switching an infinite number of times in any neighborhood of 0. The solutions q_{r} of (2_{θ,r}) for the functions h + r satisfy: given ϵ > 0 there are 0 < r, s < ϵ such that max_{0≤t≤1} |q_{s}(t) − q_{r}(t)| > c_{θ} > 0.

In the θ ≤ 1 cases, if f(0) = 0 and the functions g_{r} are as above, that is, the solutions for f + r of (2_{θ,r}), then

|g_{s}(t) − g_{y}(t)| ≤ s − y, if 0 < y < s. (3)

The proof of (3) is close to an argument in Davis [5] and will not be given here, but it is clear that the construction given above will not succeed in constructing functions that have solutions which pull apart. The inequality (3), and closely related inequalities, form the basis of the proof of uniqueness in (2_{θ,0}) given in [5]. Uniqueness for θ < 1 was known to Le Gall and Yor by the early nineties, see Le Gall-Yor [8] and Carmona-Petit-Yor [2]. Their proof used a Picard iteration type argument. To summarize, the following theorem holds.

Theorem 1. If θ ≤ 1, for any function f with f(0) = 0, there is a unique solution of (2_{θ,0}), while if θ > 1 there is at least one solution for every such f, and more than one for some of them.

Now we return to Brownian motion. We are trying to ascertain whether there is a unique adapted (to the filtration of the Brownian motion) solution to a two sided version of (1_{θ}). That is, if b_{t}, t ≥ 0, is standard Brownian motion, we ask whether there is a unique process w_{t}, t ≥ 0, which is adapted to the filtration of b and such that for almost every ω in the probability space Ω on which b is defined, w_{t}(ω), t ≥ 0, is a solution of (2_{θ,0}) for b_{t}(ω), t ≥ 0. We will call this Question 1. It was posed, and solved for θ < 1, in Le Gall-Yor [8]. In this case, as well as in the θ = 1 case considered in Davis [5], since only one solution of (2_{θ,0}) exists for every continuous function, only one exists for every Brownian path. Furthermore, to show that the process composed of these unique solutions is adapted to the Brownian filtration is also not difficult. Adaptedness is immediate for the solutions of (2_{θ,r}) of b_{t} + r, t ≥ 0, if r > 0, since these can be constructed by the Le Gall-Yor procedure, and so the limit of these as r decreases to 0, which is the unique solution w, is also adapted. The fact that this limit exists follows from (3).

Theorem 2. The answer to Question 1 is affirmative, for all θ. Furthermore, if G_{t}, t ≥ 0, is any filtration such that b_{t} is G_{t} measurable and b_{s}−b_{t} is independent of G_{t} for all 0 ≤ t < s, then there are no additional solutions adapted to this filtration.

This theorem can be rephrased as saying there is a unique strong solution of (2_{θ,0}). When θ ≤ 1, Theorem 1 follows from the deterministic results of Le Gall, Yor, and Davis, as described in the preceding paragraph. For θ > 1, we could ask whether Brownian paths are typically the kinds of functions which have several solutions in (2_{θ,0}). As indicated above, the examples of functions, given in Davis [5], which have several solutions are functions which zig-zag rapidly from above to below zero, a property of almost every Brownian path! Two simultaneous but quite different proofs of the θ > 1 cases of Theorem 2 have recently been given, in Davis [6] and Chaumont-Doney [3]. The proposition below is from Davis [6]. It is almost equivalent to the proof of Theorem 2 to show the following.

Proposition 2. Given ϵ > 0, there is a δ > 0, such that if 0 < r < s < δ, and if, for a > 0, h_{t}^{a}, t ≥ 0, is the solution of (2_{θ,a}) for a + b_{t}, t ≥ 0, then

P ( max_{0≤t≤1} |h_{t}^{r} − h_{t}^{s}| > ϵ) < ϵ.

We give just a brief overview of the proof of this proposition. The paths of h^{s} and h^{r} can be pulled apart, by the mechanism exhibited above: Both paths hit zero and then both rise above their former maxima. Then to get still further apart, they can both return to 0 and then rise again. But, if ϵ > 0, as r and s decrease to 0, the first time the paths are ϵ apart approaches infinity in probability. Martingale theory forms the core of the argument.

One thing accomplished by Theorem 2 is the construction of a process which behaves like the weak limit of p1-walk should behave. As mentioned, this theorem states that there is a unique strong solution of the Brownian version of equations (2_{θ,0}). It is easier to construct a weak solution to these equations. This was done, using excursion theory, in Perman-Werner [9]. In the special case we are talking about now, that is, reflection at 0, there is an easier way to construct a weak solution: Show that the solutions of (2_{θ,r}) for b_{t} + r, t ≥ 0, converge weakly as r approaches zero. This holds because all solutions propagate the same (distributionally) after the first time they hit the positive number ϵ, regardless of where below ϵ they start. And if ϵ is small and they start below it, they hit it fast, regardless of exactly where they start. This proof does not seem to extend to the general — not necessarily reflected — case that will soon be discussed.

That a 1p-walk converges weakly to the appropriate one of the solutions guaranteed by Theorem 2 is proved in Davis [6]. The method of proof is to embed a random walk into b_{t}, t ≥ 0, in the usual way using stopping times. Then the embedded random walk is perturbed in the following way. The first jump of the perturbed walk is the same as the first jump of the embedded walk. If the first jump of the perturbed walk is down to −1, its second jump is +1, back to 0. If the first jump of the perturbed walk is +1, whether its second jump is plus or minus one is determined by tossing an independent coin with probability p of heads. The third jump of the perturbed walk is the jump of the embedded walk, unless the position of the perturbed walk after the second jump is −1 or a maximum, in which case reflection or another flip of the biased coin determines its next jump. And so on. Clearly the perturbed walk is a 1p-walk. Then it is shown that the paths of this perturbed walk stay sufficiently close to the paths of the strong solution guaranteed by Theorem 2. This proof of the weak convergence of 1p-walk is based on the stability of solutions of the stochastic versions of (2_{θ,r}), as illustrated by Proposition 2. This approach to weak convergence shows that if a random walk is perturbed in the manner just described, the first n steps of its paths stay (arbitrarily) close, with probability approaching 1 as n approaches infinity, when compared with \sqrt{n}, to the paths which are the unique solution to (2_{θ,0}) of the piecewise polygonal path obtained by “connecting the dots” of the path of the random walk. In this sense, the perturbation of a random walk is almost deterministic.

Next we briefly discuss the situation in which there is soft perturbation, as opposed to reflection, at the minimum as well as at the maximum. Let θ be the parameter which gives the push up or down at the maximum, exactly as above, so that θ positive corresponds to a push up. And let μ be the parameter which gives the push down, so that if μ is positive the push is down. Le Gall, Yor, Carmona and Petit proved there are unique strong solutions of the appropriate equations (now we only consider starting at 0) for some ranges of θ and μ, in [2]. Davis added just a couple of additional cases, in [5], and then Perman and Werner in [9] showed there are unique strong solutions when both θ and μ are positive, with a very short and pretty argument. Finally, the remaining cases are settled in Chaumont and Doney [3] and Davis [6]. The weak convergence of pq-walk is proved in Davis [6].

2. Brownian Local Times

This section describes the second of the talks given by the author at the Albany conference, which was based on the author’s paper [6]. As this is a three page virtually self-contained paper, we are going to be very brief.

Let b_{t}, t ≥ 0, be standard Brownian motion started at zero. Let f(t), 0 ≤ t ≤ 1, be smooth, by which we mean f is continuous and has a bounded second derivative on (0,1). Let L_{f} stand for the local time spent by b_{t} on the graph of f: Formally, L_{f} is the limit as ϵ decreases to 0 of the Lebesgue measure of {0 ≤ t ≤ 1 : |b_{t}−f(t)| < ϵ} divided by 2ϵ. While it is not immediate that this limit exists almost everywhere, it does, and local times, especially at constants (i.e., on the graphs of constant functions), have become one of the indispensable tools of stochastic analysis. An example of this being provided by the work of Toth and Werner described in the previous section. It is known that the distribution of L_{0} is the distribution of the absolute value of a standard normal variable. In Burdzy-San Martin [1], the

Perturbed Random Walks 87

question was asked whether among all nondecreasing smooth functions f, L_{0} was the largest in terms of distribution, that is, whether

P (L_{f} < x) ≥ P (L_{0} < x), x > 0. (4)

In Davis [7] it is shown that the answer to this question is no. More precisely, the following theorem is proved.

Theorem 3. If the function f, defined on [0, 1], is smooth, then

P (L_{f} < x) ≥ P (2L_{0} < x), x > 0. (5)

If the constant 2 is replaced by a smaller number, then the resulting statement is false.

The analog of this theorem holds for all functions f with enough smoothness to be able to define local time via Girsanov’s theorem, a less restrictive condition than the smooth condition used here to avoid technicalities. Easy examples of rapidly oscillating functions show that without some restriction on f, no distributional comparisons of this type between L_{f} and L_{0} are possible.

We have been unable to settle whether (4) holds for all concave functions.

References

[1] K. Burdzy and J. San Martin, Iterated law of iterated logarithm, Ann. Prob. 23 (1995), 1627– 1643.

[2] Ph. Carmona, F. Petit, and M. Yor, Beta variables as time spent in [0, ∞) by certain perturbed Brownian motions, to appear in J. London Math. Soc.

[3] L. Chaumont and R. A. Doney, Pathwise uniqueness for perturbed versions of Brownian motion and reflected Brownian motion, preprint, 1997.

[4] B. Davis, Reinforced random walk, Probab. Th. Rel. Fields 84 (1990), 203–229.

[5] B. Davis, On the equation Y_{t} = B_{t} + α sup_{s≤t} Y_{s} + β inf_{s≤t} Y_{s}, The Annals of Probability 24 (1996), 2007–2023.

[6] B. Davis, Perturbed Brownian motions and random walks: strong solutions, preprint 1997.

[7] B. Davis, Distribution of Brownian local times on curves, to appear in Bull. London. Math. Soc.

[8] S. F. Le Gall and M. Yor, Enlacement du mouvement Brownian author des courbes de l’espace, Trans. Amer. Math. Soc. 317 (1992), 687–722.

[9] M. Perman and W. Werner, Perturbed Brownian motions, to appear in Probab. Th. Rel. Fields.

[10] B. Toth, Generalized Ray-Knight theory and limit theorems for self-interacting random walks on ℤ, The Annals of Probability 24 (1996), 1324–1367.

[11] B. Toth, Limit theorems for weakly reinforced random walks, to appear in Studia Sci. Math. Hung.

[12] B. Toth and W. Werner, The true self-repelling motion, preprint, 1997.

[13] W. Werner, Some remarks on perturbed reflecting Brownian motion, Seminaire de Probabilites XXIX., Lecture Notes in Math., no. 1613, Springer-verlag, Berlin, 1995, pp. 37–43.

[14] M. Yor, Some aspects of Brownian motion: some recent martingale problems, Lectures in mathematics, ETH Zurich, 1997.

Department of Statistics, Purdue University, West Lafayette, IN 47907-1399 bdavis@stat.purdue.edu http://www.stat.purdue.edu/people/bdavis/

This paper is available via http://nyjm.albany.edu:8000/j/1998/3A-6.html.