MURAL - Maynooth University Research Archive Library



    The Kemeny Constant For Finite Homogeneous Ergodic Markov Chains


    Catral, M. and Kirkland, S.J. and Neumann, M. and Sze, N.-S. (2010) The Kemeny Constant For Finite Homogeneous Ergodic Markov Chains. Journal of Scientific Computing, 45 (1-3). pp. 151-166. ISSN 0885-7474

    [img] Download (205kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    A quantity known as the Kemeny constant, which is used to measure the expected number of links that a surfer on the World Wide Web, located on a random web page, needs to follow before reaching his/her desired location, coincides with the more well known notion of the expected time to mixing, i.e., to reaching stationarity of an ergodic Markov chain. In this paper we present a new formula for the Kemeny constant and we develop several perturbation results for the constant, including conditions under which it is a convex function. Finally, for chains whose transition matrix has a certain directed graph structure we show that the Kemeny constant is dependent only on the common length of the cycles and the total number of vertices and not on the specific transition probabilities of the chain.

    Item Type: Article
    Additional Information: The original publication is available at www.springerlink.com
    Keywords: Nonnegative matrices; group inverses; directed graphs; Markov chains; stationary distribution vectors; stochastic matrices; mean first passage times;
    Academic Unit: Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 2185
    Depositing User: Professor Steve Kirkland
    Date Deposited: 13 Oct 2010 15:31
    Journal or Publication Title: Journal of Scientific Computing
    Publisher: Springer Verlag
    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