0
$\begingroup$

This question is about the advantages of ensuring a limiting distribution in the Metropolis algorithm.

According to Wikipedia ,

uniqueness of stationary distribution: the stationary distribution $\pi(x)$ must be unique. This is guaranteed by ergodicity of the Markov process, which requires that every state must (1) be aperiodic—the system does not return to the same state at fixed intervals; and (2) be positive recurrent—the expected number of steps for returning to the same state is finite.

In the article is stated that ergodic implies aperiodic. It seems that there is not agreenment about this, like in this SE question is shown.

According to this answer an unique stationary distribution exists if all states of an irreducible Markov chain are positive recurrent. In the same reference it is said that the limiting probabilities cannot converge.

I think that the requirement of aperiodicity is done to ensure that the chain is ergodic acording to this definition, which ensures a limiting distribution.


Question: In the application of the Metropolis algorithm one take the average value of some property of each state in the realization of the Markov chain. Why convergence to a limiting distribution would be an advantage? It seems to me that ensuring that the MC is irreducible and positive recurrent should be enough.

Any clarification of incorrect statements in this question is very welcome.

$\endgroup$
  • $\begingroup$ Just to clarify, in the second link you cite it states that the limiting probabilities cannot converge if the chain is periodic. That is just because we always have periodic bouncing of the probabilities. $\endgroup$ – Michael Oct 24 '19 at 21:15
  • $\begingroup$ Possibly useful: Suppose $\{Z(t)\}_{t=0}^{\infty}$ is a DTMC with finite or countable state space $S$ and suppose $\frac{1}{T}\sum_{t=0}^{T-1}P[Z(t)=i] \rightarrow \pi(i)$ for all $i \in S$. Suppose $X(t)$ is a reward with $E[X(t)|Z(t)=i]=m(i)$ for all $i \in S$, with $\sup_{i\in S} |m(i)|<\infty$. It can be shown $$ \lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1}E[X(t)] = \sum_{i\in S} \pi(i)m(i)$$ $\endgroup$ – Michael Oct 24 '19 at 21:43
  • $\begingroup$ (Assuming $\sum_{i\in S}\pi(i)=1$) $\endgroup$ – Michael Oct 24 '19 at 22:05
  • $\begingroup$ @Michael , thank you very much for your comments! I am not completely sure about the meaning of $X(t)$ but I think I understand you. What I do not get is: those properties require the existence of the stationary distribution $\pi$, but why add the requiremof that it is also a limiting distribution (which implies that the MC is aperiodic)? If states appears with a probability of $\pi$ wouldn't be enough for estimating expected values of properties determined by such states? $\endgroup$ – user1420303 Oct 25 '19 at 3:53
  • $\begingroup$ Nowhere in the above comments do I assume aperiodic. As an example consider a periodic 2-state chain that starts in state 1 and $P_{12} = P_{21} = 1$. Then $\lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1} P[Z(t)=1] = 1/2$ but $\lim_{T\rightarrow\infty} P[Z(t)=1]$ does not exist. If a chain with finite or countable state space is irreducible and there is a PMF $\pi(i)$ that satisfies the stationary equations then we must have $\lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1} P[Z(t)=i] = \pi(i)$ for all $i \in S$, regardless of periodic or aperiodic and regardless of initial state. $\endgroup$ – Michael Oct 25 '19 at 7:15
0
$\begingroup$

Suppose $\{Z(t)\}_{t=0}^{\infty}$ is a discrete time Markov Chain (DTMC) with a finite or countably infinite state space $S$ and with transition probability matrix $P=(P_{ij})$.

We say that $Z(t)$ is irreducible if there is a finite path of nonzero probability from every state $i \in S$ to every other state $j \in S$.

A probability mass function (PMF) on the state space $S$ is a vector $(\pi_i)_{i \in S}$ such that $\pi_i \geq 0$ for all $i \in S$ and $\sum_{i\in S} \pi_i=1$.

