0
$\begingroup$

This is just a reference request for a result which is very general, useful and should be well-known, but I've failed to find a good reference to cite.

The problem is to define the "most natural" stationary distribution of a finite Markov Chain with specified initial state. What I mean here by "stationary distribution" is just a solution of $\pi P=\pi$, where $P$ is the matrix of the Markov chain.

The case that is widely studied and keeps popping wherever I look is the irreducible aperiodic case, for which we have a unique stationary distribution.

But if you take a Markov Chain without these properties, you can still easily compute the stationary distribution which gives you the average time spent in each state on the long run. More precisely, we want to compute the distribution $\pi$ such that for each state $X$, $\pi(X)=\lim_{n\to\infty} \frac{E_n(X)}{n} $, where $E_n(X)$ is the expected number of occurrences of $X$ in an $n$-step process of the Markov chain.

I call a Strongly Connected Component (SCC) "ergodic" if we cannot get out of it, and "transient" otherwise.

It suffices to compute the probability $\rho(C)$ to end up in each ergodic component $C$. Remind that we know the initial state, which is why we can compute these probabilities. Then we are back to the irreducible case to compute the stationary distribution of each component. We then compose them to get the final distribution, using $\rho(C)$ to weight the local distribution in each $C$. The periodicity (inside an ergodic SCC) is not a problem either: it means that the states can be partitioned according to the period (like even states and odd states for instance). Looking at the Markov Chain induced by one class gets us back to the irreducible aperiodic case, and from this we easily deduce the distribution for all states.

A small example: if you start from $X_0$ which goes to $X_1$ with probability $\frac{1}{4}$ and $X_2$ with probability $\frac{3}{4}$. Then $X_1$ is a sink (goes to itself with probability 1), and $X_2$ goes to $X_3$ with probability 1, which goes back to $X_2$ with probability $1$. Then the "good" stationary distribution would be $\pi(X_0)=0$, $\pi(X_1)=\frac{1}{4}$, $\pi(X_2)=\pi(X_3)=\frac{3}{8}$.

Can someone point me to a reference describing this distribution?

Improve this question
$\endgroup$
5
  • $\begingroup$ In the general case, this would depend on your initial state. Although it doesn't address the full generality of your question, the Wikipedia page about absorbing Markov chains is pretty good en.wikipedia.org/wiki/Absorbing_Markov_chain $\endgroup$
    – guest
    Commented Jan 3, 2014 at 18:19
  • $\begingroup$ Stationary distribution by definition is independent of initial state. I would think the corresponding weights of the "good" stationary dist. should be (0,5/16,11/32,11/32). $\endgroup$
    – Piyush Grover
    Commented Jan 3, 2014 at 18:33
  • $\begingroup$ @piyush Markov processes that do not have stationary distributions can still have limiting distributions in certain senses. I think the OP's question is about these distributions that might not technically be stationary distributions by definition. $\endgroup$
    – guest
    Commented Jan 3, 2014 at 18:50
  • $\begingroup$ You're right that initial state is important here, I will add it in the question. $\endgroup$
    – Denis
    Commented Jan 3, 2014 at 19:40
  • $\begingroup$ I also clarified what I mean by "stationary distribution" $\endgroup$
    – Denis
    Commented Jan 3, 2014 at 19:55

1 Answer 1

Reset to default
3
$\begingroup$

I call a Strongly Connected Component (SCC) "ergodic" if we cannot get out of it, and "transient" otherwise.

It suffices to compute the probability ρ(C) to end up in each ergodic component C

Although your case is not technically an absorbing Markov chain (because not every state will eventually reach an absorbing state) you can still use absorbing Markov chain concepts and notation to compute those probabilities.

Transform your process to an absorbing Markov chain by removing all of the connections within the ergodic components, so that every state in an ergodic component of the original process is an absorbing state in the transformed process.

Now use the formulas in that wikipedia page to compute the 'canonical form' and the 'fundamental matrix' for the transformed process, and use these to find the absorbing probabilities of the transformed process.

The probability p(C) is the sum of absorbing probabilities of the component's states in the transformed absorbing process.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I don't have any problem with how to compute these probabilities and the distribution $\pi$, I'm just looking for a reference doing that. I would be surprised it does not exist already, but if specialists confirm they have no knowledge of it it would also be interesting. $\endgroup$
    – Denis
    Commented Jan 3, 2014 at 20:24
  • $\begingroup$ I think it's in the literature as 'limiting distribution' as opposed to 'stationary distribution'. $\endgroup$
    – guest
    Commented Jan 3, 2014 at 20:25
  • $\begingroup$ Here we can only compute this distribution if the initial state is fixed, which is not a common assumption in Markov chain theory. $\endgroup$
    – Denis
    Commented Jan 3, 2014 at 20:31
  • $\begingroup$ It is linear so it directly generalizes to any distribution over initial states. In absorbing Markov chain theory it is a commonly assumed that we know something about the initial state. $\endgroup$
    – guest
    Commented Jan 3, 2014 at 20:33
  • $\begingroup$ so can you point me to a reference with this ? $\endgroup$
    – Denis
    Commented Jan 3, 2014 at 20:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .