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

DOI10.1016/j.laa.2010.07.016zbMath1209.05111MaRDI QIDQ603129

Stephen J. Kirkland

Publication date: 5 November 2010

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: http://eprints.maynoothuniversity.ie/2186/2/SK_min_kemeny_final.pdf

zbMATH Keywords

directed graph; stochastic matrix; Kemeny constant

Mathematics Subject Classification ID

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

15A42: Inequalities involving eigenvalues and eigenvectors

05C20: Directed graphs (digraphs), tournaments

15B51: Stochastic matrices

Related Items

Remarks and open problems on the minimum permanent of acyclic doubly stochastic matrices, Analysis of Markov Influence Graphs, A Structured Condition Number for Kemeny's Constant, The Role of Kemeny's Constant in Properties of Markov Chains, Random Walks, Directed Cycles, and Markov Chains, On the Kemeny time for continuous-time reversible and irreversible Markov processes with applications to stochastic resetting and to conditioning towards forever-survival, Minimising the largest mean first passage time of a Markov chain: the influence of directed graphs, Alleviating road network congestion: traffic pattern optimization using Markov chain traffic assignment, Kemeny's constant and the effective graph resistance, Lower bounds for the Estrada index using mixing time and Laplacian spectrum, Generalized inverses of Markovian kernels in terms of properties of the Markov chain, The minimum coefficient of ergodicity for a Markov chain with a given directed graph, Load balancing for Markov chains with a specified directed graph, A Google-like model of road network dynamics and its application to regulation and control, The Hitting Time of Multiple Random Walks, Kemeny's Constant And An Analogue Of Braess' Paradox For Trees

Cites Work

• The Kemeny constant for finite homogeneous ergodic Markov chains
• Non-negative matrices and Markov chains. 2nd ed
• Mixing times with applications to perturbed Markov chains
• Matrix Analysis
• Kemeny's Constant and the Random Surfer
• Fastest Mixing Markov Chain on a Graph
• A combinatorial approach to the conditioning of a single entry in the stationary distribution for a Markov chain
• The Group Inverse Associated with an Irreducible Periodic Nonnegative Matrix
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item