We consider random walks on the group of orientation-preserving homeomorphisms of the real line ${mathbb R}$. In particular, the fundamental question of uniqueness of an invariant measure of the generated process is raised. This problem was already studied by Choquet and Deny (1960) in the context of random walks generated by translations of the line. Nowadays the answer is quite well understood in general settings of strongly contractive systems. Here we focus on broader class of systems satisfying the conditions: recurrence, contraction and unbounded action. We prove that under these conditions the random process possesses a unique invariant Radon measure on ${mathbb R}$. Our work can be viewed as a subsequent paper of Babillot et al. (1997) and Deroin et al. (2013).
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time $cn/2$, the curvature is asymptotically zero for $cle 1$ and is strictly positive for $c>1$.
Let $G$ be a subgroup of $text{Homeo}_+(mathbb{R})$ without crossed elements. We show the equivalence among three items: (1) existence of $G$-invariant Radon measures on $mathbb R$; (2) existence of minimal closed subsets of $mathbb R$; (3) nonexistence of infinite towers covering the whole line. For a nilpotent subgroup $G$ of $text{Homeo}_+(mathbb{R})$, we show that $G$ always has an invariant Radon measure and a minimal closed set if every element of $G$ is $C^{1+alpha} (alpha>0$); a counterexample of $C^1$ commutative subgroup of $text{Homeo}_+(mathbb{R})$ is constructed.
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $( u {bf d})^{-1}log n pm (log n)^{1/2+o(1)}$, where $ u$ and ${bf d}$ are the speed of random walk and dimension of harmonic measure on a ${rm Poisson}(lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
We study the evolution of a random walker on a conservative dynamic random environment composed of independent particles performing simple symmetric random walks, generalizing results of [16] to higher dimensions and more general transition kernels without the assumption of uniform ellipticity or nearest-neighbour jumps. Specifically, we obtain a strong law of large numbers, a functional central limit theorem and large deviation estimates for the position of the random walker under the annealed law in a high density regime. The main obstacle is the intrinsic lack of monotonicity in higher-dimensional, non-nearest neighbour settings. Here we develop more general renormalization and renewal schemes that allow us to overcome this issue. As a second application of our methods, we provide an alternative proof of the ballistic behaviour of the front of (the discrete-time version of) the infection model introduced in [23].
We consider a random walker in a dynamic random environment given by a system of independent simple symmetric random walks. We obtain ballisticity results under two types of perturbations: low particle density, and strong local drift on particles. Surprisingly, the random walker may behave very differently depending on whether the underlying environment particles perform lazy or non-lazy random walks, which is related to a notion of permeability of the system. We also provide a strong law of large numbers, a functional central limit theorem and large deviation bounds under an ellipticity condition.