Laurent Miclo

A random walk on the Rado graph

The Rado graph, also known as the random graph $G(\infty, p)$ , is a classical limit object for finite graphs. We study natural ball walks as a way of understanding the geometry of this graph. For the walk started at $i$ , we show that order $\log_2^*i$ steps are sufficient, and for infinitely many $i$ , necessary for convergence to stationarity. The proof involves an application of Hardy's inequality for trees.

Construction of set-valued dual processes on manifolds

The purpose of this paper is to construct a Brownian motion $X := (X_t)_{t\geq 0}$ taking values in a Riemannian manifold $M$ , together with a compact valued process $D:= (D_t)_{t\geq 0}$ such that, at least for small enough ${\mathscr F}^D$ -stopping time $τ> 0$ and conditioned by ${\mathscr F}_τ^D$ , the law of $X_τ$ is the normalized Lebesgue measure on $D_τ$ . This intertwining result is a generalization of Pitman theorem. We first construct regular intertwined processes related to Stokes' theorem. Then using several limiting procedures we construct synchronous intertwined, free intertwined, mirror intertwined processes. The local times of the Brownian motion on the (morphological) skeleton or the boundary of $D$ plays an important role. Several examples with moving intervals, discs, annulus, symmetric convex sets are investigated. KEYWORDS: Brownian motions on Riemannian manifolds, intertwining relations, set-valued dual processes, couplings of primal and dual processes, stochastic mean curvature evolutions, boundary and skeleton local times, generalized Pitman theorem.

Discrete self-similar and ergodic Markov chains

The first aim of this paper is to introduce a class of Markov chains on $\mathbb{Z}_+$ which are discrete self-similar in the sense that their semigroups satisfy an invariance property expressed in terms of a discrete random dilation operator. After showing that this latter property requires the chains to be upward skip-free, we first establish a gateway relation, a concept introduced in [26], between the semigroup of such chains and the one of spectrally negative self-similar Markov processes on $\mathbb{R}_+$ . As a by-product, we prove that each of these Markov chains, after an appropriate scaling, converge in the Skorohod metric, to the associated self-similar Markov process. By a linear perturbation of the generator of these Markov chains, we obtain a class of ergodic Markov chains, which are non-reversible. By means of intertwining and interweaving relations, where the latter was recently introduced in [27], we derive several deep analytical properties of such ergodic chains including the description of the spectrum, the spectral expansion of their semigroups, the study of their convergence to equilibrium in the $Φ$ -entropy sense as well as their hypercontractivity property.

On the separation cut-off phenomenon for Brownian motions on high dimensional spheres

This note proves that the separation convergence towards the uniform distribution abruptly occurs at times around ln(n)/n for the (time-accelerated by 2) Brownian motion on the sphere with a high dimension n. The arguments are based on a new and elementary perturbative approach for estimating hitting times in a small noise context. The quantitative estimates thus obtained are applied to the strong stationary times constructed in a privious article by the authors to deduce the wanted cut-off phenomenon.

Swarm gradient dynamics for global optimization: the density case

Using jointly geometric and stochastic reformulations of nonconvex problems and exploiting a Monge-Kantorovich gradient system formulation with vanishing forces, we formally extend the simulated annealing method to a wide class of global optimization methods. Due to an inbuilt combination of a gradient-like strategy and particles interactions, we call them swarm gradient dynamics. As in the original paper of Holley-Kusuoka-Stroock, the key to the existence of a schedule ensuring convergence to a global minimizer is a functional inequality. One of our central theoretical contributions is the proof of such an inequality for one-dimensional compact manifolds. We conjecture the inequality to be true in a much wider setting. We also describe a general method allowing for global optimization and evidencing the crucial role of functional inequalities {à} la Łojasiewicz.

preprint2020arXiv

Optimal epidemic suppression under an ICU constraint

How much and when should we limit economic and social activity to ensure that the health-care system is not overwhelmed during an epidemic? We study a setting where ICU resources are constrained while suppression is costly (e.g., limiting economic interaction). Providing a fully analytical solution we show that the common wisdom of "flattening the curve", where suppression measures are continuously taken to hold down the spread throughout the epidemic, is suboptimal. Instead, the optimal suppression is discontinuous. The epidemic should be left unregulated in a first phase and when the ICU constraint is approaching society should quickly lock down (a discontinuity). After the lockdown regulation should gradually be lifted, holding the rate of infected constant thus respecting the ICU resources while not unnecessarily limiting economic activity. In a final phase, regulation is lifted. We call this strategy "filling the box".

preprint2019arXiv

On interweaving relations

Interweaving relations are introduced and studied here in a general Markovian setting as a strengthening of usual intertwining relations between semigroups, obtained by adding a randomized delay feature. They provide a new classification scheme of the set of Markovian semigroups which enables to transfer from a reference semigroup and up to an independent warm-up time, some ergodic, analytical and mixing properties including the $φ$ -entropy convergence to equilibrium, the hyperboundedness and when the warm-up time is deterministic the cut-off phenomena. We also present several useful transformations that preserve interweaving relations. We provide a variety of examples of interweaving relations ranging from classical, discrete, and non-local Laguerre and Jacobi semigroups to degenerate hypoelliptic Ornstein-Uhlenbeck semigroups and some non-colliding particle systems

preprint2018arXiv

On a gateway between continuous and discrete Bessel and Laguerre processes

By providing instances of approximation of linear diffusions by birth-death processes, Feller [13], has offered an original path from the discrete world to the continuous one. In this paper, by identifying an intertwining relationship between squared Bessel processes and some linear birth-death processes, we show that this connection is in fact more intimate and goes in the two directions. As by-products, we identify some properties enjoyed by the birth-death family that are inherited from squared Bessel processes. For instance, these include a discrete self-similarity property and a discrete analogue of the beta-gamma algebra. We proceed by explaining that the same gateway identity also holds for the corresponding ergodic Laguerre semi-groups. It follows again that the continuous and discrete versions are more closely related than thought before, and this enables to pass information from one semi-group to the other one.

preprint2016arXiv

A stochastic algorithm finding $p$ -means on the circle

A stochastic algorithm is proposed, finding some elements from the set of intrinsic $p$ -mean(s) associated to a probability measure $ν$ on a compact Riemannian manifold and to $p\in[1,\infty)$ . It is fed sequentially with independent random variables $(Y_n)_{n\in \mathbb{N}}$ distributed according to $ν$ , which is often the only available knowledge of $ν$ . Furthermore, the algorithm is easy to implement, because it evolves like a Brownian motion between the random times when it jumps in direction of one of the $Y_n$ , $n\in\mathbb{N}$ . Its principle is based on simulated annealing and homogenization, so that temperature and approximations schemes must be tuned up (plus a regularizing scheme if $ν$ does not admit a Hölderian density). The analysis of the convergence is restricted to the case where the state space is a circle. In its principle, the proof relies on the investigation of the evolution of a time-inhomogeneous $\mathbb{L}^2$ functional and on the corresponding spectral gap estimates due to Holley, Kusuoka and Stroock. But it requires new estimates on the discrepancies between the unknown instantaneous invariant measures and some convenient Gibbs measures.

preprint2016arXiv

On the fastest finite Markov processes

Consider a finite irreducible Markov chain with invariant probability $π$ . Define its inverse communication speed as the expectation to go from x to y, when x, y are sampled independently according to $π$ . In the discrete time setting and when $π$ is the uniform distribution $\upsilon$ , Litvak and Ejov have shown that the permutation matrices associated to Hamiltonian cycles are the fastest Markov chains. Here we prove (A) that the above optimality is with respect to all processes compatible with a fixed graph of permitted transitions (assuming that it does contain a Hamiltonian cycle), not only the Markov chains, and, (B) that this result admits a natural extension in both discrete and continuous time when $π$ is close to $\upsilon$ : the fastest Markov chains/processes are those moving successively on the points of a Hamiltonian cycle, with transition probabilities/jump rates dictated by $π$ . Nevertheless, the claim is no longer true when $π$ is significantly different from $\upsilon$ .

An Exercise (?) in Fourier Analysis on the Heisenberg Group

Let H(n) be the group of 3x3 uni-uppertriangular matrices with entries in Z/nZ, the integers mod n. We show that the simple random walk converges to the uniform distribution in order n^2 steps. The argument uses Fourier analysis and is surprisingly challenging. It introduces novel techniques for bounding the spectrum which are useful for a variety of walks on a variety of groups.

Estimates on the amplitude of the first Dirichlet eigenvector in discrete frameworks

Consider a finite absorbing Markov generator, irreducible on the non-absorbing states. Perron-Frobenius theory ensures the existence of a corresponding positive eigenvector $φ$ . The goal of the paper is to give bounds on the amplitude $\max φ/\minφ$ . Two approaches are proposed: one using a path method and the other one, restricted to the reversible situation, based on spectral estimates. The latter approach is extended to denumerable birth and death processes absorbing at 0 for which infinity is an entrance boundary. The interest of estimating the ratio is the reduction of the quantitative study of convergence to quasi-stationarity to the convergence to equilibrium of related ergodic processes, as seen in [7].

On the Markov commutator

The Markov commutator associated to a finite Markov kernel P is the convex semigroup consisting of all Markov kernels commuting with P. Its interest comes from its relation with the hypergroup property and with the notion of Markovian duality by intertwining. In particular, it is shown that the discrete analogue of the Achour-Trim{è}che's theorem, asserting the preservation of non-negativity by the wave equations associated to certain Metropolis birth and death transition kernels, cannot be extended to all convex potentials. But it remains true for symmetric and monotone convex potentials. Keywords: finite Markov kernels, Markov commutator, symmetry group of a Markov kernel, hypergroup property, duality by intertwining, Achour-Trim{è}che theorem, birth and death chains, Metropolis algorithms, one-dimensional discrete wave equations.

Useful bounds on the extreme eigenvalues and vectors of matrices for Harper's operators

In analyzing a simple random walk on the Heisenberg group we encounter the problem of bounding the extreme eigenvalues of an $n\times n$ matrix of the form $M=C+D$ where $C$ is a circulant and $D$ a diagonal matrix. The discrete Schrödinger operators are an interesting special case. The Weyl and Horn bounds are not useful here. This paper develops three different approaches to getting good bounds. The first uses the geometry of the eigenspaces of $C$ and $D$ , applying a discrete version of the uncertainty principle. The second shows that, in a useful limit, the matrix $M$ tends to the harmonic oscillator on $L^2(\mathbb{R})$ and the known eigenstructure can be transferred back. The third approach is purely probabilistic, extending $M$ to an absorbing Markov chain and using hitting time arguments to bound the Dirichlet eigenvalues. The approaches allow generalization to other walks on other groups.

preprint2014arXiv

On quantitative convergence to quasi-stationarity

The quantitative long time behavior of absorbing, finite, irreducible Markov processes is considered. Via Doob transforms, it is shown that only the knowledge of the ratio of the values of the underlying first Dirichlet eigenvector is necessary to come back to the well-investigated situation of the convergence to equilibrium of ergodic finite Markov processes. This leads to explicit estimates on the convergence to quasi-stationarity, in particular via functional inequalities. When the process is reversible, the optimal exponential rate consisting of the spectral gap between the two first Dirichlet eigenvalues is recovered. Several simple examples are provided to illustrate the bounds obtained.

A stochastic algorithm finding generalized means on compact manifolds

A stochastic algorithm is proposed, finding the set of generalized means associated to a probability measure on a compact Riemannian manifold M and a continuous cost function on the product of M by itself. Generalized means include p-means for p>0, computed with any continuous distance function, not necessarily the Riemannian distance. They also include means for lengths computed from Finsler metrics, or for divergences. The algorithm is fed sequentially with independent random variables Y_n distributed according to the probability measure on the manifold and this is the only knowledge of this measure required. It evolves like a Brownian motion between the times it jumps in direction of the Y_n. Its principle is based on simulated annealing and homogenization, so that temperature and approximations schemes must be tuned up. The proof relies on the investigation of the evolution of a time-inhomogeneous L^2 functional and on the corresponding spectral gap estimates due to Holley, Kusuoka and Stroock.

A stochastic model for speculative bubbles

This paper aims to provide a simple modelling of speculative bubbles and derive some quantitative properties of its dynamical evolution. Starting from a description of individual speculative behaviours, we build and study a second order Markov process, which after simple transformations can be viewed as a turning two-dimensional Gaussian process. Then, our main problem is to ob- tain some bounds for the persistence rate relative to the return time to a given price. In our main results, we prove with both spectral and probabilistic methods that this rate is almost proportional to the turning frequency ω of the model and provide some explicit bounds. In the continuity of this result, we build some estimators of ω and of the pseudo-period of the prices. At last, we end the paper by a proof of the quasi-stationary distribution of the process, as well as the existence of its persistence rate.

Ornstein-Uhlenbeck pinball: I. Poincaré inequalities in a punctured domain

In this paper we study the Poincaré constant for the Gaussian measure restricted to $D=\R^d - B(y,r)$ where $B(y,r)$ denotes the Euclidean ball with center $y$ and radius $r$ , and $d\geq 2$ . We also study the case of the $l^\infty$ ball (the hypercube). This is the first step in the study of the asymptotic behavior of a $d$ -dimensional Ornstein-Uhlenbeck process in the presence of obstacles with elastic normal reflections (the Ornstein-Uhlenbeck pinball) we shall study in a companion paper.