EuDML | Browse

Sur un ensemble fini, on s'intéresse aux minorations linéaires du trou spectral d'un noyau markovien réversible, en terme de la constante isopérimétrique associée. On montre que la constante optimale est l'inverse du cardinal de l'ensemble moins un, mais on verra aussi comment il est possible de l'améliorer dans certaines situations particulières (arbres pointés radiaux à nombre fini de générations). Une application des inégalités précédentes est de retrouver immédiatement le comportement...

Uniform mixing time for random walk on lamplighter graphs

Júlia Komjáthy, Jason Miller, Yuval Peres (2014)

Annales de l'I.H.P. Probabilités et statistiques

Suppose that $𝒢$ is a finite, connected graph and $X$ is a lazy random walk on $𝒢$ . The lamplighter chain $X^{⋄}$ associated with $X$ is the random walk on the wreath product $𝒢^{⋄} = 𝐙_{2} ≀ 𝒢$ , the graph whose vertices consist of pairs $(\underset{̲}{f}, x)$ where $f$ is a labeling of the vertices of $𝒢$ by elements of $𝐙_{2} = {0, 1}$ and $x$ is a vertex in $𝒢$ . There is an edge between $(\underset{̲}{f}, x)$ and $(\underset{̲}{g}, y)$ in $𝒢^{⋄}$ if and only if $x$ is adjacent to $y$ in $𝒢$ and $f_{z} = g_{z}$ for all $z \neq x, y$ . In each step, $X^{⋄}$ moves from a configuration $(\underset{̲}{f}, x)$ by updating $x$ to $y$ using the transition rule of $X$ and then sampling both...

Unique Bernoulli $g$ -measures

Anders Johansson, Anders Öberg, Mark Pollicott (2012)

Journal of the European Mathematical Society

We improve and subsume the conditions of Johansson and Öberg and Berbee for uniqueness of a $g$ -measure, i.e., a stationary distribution for chains with complete connections. In addition, we prove that these unique $g$ -measures have Bernoulli natural extensions. We also conclude that we have convergence in the Wasserstein metric of the iterates of the adjoint transfer operator to the $g$ -measure.

Upper bound for the non-maximal eigenvalues of irreducible nonnegative matrices

Xiao-Dong Zhang, Rong Luo (2002)

Czechoslovak Mathematical Journal

We present a lower and an upper bound for the second smallest eigenvalue of Laplacian matrices in terms of the averaged minimal cut of weighted graphs. This is used to obtain an upper bound for the real parts of the non-maximal eigenvalues of irreducible nonnegative matrices. The result can be applied to Markov chains.

Currently displaying 1 – 13 of 13

Page 1