Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

Tribute to Endre Csáki and Pál Révész

Summary This article provides a glimpse of some of the highlights of the joint work of Endre Csáki and Pál Révész since 1979. The topics of this short exploration of the rich stochastic milieu of this inspiring collaboration revolve around Brownian motion, random walks and their long excursions, local times and additive functionals, iterated processes, almost sure local and global central limit theorems, integral functionals of geometric stochastic processes, favourite sites--favourite values and jump sizes for random walk and Brownian motion, random walking in a random scenery, and large void zones and occupation times for coalescing random walks.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Fonctorialité en K-Théorie bivariante pour les variétés lipschitziennes

Résumé Soit f: M V/F un morphisme continu orienté d'une variété lipschitzienne M dans l'espace des feuilles d'une variété lipschitzienne feuilletée (V,F), et soit C ^* (V,F) la C ^*-algèbre du feuilletage d'A. Connes. On construit un élèment (f) dans le groupe de K-théorie bivariante KK(C ₀ (M); C ^* (V,F)) de G. G. Kasparov et on montre la fonctorialité de cette construction. On utilise l'opérateur de signature de N. Teleman ([42]). Ceci répond pour les variétés lipschitziennes à une conjecture d'A. Connes ([11]) qui a été résolue pour les variétés différentiables dans [13, 8, 19].

---

Let M be a Lipschitz manifold, (V, F) a foliated Lipschitz manifold and let f M V/F be an oriented morphism. Let C ^* (V,F) be the foliation's C ^*-algebra of A. Connes. We then construct an element (f) of the K-theory bivariant group KK(C ₀(M); C ^* (V, F)) of G. G. Kasparov which depends functoriality on f. This uses the signature operator of N. Teleman [42]. It gives a positive answer for Lipschitz manifolds to a conjecture of A. Connes [11] which has been proved for differentiable manifolds in [13, 8, 19].

     

Regularity estimates for solutions of the equations of linear elasticity in convex plane polygonal domains

The Dirichlet problem for the plane elasticity problem on a convex polygonal domain is considered and it is proved that for data in L ² the H ² regularity estimate holds with constants independent of the Lamé coefficients.     

Walks on the slit plane

 In the first part of this paper, we enumerate exactly walks on the square lattice that start from the origin, but otherwise avoid the half-line . We call them walks on the slit plane. We count them by their length, and by the coordinates of their endpoint. The corresponding three variable is algebraic of degree 8. Moreover, for any point (i, j), the length for walks of this type ending at (i, j) is also algebraic, of degree 2 or 4, and involves the famous Catalan numbers. Our method is based on the solution of a functional equation, established via a simple combinatorial argument. It actually works for more general models, in which walks take their steps in a finite subset of ℤ² satisfying two simple conditions. The corresponding are always algebraic. In the second part of the paper, we derive from our enumerative results a number of probabilistic corollaries. For instance, we can compute exactly the probability that an ordinary random walk starting from (i, j) hits for the first time the half-line at position (k, 0), for any triple (i, j, k). This generalizes a question raised by R. Kenyon, which was the starting point of this paper. Taking uniformly at random all n-step walks on the slit plane, we also compute the probability that they visit a given point (k, 0), and the average number of visits to this point. In other words, we quantify the transience of the walks. Finally, we derive an explicit limit law for the coordinates of their endpoint. Received: 22 December 2001 / Revised version: 19 February 2002 / Published online: 30 September 2002 Both authors were partially supported by the INRIA, via the cooperative research action Alcophys. Mathematics Subject Classification (2000): O5A15-60C05     

On estimating the derivatives of symmetric diffusions in stationary random environment,with applications to ∇<Emphasis Type="Italic">ϕ</Emphasis> interface model

We consider diffusions on ℝ^d or random walks on ℤ^d in a random environment which is stationary in space and in time and with symmetric and uniformly elliptic coefficients. We show existence and H?lder continuity of second space derivatives and time derivatives for the annealed kernels of such diffusions and give estimates for these derivatives. In the case of random walks, these estimates are applied to the Ginzburg-Landau ∇ϕ interface model.     

Entropy and<Emphasis Type="Italic">σ</Emphasis>-algebra equivalence of certain random walks on random sceneries

