20
$\begingroup$

I'm doing a question on Markov chains and the last two parts say this:

  • Does this Markov chain possess a limiting distribution. If your answer is "yes", find the limiting distribution. If your answer is "no", explain why.
  • Does this Markov chain possess a stationary distribution. If your answer is "yes", find the stationary distribution. If your answer is "no", explain why.

What is the difference? Earlier, I thought the limiting distribution was when you work it out using $P = CA^n C^{-1}$ but this is the $n$'th step transition matrix. They calculated the limiting distribution using $\Pi = \Pi P$, which I thought was the stationary distribution.

Which is which then?

$\endgroup$
  • 4
    $\begingroup$ Your textbook may be making a distinction that is not universal: for instance, Karl Sigman's notes on limiting distributions defines "limiting" and "stationary" distributions to be synonymous (definition 2.3 at the bottom of p. 5). Therefore you must consult the definitions in your textbook in order to determine the difference. $\endgroup$ – whuber Jan 22 '13 at 18:41
  • $\begingroup$ @whuber It is saying something like working out $\lim_{n \rightarrow \infty} P_{ii}^{(n)}$ and this doesn't exist. It then goes on to say "even though the limiting distribution doesn't exist, the stationary does. Let $\Pi = (\pi_0, \pi_1, ... ,\pi_n)$ be the stationary distribution...." But I guarantee you to calculate the limiting distribution in the question before, they solved it like this. Does that make sense to you? $\endgroup$ – Kaish Jan 22 '13 at 19:25
  • $\begingroup$ @whuber Actually, I'm quite confused now because in the previous limiting distribution question, they don't satisy the $\pi_0 + \pi_1 + \pi_2 = 1$ equality, so maybe that is different? $\endgroup$ – Kaish Jan 22 '13 at 19:32
  • 2
    $\begingroup$ A stationary distribution is one that is stable over time. As far as I'm aware, the limiting distribution of a Markov chain is stationary and if a Markov chain has a stationary distribution it is also a limiting distribution. $\endgroup$ – shadowtalker Jul 1 '14 at 4:49
  • $\begingroup$ Answer here by Andreas might help quora.com/… $\endgroup$ – Siddharth Shakya Jun 11 '18 at 22:27
17
$\begingroup$

From An Introduction to Stochastic Modeling by Pinsky and Karlin (2011):

A limiting distribution, when it exists, is always a stationary distribution, but the converse is not true. There may exist a stationary distribution but no limiting distribution. For example, there is no limiting distribution for the periodic Markov chain whose transition probability matrix is $$ \mathbf{P}=\left\|\begin{matrix}0 & 1\\1 & 0\end{matrix}\right\| $$ but $\pi=\left(\frac{1}{2},\frac{1}{2}\right)$ is a stationary distribution, since $$ \left(\frac{1}{2},\frac{1}{2}\right)\left\|\begin{matrix}0 & 1\\1 & 0\end{matrix}\right\|=\left(\frac{1}{2},\frac{1}{2}\right) $$ (p. 205).

In a prior section, they had already defined a "limiting probability distribution" $\pi$ by

$$\lim_{n\rightarrow\infty}P_{ij}^{(n)}=\pi_j~\mathrm{for}~j=0,1,\dots,N$$

and equivalently

$$\lim_{n\rightarrow\infty}\operatorname{Pr}\{X_n=j|X_0=i\}=\pi_j>0~\mathrm{for}~j=0,1,\dots,N$$ (p. 165).

The example above oscillates deterministically, and so fails to have a limit in the same way that the sequence $\{1,0,1,0,1,\dots\}$ fails to have a limit.


They state that a regular Markov chain (in which all the n-step transition probabilities are positive) always has a limiting distribution, and prove that it must be the unique nonnegative solution to

$$\pi_j=\sum_{k=0}^N\pi_kP_{kj},~~j=0,1,\dots,N,\\ \sum_{k=0}^N\pi_k=1$$ (p. 168)

Then on the same page as the example, they write

Any set $(\pi_i)_{i=0}^{\infty}$ satisfying (4.27) is called a stationary probability distribution of the Markov chain. The term "stationary" derives from the property that a Markov chain started according to a stationary distribution will follow this distribution at all points of time. Formally, if $\operatorname{Pr}\{X_0=i\}=\pi_i$, then $\operatorname{Pr}\{X_n=i\}=\pi_i$ for all $n=1,2,\dots$.

where (4.27) is the set of equations

$$\pi_i \geq 0, \sum_{i=0}^{\infty} \pi_i=1,~\mathrm{and}~\pi_j = \sum_{i=0}^{\infty} \pi_iP_{ij}.$$

which is precisely the same stationarity condition as above, except now with an infinite number of states.

With this definition of stationarity, the statement on page 168 can be retroactively restated as:

  1. The limiting distribution of a regular Markov chain is a stationary distribution.
  2. If the limiting distribution of a Markov chain is a stationary distribution, then the stationary distribution is unique.
