Mixing properties of the generalized T, T-1-process

Consider a general random walk on ℤ^d together with an i.i.d. random coloring of ℤ^d. TheT, T ^-1-process is the one where time is indexed by ℤ, and at each unit of time we see the step taken by the walk together with the color of the newly arrived at location. S. Kalikow proved that ifd = 1 and the random walk is simple, then this process is not Bernoulli. We generalize his result by proving that it is not Bernoulli ind = 2, Bernoulli but not Weak Bernoulli ind = 3 and 4, and Weak Bernoulli ind ≥ 5. These properties are related to the intersection behavior of the past and the future of simple random walk. We obtain similar results for general random walks on ℤ^d, leading to an almost complete classification. For example, ind = 1, if a step of sizex has probability proportional to l/|x|^α (x ⊋ 0), then theT, T ^-1-process is not Bernoulli when α ≥2, Bernoulli but not Weak Bernoulli when 3/2 ≤α < 2, and Weak Bernoulli when 1 < α < 3/2. Research partially carried out while a guest of the Department of Mathematics, Chalmers University of Technology, Sweden in January 1996. Research supported by grants from the Swedish Natural Science Research Council and from the Royal Swedish Academy of Sciences.     

Passage times of random walks and Lévy processes across power law boundaries

We establish an integral test involving only the distribution of the increments of a random walk S which determines whether limsup _n→∞(S_n/n^κ) is almost surely zero, finite or infinite when 1/2<κ<1 and a typical step in the random walk has zero mean. This completes the results of Kesten and Maller [9] concerning finiteness of one-sided passage times over power law boundaries, so that we now have quite explicit criteria for all values of κ≥0. The results, and those of [9], are also extended to Lévy processes.This work is partially supported by ARC Grant DP0210572.     

Stability and other limit laws for exit times of random walks from a strip or a halfplane

We show that the passage time, T^*(r), of a random walk S_n above a horizontal boundary at r (r≥0) is stable (in probability) in the sense that as r→∞ for a deterministic function C(r)>0, if and only if the random walk is relatively stable in the sense that as n→∞ for a deterministic sequence B_n>0. The stability of a passage time is an important ingredient in some proofs in sequential analysis, where it arises during applications of Anscombe's Theorem. We also prove a counterpart for the almost sure stability of T^*(r), which we show is equivalent to E|X|<∞, EX>0. Similarly, counterparts for the exit of the random walk from the strip {|y|≤r} are proved. The conditions arefurther related to the relative stability of the maximal sum and the maximum modulus of the sums. Another result shows that the exit position of the random walk outside the boundaries at ±r drifts to ∞ as r→∞ if and only if the random walk drifts to ∞.     

Clifford-algebraic random walks on the hypercube

The n-dimensional hypercube is a simple graph on 2ⁿ vertices labeled by binary strings, or words, of length n. Pairs of vertices are adjacent if and only if they differ in exactly one position as binary words; i.e., the Hamming distance between the words is one. A discrete-time random walk is easily defined on the hypercube by “flipping” a randomly selected digit from 0 to 1 or vice-versa at each time step. By associating the words as blades in a Clifford algebra of particular signature, combinatorial properties of the geometric product can be used to represent this random walk as a sequence within the algebra. A closed-form formula is revealed which yields probability distributions on the vertices of the hypercube at any time k ≥ 0 by a formal power series expansion of elements in the algebra. Furthermore, by inducing a walk on a larger Clifford algebra, probabilities of self-avoiding walks and expected first hitting times of specific vertices are recovered. Moreover, because the Clifford algebras used in the current work are canonically isomorphic to fermion algebras, everything appearing here can be rewritten using fermion creation/annihilation operators, making the discussion relevant to quantum mechanics and/or quantum computing.     

Phase Transition in Vertex-Reinforced Random Walks on {\mathbb{Z}} with Non-linear Reinforcement

Vertex-reinforced random walk is a random process which visits a site with probability proportional to the weight w _k of the number k of previous visits. We show that if w _k ∼ k ^α, then there is a large time T ₀ such that after T ₀ the walk visits 2, 5, or ∞ sites when α < 1, = 1, or > 1, respectively. More general results are also proven.      

