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.      

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.     

Distances in random graphs with infinite mean degrees

We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function is regularly varying with exponent . In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount, is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two papers study the case where , and , respectively. The main result of this paper is that the graph distance for converges in distribution to a random variable with probability mass exclusively on the points and . We also consider the case where we condition the degrees to be at most for some , where is the size of the graph. For fixed and such that , the hopcount converges to in probability, while for , the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory. AMS 2000 Subject Classifications Primary—60G70; Secondary—05C80     

Excited random walk against a wall

We analyze random walk in the upper half of a three-dimensional lattice which goes down whenever it encounters a new vertex, a.k.a. excited random walk. We show that it is recurrent with an expected number of returns of .     

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.      

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.      

The disconnection exponent for simple random walk

LetS(t) denote a simple random walk inZ ² with integer timet. The disconnection exponent is defined by saying the probability that the path ofS starting at 0 and ending at the circle of radiusn disconnects 0 from infinity decays like . We prove that the disconnection exponent is well-defined and equals the disconnection exponent for Brownian motion which is known to exist. Research supported by the National Science Foundation.     

Sums of random symmetric matrices and quadratic optimization under orthogonality constraints

Let B _i be deterministic real symmetric m × m matrices, and ξ _i be independent random scalars with zero mean and “of order of one” (e.g., ). We are interested to know under what conditions “typical norm” of the random matrix is of order of 1. An evident necessary condition is , which, essentially, translates to ; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S _N is : for all Ω > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints , where F is quadratic in X = (X ₁,... ,X _k ). We show that when F is convex in every one of X _j , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices . Research was partly supported by the Binational Science Foundation grant #2002038.     

The exponent for the mean square displacement of self-avoiding random walk on the Sierpinski gasket

The authors rigorously prove that the exponent for the mean square displacement of self-avoiding random walk on the Sierpinski gasket is

A Marstrand theorem for measures with polytope density

Given and any centrally symmetric convex polytope , define we prove that if a Radon measure μ has the property then s is an integer. For the case Θ is the Euclidean ball, this result was first proved by Marstrand in 1955 for Hausdorff measure in the plane (Marstrand in Proc Lond Math Soc 3(4):257–302, 1954) and later for general Radon measures in (Marstrand in Trans Am Math Soc 205:369–392, 1964).     

Central limit theorem for traces of large random symmetric matrices with independent matrix elements

We study Wigner ensembles of symmetric random matricesA=(a _ij ),i, j=1,...,n with matrix elementsa _ij ,ij being independent symmetrically distributed random variables

The relation of dimension,entropy and Lyapunov exponent in random case

We consider random systems generated by two-sided compositions of random surface diffeomorphisms,together with an ergodic Borel probability measure μ.Let D(μω)be its dimension of the sample measure,then we prove a formula relating D(μω)to the entropy and Lyapunov exponents of the random system,where D(μω)is dimHμω,-/dinBμω,or-/dimBμω.     

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.     

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.     

Moments of a statistic caused by random combinations or random matings

Summary Given two sets of sizek, {α ₁...,α _k} and {β ₁...,β _k} there arek! possible combinations of these two , and suppose there is apriori given a number corresponding to the partnership (α ₁,β _j}. The average of the numbers corresponding to is a random variable, and this paper presents the first five moments of the average, and an application in the study of an isolated human population is demonstrated.     

The spectra of lamplighter groups and Cayley machines

We calculate the spectra and spectral measures associated to random walks on restricted wreath products G wr , with G a finite group, by calculating the Kesten—von Neumann—Serre spectral measures for the random walks on Schreier graphs of certain groups generated by automata. This generalises the work of Grigorchuk and Żuk on the lamplighter group. In the process we characterise when the usual spectral measure for a group generated by an automaton coincides with the Kesten—von Neumann—Serre spectral measure.     

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.     

The norm of products of free random variables

Let X _i denote free identically-distributed random variables. This paper investigates how the norm of products behaves as n approaches infinity. In addition, for positive X _i it studies the asymptotic behavior of the norm of where denotes the symmetric product of two positive operators: . It is proved that if EX _i = 1, then is between and c ₂ n for certain constant c ₁ and c ₂. For it is proved that the limit of exists and equals Finally, if π is a cyclic representation of the algebra generated by X _i , and if ξ is a cyclic vector, then for all n. These results are significantly different from analogous results for commuting random variables.     

Large deviations for Brownian motion in a random scenery

We prove large deviations principles in large time, for the Brownian occupation time in random scenery . The random field is constant on the elements of a partition of ^d into unit cubes. These random constants, say consist of i.i.d. bounded variables, independent of the Brownian motion {B_s,s0}. This model is a time-continuous version of Kesten and Spitzer's random walk in random scenery. We prove large deviations principles in ``quenched' and ``annealed' settings.Mathematics Subject Classification (2000):60F10, 60J55, 60K37     

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.