$\endgroup$
  • $\begingroup$ Can you clarify what you mean by 'transition probabilities don't change over time' for stationarity? Both limiting and stationary distribution are about the probabilities over states. $\endgroup$ – Juho Kokkala Jul 1 '14 at 7:45
  • 1
    $\begingroup$ Yup, I see you wrote your own answer but I reorganized mine to be more correct. $\endgroup$ – shadowtalker Jul 1 '14 at 9:04
  • $\begingroup$ I still don't get it. I mean what do you mean when you say "except now with an infinite number of states.... " ? Can you please clarify it more explicitely. $\endgroup$ – roni Jul 14 '16 at 16:09
  • $\begingroup$ @roni the two expressions are identical if you let $N=\infty$ $\endgroup$ – shadowtalker Jul 14 '16 at 16:30
  • $\begingroup$ In the first highlighted block, $\pi=(1/2,1/2)$ is the stationary distribution for the example, however, it has no limiting distribution since $P^{n}$ will oscillate, and it therefore has no steady state. Does this mean that it won't guarantee the existence of steady state if only the stationary distribution is calculated? $\endgroup$ – Guoyang Qin Feb 12 at 3:24
12
$\begingroup$

A stationary distribution is such a distribution $\pi$ that if the distribution over states at step $k$ is $\pi$, then also the distribution over states at step $k+1$ is $\pi$. That is, \begin{equation} \pi = \pi P. \end{equation} A limiting distribution is such a distribution $\pi$ that no matter what the initial distribution is, the distribution over states converges to $\pi$ as the number of steps goes to infinity: \begin{equation} \lim_{k\rightarrow \infty} \pi^{(0)} P^k = \pi, \end{equation} independent of $\pi^{(0)}$. For example, let us consider a Markov chain whose two states are the sides of a coin, $\{heads, tails\}$. Each step consists of turning the coin upside down (with probability 1). Note that when we compute the state distributions, they are not conditional on previous steps, i.e., the guy who computes the probabilities does not see the coin. So, the transition matrix is \begin{equation} P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. \end{equation} If we first initialize the coin by flipping it randomly ($\pi^{(0)} = \begin{pmatrix}0.5 & 0.5\end{pmatrix}$), then also all subsequent time steps follow this distribution. (If you flip a fair coin, and then turn it upside down, the probability of heads is still $0.5$). Thus, $\begin{pmatrix} 0.5 & 0.5 \end{pmatrix}$ is a stationary distribution for this Markov chain.

However, this chain does not have a limiting distribution: suppose we initialize the coin so that it is heads with probability $2/3$. Then, as all subsequent states are determined by the initial state, after an even number of steps, the state is heads with probability $2/3$ and after an odd number of steps the state is heads with probability $1/3$. This holds no matter how many steps are taken, thus the distribution over states has no limit.

Now, let us modify the process so that at each step, one does not necessarily turn the coin. Instead, one throws a die, and if the result is $6$, the coin is left as is. This Markov chain has transition matrix \begin{equation} P = \begin{pmatrix} 1/6 & 5/6 \\ 5/6 & 1/6 \end{pmatrix}. \end{equation} Without going over the math, I will point out that this process will 'forget' the initial state due to randomly omitting the turn. After a huge amount of steps, the probability of heads will be close to $0.5$, even if we know how the coin was initialized. Thus, this chain has the limiting distribution $\begin{pmatrix} 0.5 & 0.5 \end{pmatrix}$.

$\endgroup$
  • $\begingroup$ Good point about forgetting the initial state, I completely glossed over this in my answer. $\endgroup$ – shadowtalker Jul 1 '14 at 9:07
  • $\begingroup$ This explanation helps me understand a lot. Can I say the existence of a steady state is equivalent to the existence of a limiting distribution? Since it is not easy to calculate the limiting distribution, we often calculate the stationary distribution by solving balance equations instead. However, I thought this alternative method doesn't guarantee that the stationary distribution is independent from initial states, therefore, it explains why for $P = \begin{pmatrix}0&1\\1&0\end{pmatrix}$, it has the stationary distribution but no steady state that is independent from the initial states. $\endgroup$ – Guoyang Qin Feb 12 at 3:59
  • $\begingroup$ @GuoyangQin If you have a new question, you may wish to post it as a question (linking to this one if it helps provide question). Although I would have thought "steady state" in this context would mean "stationary distribution" so it would be best to clearly define the term in the question $\endgroup$ – Juho Kokkala Feb 12 at 18:57
9
$\begingroup$

Putting notation aside, the word "stationary" means "once you get there, you will stay there"; while the word "limiting" implies "you will eventually get there if you go far enough". Just thought this might be helpful.

$\endgroup$
  • $\begingroup$ It isn't clear how this applies to the question. Could you explain? $\endgroup$ – whuber Jul 28 '15 at 10:17
  • 2
    $\begingroup$ Hi @whuber, I mean to say that a limiting distribution is necessarily a stationary distribution while a stationary distribution is not necessarily a limiting distribution. Hence there is a difference. This is essentially the same as other answers but I think it's easier to remember. $\endgroup$ – BlueSky Jul 17 '16 at 2:24
  • $\begingroup$ Thank you for the clarification: it shows us what you are attempting to accomplish. However, I cannot find any reasonable way to interpret your description of "stationary" in a way that is consistent with the mathematical definition. $\endgroup$ – whuber Jul 17 '16 at 13:08
  • $\begingroup$ @whuber BlueSky's phrasing seems like an extremely straightforward plain English notion of "fixed point" to me -- I'm not sure what your object could mean. $\endgroup$ – Richard Rast Aug 20 '17 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.