Weak interaction limits for one-dimensional random polymers

 In this paper we present a new and flexible method to show that, in one dimension, various self-repellent random walks converge to self-repellent Brownian motion in the limit of weak interaction after appropriate space-time scaling. Our method is based on cutting the path into pieces of an appropriately scaled length, controlling the interaction between the different pieces, and applying an invariance principle to the single pieces. In this way, we show that the self-repellent random walk large deviation rate function for the empirical drift of the path converges to the self-repellent Brownian motion large deviation rate function after appropriate scaling with the interaction parameters. The method is considerably simpler than the approach followed in our earlier work, which was based on functional analytic arguments applied to variational representations and only worked in a very limited number of situations. We consider two examples of a weak interaction limit: (1) vanishing self-repellence, (2) diverging step variance. In example (1), we recover our earlier scaling results for simple random walk with vanishing self-repellence and show how these can be extended to random walk with steps that have zero mean and a finite exponential moment. Moreover, we show that these scaling results are stable against adding self-attraction, provided the self-repellence dominates. In example (2), we prove a conjecture by Aldous for the scaling of self-avoiding walk with diverging step variance. Moreover, we consider self-avoiding walk on a two-dimensional horizontal strip such that the steps in the vertical direction are uniform over the width of the strip and find the scaling as the width tends to infinity. Received: 6 March 2002 / Revised version: 11 October 2002 / Published online: 21 February 2003 Mathematics Subject Classification (2000): 60F05, 60F10, 60J55, 82D60 Key words or phrases: Self-repellent random walk and Brownian motion – Invariance principles – Large deviations – Scaling limits – Universality     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Invariance principle for nonhomogeneous random walks on the grid ℤ1

A nonhomogeneous random walk on the grid ℤ¹ with transition probabilities that differ from those of a certain homogeneous random walk only at a finite number of points is considered. Trajectories of such a walk are proved to converge to trajectories of a certain generalized diffusion process on the line. This result is a generalization of the well-known invariance principle for the sums of independent random variables and Brownian motion. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 459–472, September, 1999.     

Existence and regularity properties of non-isotropic singular elliptic equations

We establish existence and sharp regularity results for solutions to singular elliptic equations of the order u ^−β , 0 < β < 1, with gradient dependence and involving a forcing term λ f(x, u). Our approach is based on a singularly perturbed technique. We show that if the forcing parameter λ > 0 is large enough, our solution is positive. For λ small solutions vanish on a nontrivial set and therefore they exhibit free boundaries. We also establish regularity results for the free boundary and study the asymptotic behavior of the problem as b\searrow 0{\beta\searrow 0} and b\nearrow 1{\beta\nearrow 1}. In the former, we show that our solutions u _β converge to a C ^1,1 function which is a solution to an obstacle type problem. When b\nearrow 1{\beta\nearrow 1} we recover the Alt-Caffarelli theory.     

TheT, T −1-process, finitary codings and weak Bernoulli

We give an elementary proof that the second coordinate (the scenery process) of theT, T ⁻¹-process associated to any mean zero i.i.d. random walk onZ ^d is not a finitary factor of an i.i.d. process. In particular, this yields an elementary proof that the basicT, T ⁻¹-process is not finitarily isomorphic to a Bernoulli shift (the stronger fact that it is not Bernoulli was proved by Kalikow). This also provides (using past work of den Hollander and the author) an elementary example, namely theT, T ⁻¹-process in 5 dimensions, of a process which is weak Bernoulli but not a finitary factor of an i.i.d. process. An example of such a process was given earlier by del Junco and Rahe. The above holds true for arbitrary stationary recurrent random walks as well. On the other hand, if the random walk is Bernoulli and transient, theT, T ⁻¹-process associated to it is also Bernoulli. Finally, we show that finitary factors of i.i.d. processes with finite expected coding volume satisfy certain notions of weak Bernoulli in higher dimensions which have been previously introduced and studied in the literature. In particular, this yields (using past work of van den Berg and the author) the fact that the Ising model is weak Bernoulli throughout the subcritical regime.     

Loop-Erased Random Walk on Finite Graphs and the Rayleigh Process

Let (G _n ) _n=1^∞ be a sequence of finite graphs, and let Y _t be the length of a loop-erased random walk on G _n after t steps. We show that for a large family of sequences of finite graphs, which includes the case in which G _n is the d-dimensional torus of size-length n for d≥4, the process (Y _t ) _t=0^∞, suitably normalized, converges to the Rayleigh process introduced by Evans, Pitman, and Winter. Our proof relies heavily on ideas of Peres and Revelle, who used loop-erased random walks to show that the uniform spanning tree on large finite graphs converges to the Brownian continuum random tree of Aldous. Supported in part by NSF Grant DMS-0504882.     

Almost-sure central limit theorem for a Markov model of random walk in dynamical random environment

