𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fastest expected time to mixing for a Markov chain on a directed graph

✍ Scribed by Steve Kirkland

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
215 KB
Volume
433
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

For an irreducible stochastic matrix T, the Kemeny constant K(T) measures the expected time to mixing of the Markov chain corresponding to T. Given a strongly connected directed graph D, we consider the set Ξ£ D of stochastic matrices whose directed graph is subordinate to D, and compute the minimum value of K, taken over the set Ξ£ D . The matrices attaining that minimum are also characterised, thus yielding a description of the transition matrices in Ξ£ D that minimise the expected time to mixing. We prove that K(T) is bounded from above as T ranges over the irreducible members of D if and only if D is an intercyclic directed graph, and in the case that D is intercyclic, we find the maximum value of K on the set Ξ£ D .

Throughout, our results are established using a mix of analytic and combinatorial techniques.

πŸ“œ SIMILAR VOLUMES

A more rapidly mixing Markov chain for g
A more rapidly mixing Markov chain for graph colorings
✍ Martin Dyer; Catherine Greenhill πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 351 KB πŸ‘ 2 views

We define a new Markov chain on proper k-colorings of graphs, and relate its convergence properties to the maximum degree ⌬ of the graph. The chain is shown to have bounds on convergence time appreciably better than those for the well-known JerrumrSalas᎐Sokal chain in most circumstances. For the cas

On Markov Chains for Randomly H-Coloring
On Markov Chains for Randomly H-Coloring a Graph
✍ Colin Cooper; Martin Dyer; Alan Frieze πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 144 KB

Let H = W F be a graph without multiple edges, but with the possibility of having loops. Let G = V E be a simple graph. A homomorphism c is a map c V β†’ W with the property that v w ∈ E implies that c v c w ∈ F. We will often refer to c v as the color of v and c as an H-coloring of G. We consider the

Variances of first passage times in a Ma
Variances of first passage times in a Markov chain with applications to mixing times
✍ Jeffrey J. Hunter πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 766 KB

In an earlier paper [J.J. Hunter, Mixing times with applications to perturbed Markov chains, Linear Algebra Appl. 417 (2006) 108-123] the author introduced the statistic Ξ· i = m j =1 m ij Ο€ j as a measure of the "mixing time" or "time to stationarity" in a finite irreducible discrete time Markov cha

Expected hitting times for a random walk
Expected hitting times for a random walk on a connected graph
✍ Gregory F Lawler πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 297 KB

A random walk on a graph is defined in which a particle moves from one vertex to any adjoining vertex, each with equal probability. The expected number of steps to get from one point to another is considered. It is shown that the maximum expectation for a graph with N vertices is O(N3). It is also s

How to Get a Perfectly Random Sample fro
How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
✍ James Gary Propp; David Bruce Wilson πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 793 KB

A general problem in computational probability theory is that of generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain. Another problem is that of generating a random spanning tree of a graph or spanning arborescence of a d