Theorem: Suppose $\{Z(t)\}_{t=0}^{\infty}$ is an irreducible DTMC. If we can find a PMF $(\pi_i)_{i\in S}$ that satisfies the following stationary equations: $$ \pi_j = \sum_{i \in S} \pi_i P_{ij} \quad \forall j \in S $$ then $(\pi_i)_{i\in S}$ is the unique PMF that solves the above stationary equations, $\pi_i>0$ for all $i \in S$, and regardless of the initial condition $Z(0)$ we have for all $i \in S$: \begin{align} \lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1} 1_{\{Z(t)=i\}} &= \pi_i \quad \mbox{(with prob 1)} \\ \lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1}P[Z(t)=i] &= \pi_i \end{align} If there is no PMF that satisfies the stationary equations, then for all states $i \in S$ and regardless of the initial state $Z(0)$ we have: \begin{align} \lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1} 1_{\{Z(t)=i\}} &= 0 \quad \mbox{(with prob 1)} \\ \lim_{T\rightarrow\infty} \frac{1}{T}\sum_{t=0}^{T-1}P[Z(t)=i] &= 0 \end{align}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note 1: If $S$ has a finite state space, then there always exists a PMF solution to the stationary equations. $\endgroup$ – Michael Oct 25 '19 at 17:31
  • 1
    $\begingroup$ Note 2: If the DTMC is both irreducible and aperiodic and we can find a PMF solution $(\pi_i)_{i\in S}$ to the stationary equations, then we additionally get the following (regardless of the initial state $Z(0)$): $$ \lim_{T\rightarrow\infty} P[Z(t)=i] = \pi_i \quad \forall i \in S$$ This is the only benefit of adding the "aperiodic" assumption. $\endgroup$ – Michael Oct 25 '19 at 17:37
  • $\begingroup$ Hello: What is the reason for the downvote (and "delete" vote: I have never seen such a thing before!) If there is a comment/concern it would be more appropriate to state that. Nobody learns anything with this negative vote with no comment, which seems anti-mathematical and anti-stackexchange. $\endgroup$ – Michael Nov 15 '19 at 23:23
  • $\begingroup$ is right. That is not constructive. I find the answer very useful. I did not accept it as the best answer because it does not fully address the question "Why convergence to a limiting distribution would be an advantage?". Although the equality in the comment is closely related, I do not know why it would matter in practice, in a method that is used to compute the expected value of a function the states of the particular realization of the MC. That is, it sounds good to have this property, but I cannot justify this from a practical perspective. $\endgroup$ – user1420303 Dec 14 '19 at 23:00
  • $\begingroup$ I will start a bounty. If this answer is the best that our community can say, it will receive the credit that it deserves. $\endgroup$ – user1420303 Dec 14 '19 at 23:03
0
$\begingroup$

I would answer your question as follows. For simplicity let us talk only about the finite state case.

1) If a Markov chain consists of one recurrent class and this class is periodic of period $d$, then the states in the class are partitioned into $d$ cyclically-ordered subsets, say $S_0$, $S_1$, ..., $S_{d-1}$, where each subset has transitions only into the next subset i.e. from $S_0$ to $S_1$ to $S_2$ to $S_3$ ... then back to $S_0$. Let the transition probability matrix of this chain be equal to $\mathbb{P}$.

2) The equation ${\vec x} = {\vec x} \mathbb{P}$ always has a probaiblity vector solution. Due to the conditions of 1), this vector, say $\vec p$, is unique.

3) Cosider an aperiodic ergodic single recurrent class Markov chain with transition probability matrix $\mathbb{P}^*$. Then it holds that $\lim_{n \rightarrow \infty} [\mathbb{P}^*]^n = {\vec 1} {\vec {p^*}}$. Here ${\vec {p^*}}$ is the solution of ${\vec {p^*}} = {\vec {p^*}} \mathbb{P}^*$ and $\vec 1$ is the vector of ones. Thus the limiting value of $[\mathbb{P}^*]^n$ is a finite matrix whose rows are all the same i.e. the limiting matrix is the product ${\vec 1} {\vec {p^*}}$.

4) In the case of 1) we have that $\lim_{n \rightarrow \infty} \mathbb{P}^n$ does not converge to anything. For example, $\mathbb{P}^d_{ij}=0$ for all $j$ not in the same periodic subset as $i$. In good ergodic chains, which are usually discussed, the memory of the state, where we started (state $i$), disappears with the growth of $n$. For periodic chains it is too much to hope for.

5) Even though $\lim_{n \rightarrow \infty} \mathbb{P}^n$ does not converge to anything, according to 2), $\vec p$ exists and is unique. The vector $\vec p$ can be called steady-state probability vector. But its interpretation is different from the interpretation used for ergodic Markov chains. Specifically, for periodic chains the components of $\vec p$ are the average values over one period. Strictly speaking, it holds that $$ \lim_{n \rightarrow \infty} {1 \over d} \left (\mathbb{P}^n + \mathbb{P}^{n+1} + \dots + \mathbb{P}^{n+d-1} \right ) ={\vec 1}{\vec p}. $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I understood those implications of aperiodicity thanks to both answers to this question. What I still do not get is "Why convergence to a limiting distribution would be an advantage?" (In the context of the Metropolis algorithm). I mean, has this implications in the application of the algorithm? Clearly, it may affect the periodicity of the process, but do we care in practice for common applications? (For example, when using the algorithm for sampling for estimating the expectation of some physical magnitude) $\endgroup$ – user1420303 Dec 21 '19 at 23:45
  • 1
    $\begingroup$ Question you are asking is not simple. So it is too much to hope for a simple answer. In fact there are many issues with periodic Markov chains when using MCMC methods. Here is just one, maybe simplest. Notation as in my post above. Suppose you want to construct the MC with transition probabilities $p_{ij}$ and stationary distribution $\vec p$ (where components of $\vec p$ are the average values over one period) and you know that the period $d>2$. Useful concept in constructing $p_{ij}$ is reversibility. But it impossible (!) to use it here because a MC with period $d>2$ is never reversible. $\endgroup$ – rrv Dec 22 '19 at 9:20

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.