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.      

Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

On mixing behavior of a family of random walks determined by a linear recurrence

We study random walks on the integers mod $G_n$ that are determined by an integer sequence ${\{G_n\}}_{n\ge 1}$ generated by a linear recurrence relation. Fourier analysis provides explicit formulas to compute the eigenvalues of the transition matrices and we use this to bound the mixing time of the random walks.     

Return probabilities for random walk on a half-line

A random walk with reflecting zone on the nonnegative integers is a Markov chain whose transition probabilitiesq(x, y) are those of a random walk (i.e.,q(x, y)=p(y–x)) outside a finite set {0, 1, 2,...,K}, and such that the distributionq(x,·) stochastically dominatesp(·–x) for everyx{0, 1, 2,..., K}. Under mild hypotheses, it is proved that when xp _x>0, the transition probabilities satisfyq ⁿ(x, y)C_xyR^–nn^–3/2 asn, and when xp _x=0,q ⁿ(x, y)C_xyn^–1/2.Supported by National Science Foundation Grant DMS-9307855.     

Velocity and Lyapounov exponents of some random walks in random environment

We express the asymptotic velocity of random walks in random environment satisfying Kalikow's condition in terms of the Lyapounov exponents which have previously been used in the context of large deviations.     

Multiscale analysis of exit distributions for random walks in random environments

We present a multiscale analysis for the exit measures from large balls in , of random walks in certain i.i.d. random environments which are small perturbations of the fixed environment corresponding to simple random walk. Our main assumption is an isotropy assumption on the law of the environment, introduced by Bricmont and Kupiainen. Under this assumption, we prove that the exit measure of the random walk in a random environment from a large ball, approaches the exit measure of a simple random walk from the same ball, in the sense that the variational distance between smoothed versions of these measures converges to zero. We also prove the transience of the random walk in random environment. The analysis is based on propagating estimates on the variational distance between the exit measure of the random walk in random environment and that of simple random walk, in addition to estimates on the variational distance between smoothed versions of these quantities. Partially supported by NSF grant DMS-0503775.     

On the structure of stable random walks

We show that the Cauchy random walk on the line, and the Gaussian random walk on the plane are similar as infinite measure preserving transformations.     

Random walks on graphs with a strong isoperimetric property

A random walk on a graph is a Markov chain whose state space consists of the vertices of the graph and where transitions are only allowed along the edges. We study (strongly) reversible random walks and characterize the class of graphs where then-step transition probabilities tend to zero exponentially fast (geometric ergodicity). These characterizations deal with an isoperimetric property, norm inequalities for certain associated operators, and eigenvalues of the Laplace operator. There is some (strong) similarity with the theory of (non)amenable groups.     

Collision problems of random walks in two-dimensional time

The collision problems of two-parameter random walks are studied. That is, some criteria have been established in terms of the characteristic functions of two or more mutually independent random walks in order to determine if they meet infinitly often in certain restricted time sets.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

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.     

Self-intersections of random walks on lattices

Let {X _n ^d }_n≥0be a uniform symmetric random walk on Z^d, and Π^(d) (a,b)={X _n ^d ∈ Z^d : a ≤ n ≤ b}. Suppose f(n) is an integer-valued function on n and increases to infinity as n↑∞, and let

Random walks in random environments on metric groups

Random walks in random environments on countable metric groups with bounded jumps of the walking particle are considered. The transition probabilities of such a random walk from a pointx εG (whereG is the group in question) are described by a vectorp(x) ε ℝ^|W| (whereW ⊏G is fixed and |W|<∞). The set {p(x),x εG} is assumed to consist of independent identically distributed random vectors. A sufficient condition for this random walk to be transient is found. As an example, the groups ℤ ^d , free groups, and the free product of finitely many cyclic groups of second order are considered. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 129–135, January, 2000.     

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

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.     

Dirichlet forms and associated heat kernels on the Cantor set induced by random walks on trees

Transient random walk on a tree induces a Dirichlet form on its Martin boundary, which is the Cantor set. The procedure of the inducement is analogous to that of the Douglas integral on S¹ associated with the Brownian motion on the unit disk. In this paper, those Dirichlet forms on the Cantor set induced by random walks on trees are investigated. Explicit expressions of the hitting distribution (harmonic measure) ν and the induced Dirichlet form on the Cantor set are given in terms of the effective resistances. An intrinsic metric on the Cantor set associated with the random walk is constructed. Under the volume doubling property of ν with respect to the intrinsic metric, asymptotic behaviors of the heat kernel, the jump kernel and moments of displacements of the process associated with the induced Dirichlet form are obtained. Furthermore, relation to the noncommutative Riemannian geometry is discussed.     

Non parametric estimation for random walks in random environment

We investigate the problem of estimating the cumulative distribution function (c.d.f.) $F$ of a distribution $\nu$ from the observation of one trajectory of the random walk in i.i.d. random environment with distribution $\nu$ on $\mathbb{Z}$. We first estimate the moments of $\nu$, then combine these moment estimators to obtain a collection of estimators ${\left({\stackrel{?}{F}}_n^M\right)}_{M\ge 1}$ of $F$, our final estimator is chosen among this collection by Goldenshluger–Lepski’s method. This estimator is easily computable. We derive convergence rates for this estimator depending on the Hölder regularity of $F$ and on the divergence rate of the walk. Our rate is minimal when the chain realizes a trade-off between a fast exploration of the sites, allowing to get more information and a larger number of visits of each site, allowing a better recovery of the environment itself.     

一类随机环境下随机游动的常返性

就一类平稳环境θ下随机流动{Xn}n∈z 建立相应的Markov-双链{ηn}n∈z ={(xn,Tnθ)}n∈z ,并给出在该平稳环境θ下{xn}n∈z 为常返链的条件.