Summary We consider a model of random walk on ℤ^ν, ν≥2, in a dynamical random environment described by a field ξ={ξ _t (x): (t,x)∈ℤ^ν+1}. The random walk transition probabilities are taken as P(X _{t +1}= y|X _t = x,ξ _t =η) =P ₀( y−x)+ c(y−x;η(x)). We assume that the variables {ξ _t (x):(t,x) ∈ℤ^ν+1} are i.i.d., that both P ₀(u) and c(u;s) are finite range in u, and that the random term c(u;·) is small and with zero average. We prove that the C.L.T. holds almost-surely, with the same parameters as for P ₀, for all ν≥2. For ν≥3 there is a finite random (i.e., dependent on ξ) correction to the average of X _t , and there is a corresponding random correction of order to the C.L.T.. For ν≥5 there is a finite random correction to the covariance matrix of X _t and a corresponding correction of order to the C.L.T.. Proofs are based on some new L ^p estimates for a class of functionals of the field. Received: 4 January 1996/In revised form: 26 May 1997     

The speed of biased random walk on percolation clusters

 We consider biased random walk on supercritical percolation clusters in ℤ². We show that the random walk is transient and that there are two speed regimes: If the bias is large enough, the random walk has speed zero, while if the bias is small enough, the speed of the random walk is positive. Received: 20 November 2002 / Revised version: 17 January 2003 Published online: 15 April 2003 Research supported by Microsoft Research graduate fellowship. Research partially supported by the DFG under grant SPP 1033. Research partially supported by NSF grant #DMS-0104073 and by a Miller Professorship at UC Berkeley. Mathematics Subject Classification (2000): 60K37; 60K35; 60G50 Key words or phrases: Percolation – Random walk     

On the range of random walk

Let {S _n , n=0, 1, 2, …} be a random walk (S _n being thenth partial sum of a sequence of independent, identically distributed, random variables) with values inE _d , thed-dimensional integer lattice. Letf _n =Prob {S ₁ ≠ 0, …,S _n −1 ≠ 0,S _n =0 |S ₀=0}. The random walk is said to be transient if and strongly transient if . LetR _n =cardinality of the set {S ₀,S ₁, …,S _n }. It is shown that for a strongly transient random walk with p<1, the distribution of [R _n −np]/σ √n converges to the normal distribution with mean 0 and variance 1 asn tends to infinity, where σ is an appropriate positive constant. The other main result concerns the “capacity” of {S ₀, …,S _n }. For a finite setA inE _d , let C(A=Σ _x∈A ) Prob {S _n ∉A, n≧1 |S ₀=x} be the capacity ofA. A strong law forC{S ₀, …,S _n } is proved for a transient random walk, and some related questions are also considered. This research was partially supported by the National Science Foundation.     

Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

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.     

Moderate Deviations for Random Sums of Heavy-Tailed Random Variables

Let {Xn;n≥ 1} be a sequence of independent non-negative random variables with common distribution function F having extended regularly varying tail and finite mean μ = E（X1） and let {N（t）; t ≥0} be a random process taking non-negative integer values with finite mean λ（t） = E（N（t）） and independent of {Xn; n ≥1}. In this paper, asymptotic expressions of P（（X1 ＋… ＋XN（t）） -λ（t）μ 〉 x） uniformly for x ∈[γb（t）, ∞） are obtained, where γ〉 0 and b（t） can be taken to be a positive function with limt→∞ b（t）/λ（t） = 0.     

The hitting distributions of a half real line for two-dimensional random walks

For every two-dimensional random walk on the square lattice Z ² having zero mean and finite variance we obtain fine asymptotic estimates of the probability that the walk hits the negative real line for the first time at a site (s,0), when it is started at a site far from both (0,s) and the origin.     

Finite covers of random 3-manifolds

A 3-manifold is Haken if it contains a topologically essential surface. The Virtual Haken Conjecture posits that every irreducible 3-manifold with infinite fundamental group has a finite cover which is Haken. In this paper, we study random 3-manifolds and their finite covers in an attempt to shed light on this difficult question. In particular, we consider random Heegaard splittings by gluing two handlebodies by the result of a random walk in the mapping class group of a surface. For this model of random 3-manifold, we are able to compute the probabilities that the resulting manifolds have finite covers of particular kinds. Our results contrast with the analogous probabilities for groups coming from random balanced presentations, giving quantitative theorems to the effect that 3-manifold groups have many more finite quotients than random groups. The next natural question is whether these covers have positive betti number. For abelian covers of a fixed type over 3-manifolds of Heegaard genus 2, we show that the probability of positive betti number is 0.In fact, many of these questions boil down to questions about the mapping class group. We are led to consider the action of the mapping class group of a surface Σ on the set of quotients π₁(Σ)→Q. If Q is a simple group, we show that if the genus of Σ is large, then this action is very mixing. In particular, the action factors through the alternating group of each orbit. This is analogous to Goldman’s theorem that the action of the mapping class group on the SU(2) character variety is ergodic. Mathematics Subject Classification (2000) 57M50, 57N10