LetX=X ₀,X ₁,…be a stationary sequence of random variables defining a sequence space Σ with shift mapσ and let (T _t, Ω) be an ergodic flow. Then the endomorphismT _X(x, ω)=(σ(x),T _{x 0}(ω)) is known as a random walk on a random scenery. In [4], Heicklen, Hoffman and Rudolph proved that within the class of random walks on random sceneries whereX is an i.i.d. sequence of Bernoulli-(1/2, 1/2) random variables, the entropy ofT _t is an isomorphism invariant. This paper extends this result to a more general class of random walks, which proves the existence of an uncountable family of smooth maps on a single manifold, no two of which are measurably isomorphic. This research was sustained in part by fellowship support from the National Physical Science Consortium and the National Security Agency.     

Characters of symmetric groups: sharp bounds and applications

We provide new estimates on character values of symmetric groups which hold for all characters and which are in some sense best possible. It follows from our general bound that if a permutation σ∈S _n has at most n ^o(1) cycles of length <m, then |χ(σ)|≤χ(1)^1/m+o(1) for all irreducible characters χ of S _n . This is a far reaching generalization of a result of Fomin and Lulov. We then use our various character bounds to solve a wide range of open problems regarding mixing times of random walks, covering by powers of conjugacy classes, as well as probabilistic and combinatorial properties of word maps. In particular we prove a conjecture of Rudvalis and of Vishne on covering numbers, and a conjecture of Lulov and Pak on mixing times of certain random walks on S _n . Our character-theoretic methods also yield best possible solutions to Waring type problems for alternating groups A _n , showing that if w is a non-trivial word, and n≫0, then every element of A _n is a product of two values of w.     

Matrix random products with singular harmonic measure

Any Zariski dense countable subgroup of SL(d, \mathbb R){SL(d, \mathbb {R})} is shown to carry a non-degenerate finitely supported symmetric random walk such that its harmonic measure on the flag space is singular. The main ingredients of the proof are: (1) a new upper estimate for the Hausdorff dimension of the projections of the harmonic measure onto Grassmannians in \mathbb R^d{\mathbb {R}^d} in terms of the associated differential entropies and differences between the Lyapunov exponents; (2) an explicit construction of random walks with uniformly bounded entropy and arbitrarily long Lyapunov vector.     

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.     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

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.     

Estimations de l'erreur d'approximation par splines d'interpolation et d'ajustement d'ordre (m,s)

Résumé On montre la convergence des splines d'ajustement d'ordre (m, s) et on établit des estimations de l'erreur d'approximation par splines d'interpolation et d'ajustement d'ordre (m, s) pour des fonctions appartenant à l'espace de SobolevH ^m+s (). Ces résultats prolongent ceux de J. Duchon.

---

Approximation error estimates for interpolating and smoothing (m, s)-splines

Summary For functions belonging to the sobolev spaceH ^m+s (), convergence of smoothing (m, s)-splines is proved and approximation error estimates for interpolating and smoothing (m, s)-splines are established. This is a contribution to the (m, s)-spline theory of J. Duchon.

     

Asymptotic Properties of Ranked Heights in Brownian Excursions

Pitman and Yor^{(20, 21)} recently studied the distributions related to the ranked excursion heights of a Brownian bridge. In this paper, we study the asymptotic properties of the ranked heights of Brownian excursions. The heights of both high and low excursions are characterized by several integral tests and laws of the iterated logarithm. Our analysis relies on the distributions of the ranked excursion heights considered up to some random times.     

On the norms of group-invariant transition operators on graphs

In this paper we consider reversible random walks on an infinite grapin, invariant under the action of a closed subgroup of automorphisms which acts with a finite number of orbits on the vertex-set. Thel ²-norm (spectral radius) of the simple random walk is equal to one if and only if the group is both amenable and unimodular, and this also holds for arbitrary random walks with bounded invariant measure. In general, the norm is bounded above by the Perron-Frobenius eigenvalue of a finite matrix, and this bound is attained if and only if the group is both amenable and unimodular.     

Rational, Log Canonical, Du Bois Singularities: On the Conjectures of Kollár and Steenbrink

Let X be a proper complex variety with Du Bois singularities. Then H(X, ⁱ) H ⁱ(X, _X) is surjective for all i. This property makes this class of singularities behave well with regard to Kodaira type vanishing theorems. Steenbrink conjectured that rational singularities are Du Bois and Kollér conjectured that log canonical singularities are Du Bois. Kollér also conjectured that under some reasonable extra conditions Du Bois singularities are log canonical. In this article Steenbrink's conjecture is proved in its full generality, Kollér's first conjecture is proved under some extra conditions and Kollér's second conjecture is proved under a set of reasonable conditions, and shown that these conditions cannot be relaxed.