1
$\begingroup$

Suppose that a finite-state Markov chain with transition matrix $M$ has multiple stationary distributions (or invariant measures). Let $\Pi$ denote the set of the stationary distributions.

Fix any $\pi \in \Pi$. Does there exist a Markov chain with transition matrix $M'$ with the following properties?

  1. $M'$ is "close" to $M$.
  2. $M'$ has a unique stationary distribution $\pi'$.
  3. $\pi'$ is "close" to $\pi$.

Here, "close" means that each element of difference $\vert M' - M \vert$ is sufficiently close to zero; each element of difference $\vert \pi' - \pi \vert$ is sufficiently close to zero.

In other words, is it possible to select arbitrary one stationary distribution $\pi \in \Pi$ by slightly perturbing the Markov chain $M$?

How about countable- or uncountable-state Markov chains?

$\endgroup$
1
$\begingroup$

Here is a refinement on Ian's answer that shows the desired thing can be done for any stationary distribution of the original chain (possibly being a convex combination of the distributions associated with each irreducible class). Fix $\epsilon$ such that $0<\epsilon<1$. We can make the error $O(\epsilon)$.


Consider a discrete time Markov chain with a finite state space $S$, transition probability matrix $P$, and let $\pi = (\pi_i)_{i \in S}$ be a particular stationary distribution, so that $\pi = \pi P$. Suppose this stationary distribution is not unique. Let $T$ be the set of transient states. Suppose there are $K$ irreducible classes (we know $K\geq 2$ since the stationary distribution is not unique). Let $A_1, ..., A_K$ be the states associated with each irreducible class (the $A_1, ..., A_K$ sets are disjoint).

Each class $k \in \{1, ..., K\}$ has a stationary distribution $\pi_k= (\pi_i^k)_{i \in S}$ such that $\pi_i^k = 0$ whenever $i \notin A_k$, and $\pi_i^k>0$ if $i \in A_k$. Further, $\pi$ is a stationary distribution of $P$ if and only if it can be written as a convex combination: $$ \pi = \sum_{k=1}^K \theta_k \pi_k $$ for some nonnegative values $\theta_1, ..., \theta_K$ that sum to 1.

  • Case 1: $\theta_k>0$ for all $k \in \{1, ..., K\}$. Then $\pi$ is such that $\pi_i >0$ for all $i \notin T$. Define a square matrix $R$ by $$ R = [\pi; \pi ; ... ; \pi ]$$ Define a modified transition probability matrix:
    $$ \tilde{P} = (1-\epsilon) P + \epsilon R $$ It is easy to see that this is a valid transition probability matrix, in that all rows are nonnegative and sum to 1. Further, $\tilde{P}$ is an $O(\epsilon)$ approximation of $P$. Since $\pi_i>0$ for all $i \notin T$, it follows from the $R$ matrix that all states not in $T$ are recurrent under the modified Markov chain with $\tilde{P}$, so this modified Markov chain has 1 irreducible class and hence it has a unique stationary distribution. In fact that unique distribution is exactly $\pi$ since: $$ \pi \tilde{P} = (1-\epsilon) \pi P + \epsilon \pi R = (1-\epsilon)\pi + \epsilon \pi = \pi $$ Thus, we can perturb the transition probabilities of the original Markov chain by $O(\epsilon)$ to get a new Markov chain with a unique stationary distribution exactly equal to the desired $\pi$. $\Box$

  • Case 2: $\theta_k=0$ for some $k \in \{1, ..., K\}$. Let $z$ be the number of indices $k \in \{1, ..., K\}$ such that $\theta_k=0$. Define: $$ \tilde{\theta}_k = \left\{ \begin{array}{ll} (1-\epsilon)\theta_k &\mbox{ if $\theta_k>0$} \\ \epsilon/z & \mbox{ if $\theta_k=0$} \end{array} \right.$$ Then $\tilde{\theta}_1, ..., \tilde{\theta}_k$ are strictly positive and sum to 1. Define $$ \tilde{\pi} = \sum_{k=1}^K \tilde{\theta}_k \pi_k $$ Then $\tilde{\pi}$ is an $O(\epsilon)$ approximation of $\pi$. Also, $\tilde{\pi}_i>0$ for all $i \notin T$, and $\tilde{\pi}$ is a stationary distribution of the original Markov chain with transition probability matrix $P$. So we can use the method in Case 1 to construct a matrix $\tilde{P}$ that is an $O(\epsilon)$ approximation of $P$ and that has a unique stationary distribution equal to $\tilde{\pi}$. Specifically, $$ \tilde{P} = (1-\epsilon)P + \epsilon[\tilde{\pi}; \tilde{\pi}; ... ; \tilde{\pi}]$$ $\Box$

$\endgroup$
  • $\begingroup$ The finite state space here is not crucial. Similar can be done for countably infinite (likely even uncountable): With prob $1-\epsilon$ transition as usual, with prob $\epsilon$ transition to states according to the distribution $\tilde{\pi}$. $\endgroup$ – Michael Mar 31 '18 at 7:00
  • $\begingroup$ This is similar in spirit: you make a much more dramatic topological change (if no states are transient then the graph in your case is complete). But in exchange you get to choose $\pi$ to be exactly what you want from the existing stationary distributions. +1. $\endgroup$ – Ian Mar 31 '18 at 16:48
1
$\begingroup$

Begin with a disjoint union of two irreducible chains on $A$ and $B$ and then add a transition from $A$ to $B$ and vice versa. Make the former much more likely than the latter but both quite unlikely. Renormalize your transition kernel as required. Now the new chain is irreducible but its unique stationary distribution is close to the stationary distribution of the original chain on $B$ (because in the long run, the chain spends most of its time in $B$).

Strictly speaking, since you haven't defined what it means for $M$ and $M'$ to be "close", this might violate your requirement. Indeed, the transition kernels are close in norm, but their connectivity graphs are completely different. However, such a marked change to the connectivity graphs is necessary in order to satisfy the desired criteria, because the requirements force $M$ to be reducible and force $M'$ to be irreducible (or irreducible modulo transient states).

$\endgroup$

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.