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.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

On logarithmic Sobolev inequalities for higher order fractional derivatives

On ${\mathbb{R}}^n$, we prove the existence of sharp logarithmic Sobolev inequalities with higher fractional derivatives. Let s be a positive real number. Any function f ∈ $H^s({\mathbb{R}}^n)$ satisfies

$\underset{{\mathbb{R}}^n}{\int }|f(x){|}^2\ln (\frac{{|f(x)|}^2}{6f{6}_2^2})\mathrm{d}x+(n+\frac{n}{s}\ln \alpha +\ln \frac{s\mathrm{\Gamma }(\frac{n}{2})}{\mathrm{\Gamma }(\frac{n}{2s})})6f{6}_2^2?\frac{{\alpha }^2}{{\pi }^s}6{(?\mathrm{\Delta })}^{s/2}f{6}_2^2$

with $\alpha >0$ be any number and where the operators ${(?\mathrm{\Delta })}^{s/2}$ in Fourier spaces are defined by $\stackrel{?}{{(?\mathrm{\Delta })}^{s/2}f}(k)\text{:}={(2\pi |k|)}^s\stackrel{?}{f}(k)$. To cite this article: A. Cotsiolis, N.K. Tavoularis, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields

We show that the entropy functional exhibits a quasi-factorization property with respect to a pair of weakly dependent σ-algebras. As an application we give a simple proof that the Dobrushin and Shlosmans complete analyticity condition, for a Gibbs specification with finite range summable interaction, implies uniform logarithmic Sobolev inequalities. This result has been previously proven using several different techniques. The advantage of our approach is that it relies almost entirely on a general property of the entropy, while very little is assumed on the Dirichlet form. No topology is introduced on the single spin space, thus discrete and continuous spins can be treated in the same way. Received: 7 July 2000 / Revised version: 10 October 2000 / Published online: 5 June 2001     

Modified logarithmic Sobolev inequalities and transportation inequalities

We present a class of modified logarithmic Sobolev inequality, interpolating between Poincaré and logarithmic Sobolev inequalities, suitable for measures of the type exp (−|x|^α) or exp (−|x|^α log ^β(2+|x|)) (α ∈]1,2[ and β ∈ ℝ) which lead to new concentration inequalities. These modified inequalities share common properties with usual logarithmic Sobolev inequalities, as tensorisation or perturbation, and imply as well Poincaré inequality. We also study the link between these new modified logarithmic Sobolev inequalities and transportation inequalities. Send offprint requests to: Ivan Gentil     

Triangular array limits for continuous time random walks

A continuous time random walk (CTRW) is a random walk subordinated to a renewal process, used in physics to model anomalous diffusion. Transition densities of CTRW scaling limits solve fractional diffusion equations. This paper develops more general limit theorems, based on triangular arrays, for sequences of CTRW processes. The array elements consist of random vectors that incorporate both the random walk jump variable and the waiting time preceding that jump. The CTRW limit process consists of a vector-valued Lévy process whose time parameter is replaced by the hitting time process of a real-valued nondecreasing Lévy process (subordinator). We provide a formula for the distribution of the CTRW limit process and show that their densities solve abstract space–time diffusion equations. Applications to finance are discussed, and a density formula for the hitting time of any strictly increasing subordinator is developed.     

Isoperimetric inequalities and random walks on quotients of graphs and buildings

Let be a Euclidean or hyperbolic building and let GAut be a locally compact unimodular group, which acts strongly transitively on . We use graphs , quasi-isometric to , to study asymptotic properties of quotients , where is a discrete subgroup of G. If G has Kazhdans property (T) we show that such quotients satisfy strong isoperimetric inequalities. This yields new examples of graphs with positive Cheeger constant. Such graphs cannot be bi-Lipschitz embedded into Hilbert space. Moreover, simple random walks on such quotients are shown to be recurrent if and only if is a uniform lattice in G.Mathematics Subject Classification (1991): 11E95, 22E40, 22E50, 51E24, 60G50in final form: 10 October 2003     

