Random Walks on Wreath Products of Groups

We bound the rate of convergence to uniformity for a certain random walk on the complete monomial groups GS _n for any group G. Specifically, we determine that n log n+ n log (|G|–1|) steps are both necessary and sufficient for ² distance to become small. We also determine that n log n steps are both necessary and sufficient for total variation distance to become small. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group ₂S _n , the generalized symmetric group _m S _n , and S _m S _n . In the special case of the hyperoctahedral group, our random walk exhibits the cutoff phenomenon.     

Random Walks on Dihedral Groups

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p ² steps are necessary for the walk to become close to uniformly distributed on all of D _2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p ^2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D _2p . We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D _2p .     

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.     

Random walks supported on random points ofZ/nZ

Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn ^2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn ^2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn) ^a , we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan     

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.     

Long Excursions of a Random Walk

In Csáki et al. ⁽¹⁾ and Révész and Willekens⁽⁹⁾ it was proved that the length of the longest excursion among the first n excursions of a plane random walk is nearly equal to the total sum of the lenghts of these excursions. In this paper several results are proved in the same spirit, for plane random walks and for random walks in higher dimensions.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

Random walks in a convex body and an improved volume algorithm

We give a randomized algorithm using O(n⁷ log² n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n⁶ log⁴ n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n⁵ log⁴ n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n⁶ log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.     

Valleys and the Maximum Local Time for Random Walk in Random Environment

Let ξ (n, x) be the local time at x for a recurrent one-dimensional random walk in random environment after n steps, and consider the maximum ξ^*(n) = max _x ξ(n, x). It is known that lim sup is a positive constant a.s. We prove that lim inf is a positive constant a.s. this answers a question of P. Révész [5]. The proof is based on an analysis of the valleys in the environment, defined as the potential wells of record depth. In particular, we show that almost surely, at any time n large enough, the random walker has spent almost all of its lifetime in the two deepest valleys of the environment it has encountered. We also prove a uniform exponential tail bound for the ratio of the expected total occupation time of a valley and the expected local time at its bottom.     

Random walk on a discrete Heisenberg group

We use the estimate of paths in Z ² enclosing a null algebraic area to compute correction terms on the random walk on certain discrete Heisenberg groups. We obtain that the probability to return at the origin of the simple random walk on this group is $\frac{1}{4n^{2}}+O(\frac{1}{n^{3}})$ .     

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.     

Random walks on the torus with several generators

Given n vectors {_i} ∈ [0, 1)^d, consider a random walk on the d‐dimensional torus ??^d = ?^d/?^d generated by these vectors by successive addition and subtraction. For certain sets of vectors, this walk converges to Haar (uniform) measure on the torus. We show that the discrepancy distance D(Q*^k) between the kth step distribution of the walk and Haar measure is bounded below by D(Q*^k) ≥ C₁k^?n/2, where C₁ = C(n, d) is a constant. If the vectors are badly approximated by rationals (in a sense we will define), then D(Q*^k) ≤ C₂k^?n/2d for C₂ = C(n, d, _j) a constant. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Topology of Random 2-Complexes

We study the Linial–Meshulam model of random two-dimensional simplicial complexes. One of our main results states that for p≪n ⁻¹ a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π ₁(Y) is free and H ₂(Y)=0, asymptotically almost surely. Our other main result gives a precise threshold for collapsibility of a random 2-complex to a graph in a prescribed number of steps. We also prove that, if the probability parameter p satisfies p≫n ^−1/2+ϵ , where ϵ>0, then an arbitrary finite two-dimensional simplicial complex admits a topological embedding into a random 2-complex, with probability tending to one as n→∞. We also establish several related results; for example, we show that for p<c/n with c<3 the fundamental group of a random 2-complex contains a non-abelian free subgroup. Our method is based on exploiting explicit thresholds (established in the paper) for the existence of simplicial embeddings and immersions of 2-complexes into a random 2-complex.     

Random processes of manifolds in R n

Summary We compute the expected values of certain random variables associated with a random process of manifolds in R ⁿ by inserting certain general formulas of integral geometry into the definition of the moment measures of a point process.Dedicated to Professor Leopold Schmetterer on the occasion of his 60^th Birthday     

Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

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.     

Moments of Absorption Time for a Conditioned Random Walk

A random walk on the set of integers {0,1,2,...,a} with absorbing barriers at 0 and a is considered. The transition times from the integers z (0<z<a) are random variables with finite moments. The nth moment of the time to absorption at a, D_z,n, conditioned on the walk starting at z and being absorbed at a, is discussed, and a difference equation with boundary values and initial values for D_z,n is given. It is solved in several special cases. The problem is motivated by questions from biology about tumor growth and multigene evolution which are discussed.     

Random walks on diestel-leader graphs

We investigate various features of a quite new family of graphs, introduced as a possible example of vertex-transitive graph not roughly isometric with a Cayley graph of some finitely generated group. We exhibit a natural compactification and study a large class of random walks, proving theorems concerning almost sure convergence to the boundary, a strong law of large numbers and a central limit theorem. The asymptotic type of then-step transition probabilities of the simple random walk is determined.     

Random walks and an O*(n5) volume algorithm for convex bodies

Given a high dimensional convex body K⊆ℝⁿ by a separation oracle, we can approximate its volume with relative error ε, using O*(n⁵) oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we use “rounding” followed by a multiphase Monte-Carlo (product estimator) technique. Both parts rely on sampling (generating random points in K), which is done by random walk. Our algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions (diameter) and local obstructions (boundary problems) for fast mixing; and a stepwise interlacing of rounding and sampling. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 1–50, 1997