Amenable ergodic group actions and an application to Poisson boundaries of random walks

We introduce and study the class of amenable ergodic group actions which occupy a position in ergodic theory parallel to that of amenable groups in group theory. We apply this notion to questions about skew products, the range (i.e., Poincaré flow) of a cocycle, and to Poisson boundaries.     

Intersections of random walks with random sets

Two general theorems about the intersections of a random walk with a random set are proved. The result is applied to the cases when the random set is a (deterministic) half-line and a two-sided random walk. Research supported by NSF Grant DMS-8702879 and an Alfred P. Sloan Research Fellowship.     

Introduction to random walks on homogeneous spaces

Let a ₀ and a ₁ be two matrices in SL(2, ${\mathbb{Z}}$ ) which span a non-solvable group. Let x ₀ be an irrational point on the torus ${\mathbb{T}^2}$ . We toss a ₀ or a ₁, apply it to x ₀, get another irrational point x ₁, do it again to x ₁, get a point x ₂, and again. This random trajectory is equidistributed on the torus. This phenomenon is quite general on any finite volume homogeneous space.     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

On symmetric random walks with random conductances on ℤ d

We study models of continuous time, symmetric, ℤ^d-valued random walks in random environments. One of our aims is to derive estimates on the decay of transition probabilities in a case where a uniform ellipticity assumption is absent. We consider the case of independent conductances with a polynomial tail near 0 and obtain precise asymptotics for the annealed return probability and convergence times for the random walk confined to a finite box.     

Maxima of branching random walks vs. independent random walks

In recent years several authors have obtained limit theorems for the location of the right most particle in a supercritical branching random walk. In this paper we will consider analogous problems for an exponentially growing number of independent random walks. A comparison of our results with the known results of branching random walk then identifies the limit behaviors which are due to the number of particles and those which are determined by the branching structure.     

Branching random walks with random environments in time

We consider a branching random walk on N with a random environment in time （denoted by ξ）. Let Zn be the counting measure of particles of generation n, and let Zn（t） be its Laplace transform. We show the convergence of the free energy n-llog Zn（t）, large deviation principles, and central limit theorems for the sequence of measures {Zn}, and a necessary and sufficient condition for the existence of moments of the limit of the martingale Zn（t）/E[Zn（t）ξ].     

Competitive clustering algorithms based on ultrametric properties

We propose in this paper two new competitive unsupervised clustering algorithms: the first algorithm deals with ultrametric data, it has a computational cost of O(n). The second algorithm has two strong features: it is fast and flexible on the processed data type as well as in terms of precision. The second algorithm has a computational cost, in the worst case, of O(n²), and in the average case, of O(n). These complexities are due to exploitation of ultrametric distance properties. In the first method, we use the order induced by an ultrametric in a given space to demonstrate how we can explore quickly data proximity. In the second method, we create an ultrametric space from a sample data, chosen uniformly at random, in order to obtain a global view of proximities in the data set according to the similarity criterion. Then, we use this proximity profile to cluster the global set. We present an example of our algorithms and compare their results with those of a classic clustering method.     

Diffusivity of a random walk on random walks

We consider a random walk with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267–283, 2015     

Random walks on random coset spaces with applications to Furstenberg entropy

We determine the range of Furstenberg entropy for stationary ergodic actions of nonabelian free groups by an explicit construction involving random walks on random coset spaces.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Multi-excited random walks on integers

We introduce a class of nearest-neighbor integer random walks in random and non-random media, which includes excited random walks considered in the literature. At each site the random walker has a drift to the right, the strength of which depends on the environment at that site and on how often the walker has visited that site before. We give exact criteria for recurrence and transience and consider the speed of the walk.Most of this work was done while the author was Szegö Assistant Professor at Stanford University.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

Limit theorems for random walks with dynamical random transitions

Let be an ergodic and conservative non-singular transformation of (, ,m) (thedynamic environment), let _w be a random probability on a locally compact second countable groupG, and define

Self-intersections of random walks on lattices

Let {X _n ^d }_n≥0be a uniform symmetric random walk on Z^d, and Π^(d) (a,b)={X _n ^d ∈ Z^d : a ≤ n ≤ b}. Suppose f(n) is an integer-valued function on n and increases to infinity as n↑∞, and let

Isomorphism of random walks

We show that any two aperiodic, recurrent random walks on the integers whose jump distributions have finite seventh moment, are isomorphic as infinite measure preserving transformations. The method of proof involved uses a notion of equivalence of renewal sequences, and the “relative” isomorphism of Bernoulli shifts respecting a common state lumping with the same conditional entropy. We also prove an analogous result for random walks on the two dimensional integer lattice.     

Survival of branching random walks with absorption

We consider a branching random walk on R starting from x≥0 and with a killing barrier at 0. At each step, particles give birth to b children, which move independently. Particles that enter the negative half-line are killed. In the case of almost sure extinction, we find asymptotics for the survival probability at time n, when n tends to infinity.