A subdiffusive behaviour of recurrent random walk in random environment on a regular tree

We are interested in the random walk in random environment on an infinite tree. Lyons and Pemantle (Ann. Probab. 20, 125–136, 1992) give a precise recurrence/transience criterion. Our paper focuses on the almost sure asymptotic behaviours of a recurrent random walk (X _n ) in random environment on a regular tree, which is closely related to Mandelbrot’s (C. R. Acad. Sci. Paris 278, 289–292, 1974) multiplicative cascade. We prove, under some general assumptions upon the distribution of the environment, the existence of a new exponent such that behaves asymptotically like . The value of ν is explicitly formulated in terms of the distribution of the environment.      

On the spectrum of lamplighter groups and percolation clusters

Let be a finitely generated group and X its Cayley graph with respect to a finite, symmetric generating set S. Furthermore, let be a finite group and the lamplighter group (wreath product) over with group of “lamps” . We show that the spectral measure (Plancherel measure) of any symmetric “switch–walk–switch” random walk on coincides with the expected spectral measure (integrated density of states) of the random walk with absorbing boundary on the cluster of the group identity for Bernoulli site percolation on X with parameter . The return probabilities of the lamplighter random walk coincide with the expected (annealed) return probabilities on the percolation cluster. In particular, if the clusters of percolation with parameter are almost surely finite then the spectrum of the lamplighter group is pure point. This generalizes results of Grigorchuk and Żuk, resp. Dicks and Schick regarding the case when is infinite cyclic. Analogous results relate bond percolation with another lamplighter random walk. In general, the integrated density of states of site (or bond) percolation with arbitrary parameter is always related with the Plancherel measure of a convolution operator by a signed measure on , where or another suitable group. M. Neuhauser’s research supported by the Marie-Curie Excellence Grant MEXT-CT-2004-517154. The research of W. Woess was partially supported by Austrian Science Fund (FWF) P18703-N18.     

The Poisson boundary of lamplighter random walks on trees

Let be the homogeneous tree with degree q + 1 ≥ 3 and a finitely generated group whose Cayley graph is . The associated lamplighter group is the wreath product , where is a finite group. For a large class of random walks on this group, we prove almost sure convergence to a natural geometric boundary. If the probability law governing the random walk has finite first moment, then the probability space formed by this geometric boundary together with the limit distribution of the random walk is proved to be maximal, that is, the Poisson boundary. We also prove that the Dirichlet problem at infinity is solvable for continuous functions on the active part of the boundary, if the lamplighter “operates at bounded range”. Supported by ESF program RDSES and by Austrian Science Fund (FWF) P15577.     

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.     

More Randomness of Environment Does Not Always Slow Down a Random Walk

We consider a random walk on in a stationary and ergodic random environment, whose states are called types of the vertices of . We find conditions for which the speed of the random walk is positive. In the case of a Markov chain environment with finitely many states, we give an explicit formula for the speed and for the asymptotic proportion of time spent at vertices of a certain type. Using these results, we compare the speed of random walks on in environments of varying randomness.     

Random walk in random scenery and self-intersection local times in dimensions d ≥ 5

Let {S _k , k ≥ 0} be a symmetric random walk on , and an independent random field of centered i.i.d. random variables with tail decay . We consider a random walk in random scenery, that is . We present asymptotics for the probability, over both randomness, that {X _n > n ^β} for β > 1/2 and α > 1. To obtain such asymptotics, we establish large deviations estimates for the self-intersection local times process , where l _n (x) is the number of visits of site x up to time n.      

Generating Random Elements in SL n (F q ) by Random Transvections

This paper studies a random walk based on random transvections in SL _n(F _q ) and shows that, given > 0, there is a constant c such that after n + c steps the walk is within a distance from uniform and that after n – c steps the walk is a distance at least 1 – from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL _n(F _q ) to compare them with random transvections.     

Dynamic ℤ d -Random Walks in a Random Scenery: A Strong Law of Large Numbers

In this paper, we study a _d -random walk on nearest neighbours with transition probabilities generated by a dynamical system . We prove, at first, that under some hypotheses, verifies a local limit theorem. Then, we study these walks in a random scenery , a sequence of independent, identically distributed and centred random variables and show that for certain dynamic random walks, satisfies a strong law of large numbers.     

The Spectrum of a Random Geometric Graph is Concentrated

Consider n points, x ₁,... , x _n , distributed uniformly in [0, 1] ^d . Form a graph by connecting two points x _i and x _j if . This gives a random geometric graph, , which is connected for appropriate r(n). We show that the spectral measure of the transition matrix of the simple random walk on is concentrated, and in fact converges to that of the graph on the deterministic grid.      

A Slow Transient Diffusion in a Drifted Stable Potential

We consider a diffusion process X in a random potential of the form , where is a positive drift and is a strictly stable process of index with positive jumps. Then the diffusion is transient and converges in law towards an exponential distribution. This behaviour contrasts with the case where is a drifted Brownian motion and provides an example of a transient diffusion in a random potential which is as “slow” as in the recurrent setting.      

Drift to Infinity and the Strong Law for Subordinated Random Walks and Lévy Processes