Isoperimetry and symmetrization for logarithmic Sobolev inequalities

Using isoperimetry and symmetrization we provide a unified framework to study the classical and logarithmic Sobolev inequalities. In particular, we obtain new Gaussian symmetrization inequalities and connect them with logarithmic Sobolev inequalities. Our methods are very general and can be easily adapted to more general contexts.     

Analytic inequalities,isoperimetric inequalities and logarithmic Sobolev inequalities

There is a simple equivalence between isoperimetric inequalities in Riemannian manifolds and certain analytic inequalities on the same manifold, more extensive than the familiar equivalence of the classical isoperimetric inequality in Euclidean space and the associated Sobolev inequality. By an isoperimetric inequality in this connection we mean any inequality involving the Riemannian volume and Riemannian surface measure of a subset α and its boundary, respectively. We exploit the equivalence to give log-Sobolev inequalities for Riemannian manifolds. Some applications to Schrödinger equations are also given.     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

A general two-scale criteria for logarithmic Sobolev inequalities

We present a general criteria to prove that a probability measure satisfies a logarithmic Sobolev inequality, knowing that some of its marginals and associated conditional laws satisfy a logarithmic Sobolev inequality. This is a generalization of a result by N. Grunewald et al. [N. Grunewald, F. Otto, C. Villani, M.G. Westdickenberg, A two-scale approach to logarithmic Sobolev inequalities and the hydrodynamic limit, Ann. Inst. H. Poincaré Probab. Statist., in press].     

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.     

General logarithmic Sobolev inequalities and Orlicz imbeddings

We obtain, for a large class of measures μ, general inequalities of the form $\text{∫R}{}^{\mathrm{n}}\text{|u|}{}^{\mathrm{p}}\text{A(}\text{log}{}^1\text{|u|) dμ ? K(6u : W}{}^{\mathrm{m,p}}\text{(R}{}^{\mathrm{n}}\text{,dμ)6}{}^{\mathrm{p}}\text{+ 6 u 6}{}^{\mathrm{p}}\text{A(}\text{log}{}^1\text{6 u 6))}$, where $\text{6u6 = 6 u: L}{}^{\mathrm{p}}\text{(R}{}^{\mathrm{n}}\text{,dμ)6}{}^{\mathrm{p}}\text{,}\text{log}{}^1\text{t =}\text{max}\text{{1,}\text{log}\text{t}}$, and the function A depends in an appropriate way on μ. Our results extend similar results obtained by Rosen for the case p = 2, A(t) = t^s. We also investigate some implications of these inequalities for the imbedding of Sobolev spaces into Orlicz spaces.     

A tight lower bound on the cover time for random walks on graphs

We prove that the expected time for a random walk to cover all n vertices of a graph is at least (1 + o(1))n In n.     

A tight upper bound on the cover time for random walks on graphs

We prove that the expected time for a random walk to visit all n vertices of a connected graph is at most 4/27n³ + o(n³).     

Clark formula and logarithmic Sobolev inequalities for Bernoulli measures

Using a Clark formula for the predictable representation of random variables in discrete time and adapting the method presented in [Electron. Commun. Probab. 2 (1997) 71–81] in the Brownian case, we obtain a proof of modified and L¹ logarithmic Sobolev inequalities for Bernoulli measures. We also prove a bound that improves these inequalities as well as the optimal constant inequality of [J. Funct. Anal. 156 (2) (1998) 347–365]. To cite this article: F. Gao, N. Privault, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Weak logarithmic Sobolev inequalities and entropic convergence

In this paper we introduce and study a weakened form of logarithmic Sobolev inequalities in connection with various others functional inequalities (weak Poincaré inequalities, general Beckner inequalities, etc.). We also discuss the quantitative behaviour of relative entropy along a symmetric diffusion semi-group. In particular, we exhibit an example where Poincaré inequality can not be used for deriving entropic convergence whence weak logarithmic Sobolev inequality ensures the result.      

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.