A law of the iterated logarithm for a class of polynomial hypergroups

We consider stationary ₀-valued Markov chains whose transition probabilities are associated with convolution structures of measures which are induced by linearization formulas of orthogonal polynomials. The best known examples are random walks on polynomial hypergroups and generalized birth and death random walks. Using central limit theorems derived in a recent paper by the author and some martingale arguments, we here prove a law of the iterated logarithm for a class of such Markov chains.     

The central limit theorem for stationary Markov processes with normal generator—with applications to hypergroups

We extend the central limit theorem for additive functionals of a stationary, ergodic Markov chain with normal transition operator due to Gordin and Lif?ic, 1981 [A remark about a Markov process with normal transition operator, In: Third Vilnius Conference on Probability and Statistics 1, pp. 147–48] to continuous-time Markov processes with normal generators. As examples, we discuss random walks on compact commutative hypergroups as well as certain random walks on non-commutative, compact groups.     

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.     

A law of the iterated logarithm for Markov chains on ℕ0 associated with orthogonal polynomials

We derive laws of the iterated logarithm for Markov chains on the nonnegative integers whose transition probabilities are associated with a sequence of orthogonal polynomials. These laws can be applied to a large class of birth and death random walks and random walks on polynomial hypergroups. In particular, the results of our paper lead immediately to a law of the iterated logarithm for the growth of the distance of isotropic random walks on infinite distance-transitive graphs as well as on certain finitely generated semigroups from their starting points.     

A finite dimensional approximation of the effective diffusivity for a symmetric random walk in a random environment

We consider a nearest neighbor, symmetric random walk on a homogeneous, ergodic random lattice Z^d${\mathbb{Z}}^d$. The jump rates of the walk are independent, identically Bernoulli distributed random variables indexed by the bonds of the lattice. A standard result from the homogenization theory, see [A. De Masi, P.A. Ferrari, S. Goldstein, W.D. Wick, An invariance principle for reversible Markov processes, Applications to random walks in random environments, J. Statist. Phys. 55(3/4) (1989) 787–855], asserts that the scaled trajectory of the particle satisfies the functional central limit theorem. The covariance matrix of the limiting normal distribution is called the effective diffusivity of the walk. We use the duality structure corresponding to the product Bernoulli measure to construct a numerical scheme that approximates this parameter when d?3$d?3$. The estimates of the convergence rates are also provided.     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

The converse of Schur’s theorem

Schur’s theorem states that for a group G finiteness of G/Z(G) implies the finiteness of G′. In this paper, we show the converse is true provided that G/Z(G) is finitely generated and in such case, we have |G/Z(G)| ≤ |G′| ^d(G/Z(G)). In the special case of G being nilpotent, we prove |G/Z(G)| divides |G′| ^d(G/Z(G)).     

Large deviations for Poisson systems of independent random walks

Summary We prove large deviation theorems for occupation time functionals of independent random walks started from a Poisson field on Z ^d. In dimensions 1 and 2 the large deviation tails are larger than exponential. Exact asymptotics are derived.Partially supported by the National Science Foundation under Grant MCS 81-02131 and MCS 81-00256Alfred P. Sloan Research Fellow     

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.     

On the local time of random walk on the 2-dimensional comb

We study the path behaviour of general random walks, and that of their local times, on the 2-dimensional comb lattice C² that is obtained from Z² by removing all horizontal edges off the x-axis. We prove strong approximation results for such random walks and also for their local times. Concentrating mainly on the latter, we establish strong and weak limit theorems, including Strassen-type laws of the iterated logarithm, Hirsch-type laws, and weak convergence results in terms of functional convergence in distribution.     

Geometric analysis for the metropolis algorithm on Lipschitz domains

This paper gives geometric tools: comparison, Nash and Sobolev inequalities for pieces of the relevant Markov operators, that give useful bounds on rates of convergence for the Metropolis algorithm. As an example, we treat the random placement of N hard discs in the unit square, the original application of the Metropolis algorithm.     

How edge-reinforced random walk arises naturally

 We give a characterization of a modified edge-reinforced random walk in terms of certain partially exchangeable sequences. In particular, we obtain a characterization of an edge-reinforced random walk (introduced by Coppersmith and Diaconis) on a 2-edge-connected graph. Modifying the notion of partial exchangeability introduced by Diaconis and Freedman in [3], we characterize unique mixtures of reversible Markov chains under a recurrence assumption. Received: 22 January 2002 / Revised version: 24 September 2002 Published online: 15 April 2003 Most of this paper was written while the author was working at EURANDOM in Eindhoven, The Netherlands. Mathematics Subject Classification (2000): 60K37, 60G09     

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

The rate of escape for anisotropic random walks in a tree

Summary Let G be the group generated by L free involutions, whose Cayley graph T is the infinite homogeneous tree with L edges at every node. A general central limit theorem and law of the iterated logarithm is proven for left-invariant random walks Z _n on G or T which applies to the distance of Z _n from a fixed point, as well as to the distribution of the last R letters in Z _n . For nearest neighbor random walks, we also derive a generating function identity that yields formulas for the asymptotic mean and variance of the distance from a fixed point. A generalization for Z _n with a finitely supported step distribution is derived and discussed.Partially supported by grant NSF MCS85-04315     

Mean field bounds on Lyapunov exponents in Z d at the critical energy

We further develop the supersymmetric formalism initiated in [W1] (see also [SjW]). We obtain the optimal mean field bounds at the critical energy for Lyapunov exponents of random walks in random potentials in Z ^d at weak disorder. This extends some of the results in [W1]. Received: 9 December 1999 / Revised version: 8 May 2000 /?Published online: 15 February 2001     

Ergodicity conditions for two-dimensional Markov chains on the positive quadrant

Summary The basic problem considered in this paper is that of determining conditions for recurrence and transience for two dimensional irreducible Markov chains whose state space is Z ₊ ² =Z₊xZ₊. Assuming bounded jumps and a homogeneity condition Malyshev [7] obtained necessary and sufficient conditions for recurrence and transience of two dimensional random walks on the positive quadrant. Unfortunately, his hypothesis that the jumps of the Markov chain be bounded rules out for example, the Poisson arrival process. In this paper we generalise Malyshev's theorem by means of a method that makes novel use of the solution to Laplace's equation in the first quadrant satisfying an oblique derivative condition on the boundaries. This method, which allows one to replace the very restrictive boundedness condition by a moment condition and a lower boundedness condition, is of independent interest.     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

On estimating the derivatives of symmetric diffusions in stationary random environment,with applications to ∇<Emphasis Type="Italic">ϕ</Emphasis> interface model

We consider diffusions on ℝ^d or random walks on ℤ^d in a random environment which is stationary in space and in time and with symmetric and uniformly elliptic coefficients. We show existence and H?lder continuity of second space derivatives and time derivatives for the annealed kernels of such diffusions and give estimates for these derivatives. In the case of random walks, these estimates are applied to the Ginzburg-Landau ∇ϕ interface model.