We determine conditions under which a subordinated random walk of the form tends to infinity almost surely (a.s), or tends to infinity a.s., where {N(n)} is a (not necessarily integer valued) renewal process, denotes the integer part of N(n), and S_n is a random walk independent of {N(n)}. Thus we obtain versions of the Alternatives, for drift to infinity, or for divergence to infinity in the strong law, for . A complication is that is not, in general, itself, a random walk. We can apply the results, for example, to the case when N(n)= n, > 0, giving conditions for lim , a.s., and lim sup , a.s., etc. For some but not all of our results, N(1) is assumed to have finite expectation. Examples show that this is necessary for the kind of behaviour we consider. The results are also shown to hold in the same degree of generality for subordinated Lévy processes.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

Uniform Comparison of Tails of (Non-Symmetric) Probability Measures and Their Symmetrized Counterparts with Applications

Let (, ) be a separable Banach space and let be a class of probability measures on , and let denote the symmetrization of . We provide two sufficient conditions (one in terms of certain quantiles and the other in terms of certain moments of relative to μ and , ) for the “uniform comparison” of the μ and measure of the complements of the closed balls of centered at zero, for every . As a corollary to these “tail comparison inequalities,” we show that three classical results (the Lévy-type Inequalities, the Kwapień-Contraction Inequality, and a part of the It?–Nisio Theorem) that are valid for the symmetric (but not for the general non-symmetric) independent -valued random vectors do indeed hold for the independent random vectors whose laws belong to any which satisfies one of the two noted conditions and which is closed under convolution. We further point out that these three results (respectively, the tail comparison inequalities) are valid for the centered log-concave, as well as, for the strictly α-stable (or the more general strictly (r, α) -semistable) α ≠ 1 random vectors (respectively, probability measures). We also present several examples which we believe form a valuable part of the paper.      

A renormalization approach to irrational rotations

We introduce a renormalization procedure which allows us to study in a unified and concise way different properties of the irrational rotations on the unit circle , . In particular, we obtain sharp results for the diffusion of the walk on generated by the location of points of the sequence {n α + β} on a binary partition of the unit interval. Finally, we give some applications of our method.      

Is the Approximation Rate for European Pay-offs in the Black–Scholes Model Always 1/ \sqrt{n}

For a Borel-function , we consider the approximation of a random variable f(W ₁) with by stochastic integrals with respect to the Brownian motion and the geometric Brownian motion, where the integrands are piecewise constant within certain deterministic time intervals. In earlier papers it has been shown that under certain regularity conditions the optimal approximation rate is 1/ , if one optimizes over deterministic time-nets of cardinality n. We will show the existence of random variables f(W ₁) such that the approximation error tends as slowly to zero as one wishes.     

Limit distributions of upper order statistics for families of multivariate distributions

We consider a portfolio of dependent exchangeable random variables , where the dependence structure is generated by a mixture model (Archimedean copulas belong to this class of models). Define the ordered sample . We prove results of the following type: fix and choose appropriately, then converges in distribution to a random vector as , for which we can explicitly give the distribution.     

Projective re-normalization for improving the behavior of a homogeneous conic linear system

In this paper we study the homogeneous conic system . We choose a point that serves as a normalizer and consider computational properties of the normalized system . We show that the computational complexity of solving F via an interior-point method depends only on the complexity value of the barrier for C and on the symmetry of the origin in the image set , where the symmetry of 0 in is

On the Kernel Rule for Function Classification

Let X be a random variable taking values in a function space , and let Y be a discrete random label with values 0 and 1. We investigate asymptotic properties of the moving window classification rule based on independent copies of the pair (X,Y). Contrary to the finite dimensional case, it is shown that the moving window classifier is not universally consistent in the sense that its probability of error may not converge to the Bayes risk for some distributions of (X,Y). Sufficient conditions both on the space and the distribution of X are then given to ensure consistency.     

On The Invariant Measure of a Positive Recurrent Diffusion in $${\mathbb{R}}$$

Given a one-dimensional positive recurrent diffusion governed by the Stratonovich SDE , we show that the associated stochastic flow of diffeomorphisms focuses as fast as , where is the finite stationary measure. Moreover, if the drift is reversed and the diffeomorphism is inverted, then the path function so produced tends, independently of its starting point, to a single (random) point whose distribution is . Applications to stationary solutions of X _t , asymptotic behavior of solutions of SPDEs and random attractors are offered. This paper was written while the author was visiting Northwestern University and the opinions expressed in it are those of the author alone and do not necessarily reflect the views of Merrill Lynch, its subsidiaries or affiliates.     

Number Variance of Random Zeros on Complex Manifolds

We show that the variance of the number of simultaneous zeros of m i.i.d. Gaussian random polynomials of degree N in an open set with smooth boundary is asymptotic to , where is a universal constant depending only on the dimension m. We also give formulas for the variance of the volume of the set of simultaneous zeros in U of k < m random degree-N polynomials on . Our results hold more generally for the simultaneous zeros of random holomorphic sections of the N-th power of any positive line bundle over any m-dimensional compact K?hler manifold. Received: August 2006 Revision: March 2007 Accepted: April 2007