MURAL - Maynooth University Research Archive Library



    Fastest Expected Time to Mixing for a Markov Chain on a Directed Graph


    Kirkland, Steve (2010) Fastest Expected Time to Mixing for a Markov Chain on a Directed Graph. Linear Algebra and its Applications, 433. pp. 1988-1996. ISSN 0024-3795

    [img] Download (211kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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.

    Item Type: Article
    Additional Information: This material is based upon works supported in part by the Science Foundation Ireland under Grant No. SFI/07/SK/I1216b.
    Keywords: Stochastic matrix; Directed graph; Kemeny constant;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 2186
    Depositing User: Professor Steve Kirkland
    Date Deposited: 13 Oct 2010 15:33
    Journal or Publication Title: Linear Algebra and its Applications
    Publisher: Elsevier
    Refereed: No
    URI:
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads