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

DOI10.1016/j.laa.2010.07.016zbMath1209.05111OpenAlexW2057847103MaRDI 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 graphstochastic matrixKemeny constant

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Inequalities involving eigenvalues and eigenvectors (15A42) Directed graphs (digraphs), tournaments (05C20) Stochastic matrices (15B51)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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