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.     

A random environment for linearly edge-reinforced random walks on infinite graphs

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds for the random weights, uniform, among others, in the size of the graph.      

Random walk in mixed random environment without uniform ellipticity

We study a random walk in random environment on ?₊. The random environment is not homogeneous in law, but is a mixture of two kinds of site, one in asymptotically vanishing proportion. The two kinds of site are (i) points endowed with probabilities drawn from a symmetric distribution with heavy tails at 0 and 1, and (ii) “fast points” with a fixed systematic drift. Without these fast points, the model is related to the diffusion in heavy-tailed (“stable”) random potential studied by Schumacher and Singh; the fast points perturb that model. The two components compete to determine the behaviour of the random walk; we identify phase transitions in terms of the model parameters. We give conditions for recurrence and transience and prove almost sure bounds for the trajectories of the walk.     

Occupation measure for random walk on the circle

We give bounds on the probability of deviation of the occupation measure of an interval on the circle for random walk.     

Slowdown and neutral pockets for a random walk in random environment

We consider a d-dimensional random walk in random environment for which transition probabilities at each site are either neutral or present an effective drift “pointing to the right”. We obtain large deviation estimates on the probability that the walk moves in a too slow ballistic fashion, both under the annealed and quenched measures. These estimates underline the key role of large neutral pockets of the medium in the occurrence of slowdowns of the walk. Received: 12 March 1998 / Revised version: 19 February 1999     

A random walk with a branching system in random environments

We consider a branching random walk in random environments, where the particles are reproduced as a branching process with a random environment (in time), and move independently as a random walk on Z with a random environment (in locations). We obtain the asymptotic properties on the position of the rightmost particle at time n, revealing a phase transition phenomenon of the system.     

Large deviations for hitting times of a random walk in random environment on a strip

We consider a random walk in random environment on a strip, which is transient to the right. The random environment is stationary and ergodic. By the constructed enlarged random environment which was first introduced by Goldsheid （2008）, we obtain the large deviations conditioned on the environment （in the quenched case） for the hitting times of the random walk.     

Asymptotic direction for random walks in random environments

In this paper we study the existence of an asymptotic direction for random walks in random i.i.d. environments (RWRE). We prove that if the set of directions where the walk is transient contains a non-empty open set, the walk admits an asymptotic direction. The main tool to obtain this result is the construction of a renewal structure with cones. We also prove that RWRE admits at most two opposite asymptotic directions.     

Product-form characterization for a two-dimensional reflecting random walk

We consider a two-dimensional skip-free reflecting random walk on the non-negative integers, which is referred to as a 2-d reflecting random walk. We give necessary and sufficient conditions for the stationary distribution to have a product-form. We also derive simpler sufficient conditions for the product-form for a restricted class of 2-d reflecting random walks. We apply these results and obtain a product-form approximation of the stationary distribution through a suitable modification of the parameters of the random walk.     

On convergent probability of a random walk

This note introduces an interesting random walk on a straight path with cards of random numbers. The method of recurrent relations is used to obtain the convergent probability of the random walk with different initial positions.     

Monotonicity for excited random walk in high dimensions

We prove that the drift θ(d, β) for excited random walk in dimension d is monotone in the excitement parameter ${\beta \in [0,1]}$ , when d is sufficiently large. We give an explicit criterion for monotonicity involving random walk Green’s functions, and use rigorous numerical upper bounds provided by Hara (Private communication, 2007) to verify the criterion for d ≥ 9.     

Random random walks on ℤ2 d

Summary. We consider random walks on classes of graphs defined on the d-dimensional binary cube ℤ₂ ^d by placing edges on n randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the walk forgets where it started, and reaches a random location. In this paper we resolve a question of Diaconis by finding exact expressions for this mixing time that hold for all n>d and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science.     

On symmetric random walks with random conductances on ℤ d

We study models of continuous time, symmetric, ℤ^d-valued random walks in random environments. One of our aims is to derive estimates on the decay of transition probabilities in a case where a uniform ellipticity assumption is absent. We consider the case of independent conductances with a polynomial tail near 0 and obtain precise asymptotics for the annealed return probability and convergence times for the random walk confined to a finite box.     

Simple random walk on long range percolation clusters I: heat kernel bounds

In this paper, we derive upper bounds for the heat kernel of the simple random walk on the infinite cluster of a supercritical long range percolation process. For any d ?? 1 and for any exponent ${s \in (d, (d+2) \wedge 2d)}$ giving the rate of decay of the percolation process, we show that the return probability decays like ${t^{-{d}/_{s-d}}}$ up to logarithmic corrections, where t denotes the time the walk is run. Our methods also yield generalized bounds on the spectral gap of the dynamics and on the diameter of the largest component in a box. The bounds and accompanying understanding of the geometry of the cluster play a crucial role in the companion paper (Crawford and Sly in Simple randomwalk on long range percolation clusters II: scaling limit, 2010) where we establish the scaling limit of the random walk to be ??-stable Lévy motion.     

Approximation of the expectation of the first exit time from an interval for a random walk

We obtain asymptotic expansions for the expectation of the first exit time from an expanding strip for a random walk trajectory. We suppose that the distribution of random walk jumps satisfies the Cramér condition on the existence of an exponential moment.     

The energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.     

Fast graphs for the random walker

 Consider the time T _oz when the random walk on a weighted graph started at the vertex o first hits the vertex set z. We present lower bounds for T _oz in terms of the volume of z and the graph distance between o and z. The bounds are for expected value and large deviations, and are asymptotically sharp. We deduce rate of escape results for random walks on infinite graphs of exponential or polynomial growth, and resolve a conjecture of Benjamini and Peres. Received: 31 October 2000 / Revised version: 5 January 2002 / Published online: 22 August 2002     

Logarithmic speeds for one-dimensional perturbed random walks in random environments

We study the random walk in a random environment on Z⁺={0,1,2,…}${\mathbb{Z}}^{+}=\{0,1,2,\dots \}$, where the environment is subject to a vanishing (random) perturbation. The two particular cases that we consider are: (i) a random walk in a random environment perturbed from Sinai’s regime; (ii) a simple random walk with a random perturbation. We give almost sure results on how far the random walker is from the origin, for almost every environment. We give both upper and lower almost sure bounds. These bounds are of order (logt)^β${(logt)}^{\beta }$, for β∈(1,∞)$\beta \in (1,\infty )$, depending on the perturbation. In addition, in the ergodic cases, we give results on the rate of decay of the stationary distribution.     

On the exact distributional asymptotics for the supremum of a random walk with increments in a class of light-tailed distributions

We study the distribution of the maximum M of a random walk whose increments have a distribution with negative mean which belongs for some γ > 0 to a subclass of the class S _γ (for example, see Chover, Ney, and Wainger [5]). For this subclass we provide a probabilistic derivation of the asymptotic tail distribution of M and show that the extreme values of M are in general attained through some single large increment in the random walk near the beginning of its trajectory. We also give some results concerning the “spatially local” asymptotics of the distribution of M, the maximum of the stopped random walk for various stopping times, and various bounds.     

Quenched tail estimate for the random walk in random scenery and in random layered conductance

We discuss the quenched tail estimates for the random walk in random scenery. The random walk is the symmetric nearest neighbor walk and the random scenery is assumed to be independent and identically distributed, non-negative, and has a power law tail. We identify the long time asymptotics of the upper deviation probability of the random walk in quenched random scenery, depending on the tail of scenery distribution and the amount of the deviation. The result is in turn applied to the tail estimates for a random walk in random conductance which has a layered structure.