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.     

Decoupling inequalities and interlacement percolation on <Emphasis Type="Italic">G</Emphasis>×ℤ

We study the percolative properties of random interlacements on G×ℤ, where G is a weighted graph satisfying certain sub-Gaussian estimates attached to the parameters α>1 and 2≤β≤α+1, describing the respective polynomial growths of the volume on G and of the time needed by the walk on G to move to a distance. We develop decoupling inequalities, which are a key tool in showing that the critical level u _∗ for the percolation of the vacant set of random interlacements is always finite in our set-up, and that it is positive when α≥1+β/2. We also obtain several stretched exponential controls both in the percolative and non-percolative phases of the model. Even in the case where G=ℤ ^d , d≥2, several of these results are new.     

Quenched invariance principle for simple random walk on percolation clusters

We consider the simple random walk on the (unique) infinite cluster of super-critical bond percolation in ℤ ^d with d≥2. We prove that, for almost every percolation configuration, the path distribution of the walk converges weakly to that of non-degenerate, isotropic Brownian motion. Our analysis is based on the consideration of a harmonic deformation of the infinite cluster on which the random walk becomes a square-integrable martingale. The size of the deformation, expressed by the so called corrector, is estimated by means of ergodicity arguments.     

Isomorphism rigidity of irreducible algebraic ℤd-actions

An irreducible algebraic ℤ ^d -actionα on a compact abelian group X is a ℤ ^d -action by automorphisms of X such that every closed, α-invariant subgroup Y⊊X is finite. We prove the following result: if d≥2, then every measurable conjugacy between irreducible and mixing algebraic ℤ ^d -actions on compact zero-dimensional abelian groups is affine. For irreducible, expansive and mixing algebraic ℤ ^d -actions on compact connected abelian groups the analogous statement follows essentially from a result by Katok and Spatzier on invariant measures of such actions (cf. [4] and [3]). By combining these two theorems one obtains isomorphism rigidity of all irreducible, expansive and mixing algebraic ℤ ^d -actions with d≥2. Oblatum 30-IX-1999 & 4-V-2000?Published online: 16 August 2000     

The relative trace formula for groups with involution

A theorem of Bourgain states that the harmonic measure for a domain in ℝ ^d is supported on a set of Hausdorff dimension strictly less thand [2]. We apply Bourgain’s method to the discrete case, i.e., to the distribution of the first entrance point of a random walk into a subset of ℤ ^d ,d≥2. By refining the argument, we prove that for allβ>0 there existsρ(d,β)<d andN(d,β), such that for anyn>N(d,β), anyx ∈ ℤ ^d , and anyA ⊂ {1,…,n} ^d •{y∈ℤ whereν _A,x (y) denotes the probability thaty is the first entrance point of the simple random walk starting atx intoA. Furthermore,ρ must converge tod asβ → ∞. Supported by Swiss NF grant 20-55648.98.     

Equivalence of renewal sequences and isomorphism of random walks

We show that centred aperiodic random walks on ℤ ^d whose jump random variables are inL ²√log⁺ L have equivalent renewal sequences. An isomorphism theorem is deduced. Research was done while the author was visiting the Centre de Physique Theorique, Luminy-Marseille, France. Research supported by NSF Grant DMS 91-00725.     

Rate of escape on the lamplighter tree

Suppose we are given a homogeneous tree {ie173-01} of degree q ≥ 3, where at each vertex sits a lamp, which can be switched on or off. This structure can be described by the wreath product (ℤ/2)≀Γ, where Γ = * _i=1^qℤ/2 is the free product group of q factors ℤ/2. We consider a transient random walk on a Cayley graph of (ℤ/2) ≀Γ, for which we want to compute lower and upper bounds for the rate of escape, that is, the speed at which the random walk flees to infinity. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 50, Functional Analysis, 2007.     

Limsup results and LIL for partial sum processes of a Gaussian random field

Let {ξ _j ; j ∈ ℤ₊ ^d be a centered stationary Gaussian random field, where ℤ₊ ^d is the d-dimensional lattice of all points in d-dimensional Euclidean space ℝ^d, having nonnegative integer coordinates. For each j = (j ₁ , ..., jd) in ℤ₊ ^d , we denote |j| = j ₁ ... j _d and for m, n ∈ ℤ₊ ^d , define S(m, n] = Σ _m<j≤n ζ _j , σ²(|n−m|) = ES ² (m, n], S _n = S(0, n] and S ₀ = 0. Assume that σ(|n|) can be extended to a continuous function σ(t) of t > 0, which is nondecreasing and regularly varying with exponent α at b ≥ 0 for some 0 < α < 1. Under some additional conditions, we study limsup results for increments of partial sum processes and prove as well the law of the iterated logarithm for such partial sum processes. Research supported by NSERC Canada grants at Carleton University, Ottawa     

On polynomial symbols for subdivision schemes

Given a dilation matrix A :ℤ^d→ℤ^d, and G a complete set of coset representatives of 2π(A ^−Tℤ^d/ℤ^d), we consider polynomial solutions M to the equation ∑ _g∈G M(ξ+g)=1 with the constraints that M≥0 and M(0)=1. We prove that the full class of such functions can be generated using polynomial convolution kernels. Trigonometric polynomials of this type play an important role as symbols for interpolatory subdivision schemes. For isotropic dilation matrices, we use the method introduced to construct symbols for interpolatory subdivision schemes satisfying Strang–Fix conditions of arbitrary order. Research partially supported by the Danish Technical Science Foundation, Grant No. 9701481, and by the Danish SNF-PDE network.     

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     

A new inductive approach to the lace expansion for self-avoiding walks

Summary. We introduce a new inductive approach to the lace expansion, and apply it to prove Gaussian behaviour for the weakly self-avoiding walk on ℤ ^d where loops of length m are penalised by a factor e ^{−β/m p} (0<β≪1) when: (1) d>4, p≥0; (2) d≤4, . In particular, we derive results first obtained by Brydges and Spencer (and revisited by other authors) for the case d>4, p=0. In addition, we prove a local central limit theorem, with the exception of the case d>4, p=0. Received: 29 October 1997 / In revised form: 15 January 1998     

Quenched invariance principles for walks on clusters of percolation or among random conductances

In this work we principally study random walk on the supercritical infinite cluster for bond percolation on ^d. We prove a quenched functional central limit theorem for the walk when d4. We also prove a similar result for random walk among i.i.d. random conductances along nearest neighbor edges of ^d, when d1.V. Sidoravicius would like to thank the FIM for financial support and hospitality during his multiple visits to ETH. His research was also partially supported by FAPERJ and CNPq.     

New results on measures of maximal entropy

It has recently been demonstrated that there are strongly irreducible subshifts of finite type with more than one measure of maximal entropy. Here we obtain a number of results concerning the uniqueness of the measure of maximal entropy. In addition, we construct for anyd≥2 andk a strongly irreducible subshift of finite type ind dimensions with exactlyk ergodic (extremal) measures of maximal entropy. Ford≥3, we construct a strongly irreducible subshift of finite type ind dimensions with a continuum of ergodic measures of maximal entropy. Research supported in part by AFOSR grant # 91-0215 and NSF grant # DMS-9103738. Research supported by the Swedish National Science Foundation.     

Moments and Distribution of the Local Times of a Transient Random Walk on ℤ d

Consider an arbitrary transient random walk on ℤ ^d with d∈ℕ. Pick α∈[0,∞), and let L _n (α) be the spatial sum of the αth power of the n-step local times of the walk. Hence, L _n (0) is the range, L _n (1)=n+1, and for integers α, L _n (α) is the number of the α-fold self-intersections of the walk. We prove a strong law of large numbers for L _n (α) as n→∞. Furthermore, we identify the asymptotic law of the local time in a random site uniformly distributed over the range. These results complement and contrast analogous results for recurrent walks in two dimensions recently derived by Černy (Stoch. Proc. Appl. 117:262–270, 2007). Although these assertions are certainly known to experts, we could find no proof in the literature in this generality.      

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Diffusive scaling of the spectral gap for the dilute Ising lattice-gas dynamics below the percolation threshold

We consider a conservative stochastic lattice-gas dynamics reversible with respect to the canonical Gibbs measure of the bond dilute Ising model on ℤ ^d at inverse temperature β. When the bond dilution density p is below the percolation threshold we prove that for any particle density and any β, with probability one, the spectral gap of the generator of the dyamics in a box of side L centered at the origin scales like L ⁻². Such an estimate is then used to prove a decay to equilibrium for local functions of the form where ε is positive and arbitrarily small and α = ? for d = 1, α=1 for d≥2. In particular our result shows that, contrary to what happes for the Glauber dynamics, there is no dynamical phase transition when β crosses the critical value β _c of the pure system. Received: 10 April 2000 / Revised version: 23 October 2000 / Published online: 5 June 2001     

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.     

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     

Two order superconvergence of finite element methods for Sobolev equations

We consider finite element methods applied to a class of Sobolev equations inR ^d(d ≥ 1). Global strong superconvergence, which only requires that partitions are quais-uniform, is investigated for the error between the approximate solution and the Ritz-Sobolev projection of the exact solution. Two order superconvergence results are demonstrated inW ^1,p (Ω) andL _p(Ω) for 2 ≤p < ∞.