Limit theorems for random walks

We consider a random walk $S_{\tau }$ which is obtained from the simple random walk $S$ by a discrete time version of Bochner’s subordination. We prove that under certain conditions on the subordinator $\tau$ appropriately scaled random walk $S_{\tau }$ converges in the Skorohod space to the symmetric $\alpha$-stable process $B^{\alpha }$. We also prove asymptotic formula for the transition function of $S_{\tau }$ similar to the Pólya’s asymptotic formula for $B^{\alpha }$.     

Limit theorems for random walks with dynamical random transitions

Let be an ergodic and conservative non-singular transformation of (, ,m) (thedynamic environment), let _w be a random probability on a locally compact second countable groupG, and define

Limit theorems for one-dimensional diffusions and random walks in random environments

Summary The limiting behavior of one-dimensional diffusion process in an asymptotically self-similar random environment is investigated through the extension of Brox's method. Similar problems are then discussed for a random walk in a random environment with the aid of optional sampling from a diffusion model; an extension of the result of Sinai is given in the case of asymptotically self-similar random environments.     

Limit theorems for reinforced random walks on certain trees

Consider a linearly edge-reinforced random walk defined on the b-ary tree, b≥70. We prove the strong law of large numbers for the distance of this process from the root. We give a sufficient condition for this strong law to hold for general edge-reinforced random walks and random walks in a random environment. We also provide a central limit theorem. Supported in part by a Purdue Research Foundation fellowship this work is part of the author's PhD thesis.     

Conditioned limit theorems for random walks with negative drift

Summary In this paper we will solve a problem posed by Iglehart. In (1975) he conjectured that if S _n is a random walk with negative mean and finite variance then there is a constant so that (S _[n.]/n ^1/2¦N>n) converges weakly to a process which he called the Brownian excursion. It will be shown that his conjecture is false or, more precisely, that if ES ₁=–a<0, ES ₁ ² <, and there is a slowly varying function L so that P(S ₁>x)x ^–q L(x) as x then (S _[n.]/n¦S _n >0) and (S _[n.]/n¦N>n) converge weakly to nondegenerate limits. The limit processes have sample paths which have a single jump (with d.f. (1–(x/a)^–q )⁺) and are otherwise linear with slope –a. The jump occurs at a uniformly distributed time in the first case and at t=0 in the second.The research for this paper was started while the author was visiting W. Vervaat at the Katholieke Universiteit in Nijmegen, Holland, and was completed while the author was at UCLA being supported by funds from NSF grant MCS 77-02121     

Branching random walks II

A general method is developed with which various theorems on the mean square convergence of functionals of branching random walks are proven. The results cover extensions and generalizations of classical central limit analogues as well as a result of a different type.     

Two renewal theorems for general random walks tending to infinity

Summary. Necessary and sufficient conditions for the existence of moments of the first passage time of a random walk S _n into [x, ∞) for fixed x≧ 0, and the last exit time of the walk from (−∞, x], are given under the condition that S _n →∞ a.s. The methods, which are quite different from those applied in the previously studied case of a positive mean for the increments of S _n , are further developed to obtain the “order of magnitude” as x→∞ of the moments of the first passage and last exit times, when these are finite. A number of other conditions of interest in renewal theory are also discussed, and some results for the first time for which the random walk remains above the level x on K consecutive occasions, which has applications in option pricing, are given. Received: 18 September 1995/In revised form: 28 February 1996     

Limit theorems of continuous-time random walks with tails

We study the functional limits of continuous-time random walks (CTRWs) with tails under certain conditions. We find that the scaled CTRWs with tails converge weakly to an α-stable Lévy process in D([0, 1]) with M ₁-topology but the corresponding scaled CTRWs converge weakly to the same limit in D([0, 1]) with J ₁-topology.     

Synchronization and functional central limit theorems for interacting reinforced random walks

We obtain Central Limit Theorems in Functional form for a class of time-inhomogeneous interacting random walks. Due to a reinforcement mechanism and interaction, the walks are strongly correlated and converge almost surely to the same, possibly random, limit. We study random walks interacting through a mean-field rule and compare the rate they converge to their limit with the rate of synchronization, i.e. the rate at which their mutual distances converge to zero. We show that, under certain conditions, synchronization is faster than convergence. Even if our focus is on theoretical results, we propose as main motivations two contexts in which such results could directly apply: urn models and opinion dynamics in a random network evolving via preferential attachment.     

Efficient simulation and conditional functional limit theorems for ruinous heavy-tailed random walks

The contribution of this paper is to introduce change of measure based techniques for the rare-event analysis of heavy-tailed random walks. Our changes of measures are parameterized by a family of distributions admitting a mixture form. We exploit our methodology to achieve two types of results. First, we construct Monte Carlo estimators that are strongly efficient (i.e. have bounded relative mean squared error as the event of interest becomes rare). These estimators are used to estimate both rare-event probabilities of interest and associated conditional expectations. We emphasize that our techniques allow us to control the expected termination time of the Monte Carlo algorithm even if the conditional expected stopping time (under the original distribution) given the event of interest is infinity–a situation that sometimes occurs in heavy-tailed settings. Second, the mixture family serves as a good Markovian approximation (in total variation) of the conditional distribution of the whole process given the rare event of interest. The convenient form of the mixture family allows us to obtain functional conditional central limit theorems that extend classical results in the literature.     

Limit theorems for Markov random walks with a fixed number of certain transitions

The limit behavior of Markov chains with discrete time and a finite number of states (MCDT) depending on the number n of its steps has been almost completely investigated [1–4]. In [5], MCDT with forbidden transitions were investigated, and in [6], the sum of a random number of functionals of random variables related by a homogeneous Markov chain (HMC) was considered. In the present paper, we continue the investigation of the limit behavior of the MCDT with random stopping time which is determined by a Markov walk plan II with a fixed number of certain transitions [7, 8]. Here we apply a method similar to that of [6], which allows us to obtain, together with some generalizations of the results of [6], a number of new assertions. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 119–130, Perm, 1990.     

Ergodic theorems for coupled random walks and other systems with locally interacting components

Summary In [5] the second author introduced a variety of new infinite systems with locally interacting components. On the basis of computations for the finite analogues of these systems, he made conjectures ragarding their limiting behavior as t. This paper is devoted to the construction of these processes and to the proofs of these conjectures. We restrict ourselves primarily to spatially homogeneous situations; interesting problems remain unsolved in inhomogeneous cases. Two features distinguish these processes from most other infinite particle systems which have been studied. One is that the state spaces of these systems are noncompact; the other that even though the invariant measures are not generally of product form, one can nevertheless compute explicitly the first and second moments of the number of particles per site in equilibrium. The second moment computations are of inherent interest of course, and they play an important role in the proofs of the ergodic theorems as well.Research supported in part by NSF Grant MCS 77-02121Research supported in part by NSF Grant MCS 77-03543.