most recent 30 from http://mathoverflow.net 2013-05-21T15:13:59Z http://mathoverflow.net/feeds/question/101477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101477/combinatorial-descriptions-of-the-stationary-distribution-of-a-markov-chain Erik Aas 2012-07-06T10:24:52Z 2012-07-06T15:53:20Z

<p>When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible. </p> <p>If the Markov chain happens to be equivalent to an "undirected Markov chain", i.e. for each directed arc (u,v) with weight w there is an arc (v,u) with same weight w, then it is easy to characterize the stationary distribution directly in terms of the graph; the stationary distribution at a vertex v is proportional to the out-degree (which in this case is half the total degree) of v.</p> <p>However I know of no such direct description of the stationary distribution in terms of the graph of a Markov chain that does not come from an undirected graph (except possibly for time-reversible chains, but this is a very special special case). My question is: are there any such descriptions?</p> <p>This is of course a bit vague(since the stationary distribution clearly depends only on the graph) but I hope it is not too vague.</p> <p>I would not expect an as easy description as in the undirected case (where it suffices to look in a neighbourhood of radius 1 to find the probability of any vertex), but it seems reasonable that there could be a description involving, say, all trees rooted at the vertex.</p> <p>This seems not to be treated in standard texts on Markov chains (correct me if wrong), where usually most effort is spent on proving existence, estimating speed of convergence, and the underlying graph is considered as 'auxilliary'.</p>

http://mathoverflow.net/questions/101477/combinatorial-descriptions-of-the-stationary-distribution-of-a-markov-chain/101486#101486 Philippe Nadeau 2012-07-06T12:35:22Z 2012-07-06T12:35:22Z

<p>"Markov Chain Tree Theorem" is what you should look up: it says essentially that the stationary probability of a given state/vertex is given by the sum of the weights of all spanning trees rooted at that vertex.</p>