Maxima of branching random walks vs. independent random walks

In recent years several authors have obtained limit theorems for the location of the right most particle in a supercritical branching random walk. In this paper we will consider analogous problems for an exponentially growing number of independent random walks. A comparison of our results with the known results of branching random walk then identifies the limit behaviors which are due to the number of particles and those which are determined by the branching structure.     

Delayed random walks

A delayed random walk $\text{{S}{}^1{}_{\mathrm{n}}\text{, n ≥ 0}}$ is defined here as a partial sum process of independent random variables in which the first N summands (N optional) are distributed F¹,…,F_N, respectively, while all remaining summands are distributed F₀, where {F_k, _k ≥ 0} is a sequence of proper distribution functions on the real line. Delayed random walks arise naturally in the study of certain generalized single server queues. This paper examines optional times of the process such as $\text{π = inf {n: n ≥ 1 and S}{}^1{}_{\mathrm{n}}\text{≥ 0}}$. Conditions insuring the finiteness of E {π} and E {π²} are obtained, generating functions calculated, and illustrative examples given. The bivariate functions $\text{E{r}{}^{\mathrm{\pi }}\text{explsqbitS}{}^1{}_{\mathrm{\pi }}\text{rsqb}}$ and $\text{E {}\text{∑}\text{n=0}\text{π?1}\text{explsqbitS}{}^1{}_{\mathrm{n}}\text{rsqb}}$ are studied for the case where N ≡ 1.     

Biased random walks

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, at each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.     

Persistent random walks in random environment

Summary Weak convergence of a class of functionals of PRWRE is proved. As a consequence CLT is obtained for the normed trajectory.Work supported by the Central Research Fund of the Hungarian Academy of Sciences (Grant No. 476/82).     

Intersections of random walks with random sets

Two general theorems about the intersections of a random walk with a random set are proved. The result is applied to the cases when the random set is a (deterministic) half-line and a two-sided random walk. Research supported by NSF Grant DMS-8702879 and an Alfred P. Sloan Research Fellowship.     

p-Sets for random walks

Summary Let (,,P) be a probability space and let {itX _n ()} _n=1 be a sequence of i.i.d. random vectors whose state space isZ ^m for some positive integerm, where Z denotes the integers. Forn = 1, 2,... letS _n () be the random walk defined by . ForxZ ^m andU ^m, them-dimensional torus, let . Finally let be the characteristic function of the X's.In this paper we show that, under mild restrictions, there exists a set withP{ ₀ } = 1 such that for ₀ we have for all aU ^m,le0.As a consequence of this theorem, we obtain two corollaries. One is concerned with occupancy sets form-dimensional random walks, and the other is a mean ergodic theorem.Research supported by N.S.F. Grant # MCS 77-26809     

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.     

Remarkable asymmetric random walks

There exists an asymmetric probability measure on the real line with for every . can be chosen absolutely continuous and can be chosen to be concentrated on the integers. In both cases, can be chosen to have moments of every order, but cannot be determined by its moments.

     

Branching random walks I

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.     

Recurrence of inhomogeneous random walks

Inhomogeneous random walk means to study the time evolution of a sum of independent vector valued random variables (called “steps”), where we go beyond the traditional framework of Random Walks by dropping the usual condition of “identically distributed steps”. Our results show that genuinely 2-dimensional steps suffice—we do not need identically distributed steps to prove 2-dimensional Pólya type theorems. It turns out that we do not even need a whole 2-dimensional random walk: we can guarantee recurrence in a given sparse subsequence of the steps. An interesting example is the two-dimensional simple symmetric random walk on the lattice \(\mathbb {Z}^2\), where we can prove recurrence for the sequence of primes; more precisely, for the sets \(\{ p+1{:}\ p\ge 3\ \mathrm{prime}\}\), or \(\{ p-1{:}\ p\ge 3\ \mathrm{prime}\}\), or \(\{ 2p{:}\ p\ge 3\ \mathrm{prime}\}\), etc. (since for return we clearly need a set of even numbers). In this direction we can prove optimal results, describing the class of sparsest subsequences still exhibiting recurrence. In fact, we can prove these best possible results for the larger class of inhomogeneous random walks. We can also prove the one-dimensional analogs, which—not surprisingly—turn out to be easier.     

Clairvoyant scheduling of random walks

Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. Years ago, Peter Winkler asked the question: for which graphs are two independent random walks compatible with positive probability. Up to now, no such graphs were found. We show in this paper that large complete graphs have this property. The question is equivalent to a certain dependent percolation with a power‐law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Scaling exponents of random walks in random sceneries

We compute the exact asymptotic normalizations of random walks in random sceneries, for various null recurrent random walks to the nearest neighbours, and for i.i.d., centered and square integrable random sceneries. In each case, the standard deviation grows like n with . Here, the value of the exponent is determined by the sole geometry of the underlying graph, as opposed to previous examples, where this value reflected mainly the integrability properties of the steps of the walk, or of the scenery. For discrete Bessel processes of dimension d[0;2[, the exponent is . For the simple walk on some specific graphs, whose volume grows like n^d for d[1;2[, the exponent is =1−d/4. We build a null recurrent walk, for which without logarithmic correction. Last, for the simple walk on a critical Galton–Watson tree, conditioned by its nonextinction, the annealed exponent is . In that setting and when the scenery is i.i.d. by levels, the same result holds with .     

Diffusivity of a random walk on random walks

We consider a random walk with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267–283, 2015     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

Range reliability in random walks

This paper introduces a definition of reliability based on a process range. Thus, process failure is defined when the range of a process first reaches a given and unacceptable level. The Mean Time To Failure (MTTF) which is denned as the mean of the first time for a range to attain a given amplitude is then calculated for an asymmetric random walk process. The probability distribution of the range is then given and the process reliability over long periods of system operations are then calculated. Applications such as the control of wings movements, stock price and exchange rates volatility (defined in terms of reliability) are also used to motivate the usefulness of range processes in reliability studies. Finally, we point out that there is necessarily a relationship between the range reliability and the propensity of a series to become chaotic.     

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 }$.     

Multi-excited random walks on integers

We introduce a class of nearest-neighbor integer random walks in random and non-random media, which includes excited random walks considered in the literature. At each site the random walker has a drift to the right, the strength of which depends on the environment at that site and on how often the walker has visited that site before. We give exact criteria for recurrence and transience and consider the speed of the walk.Most of this work was done while the author was Szegö Assistant Professor at Stanford University.