Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A Proof of the Markov Chain Tree Theorem.

    Thumbnail
    View/Open
    TR_88-97.pdf (281.3Kb)
    No. of downloads: 919

    Date
    1988
    Author
    Anantharam, Venkat
    Tsoucas, P.
    Metadata
    Show full item record
    Abstract
    Let X be a finite set, P a stochastic matrix on X, and P{BAR} = lim{AS n GOES TO x} (1/n){SIGMA k=0 to n-1, P^k}. Let G = (X, E) be the weighted directed graph on X associated to P, with weights P_ij. An arborescence is a subset a {IS AN ELEMENT OF} E which has at most one edge out of every node, contains no cycles, and has maximum possible cardinality. The weight of an arborescence is the product of its edge weights. Let A denote the set of all arborescences. Let A_ij denote the set of all arborescences which have j as a root and in which there is a directed path from i to j. Let ||A||, resp. ||A_ij||, be the sum of the weights of the arborescences in A, resp. A_ij. The Markov chain tree theorem states that p_ij = ||A_i,j||/||A||. We give a proof of this theorem which is probabilitistic in nature.
    URI
    http://hdl.handle.net/1903/4823
    Collections
    • Institute for Systems Research Technical Reports

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility