# Invariant Distribution in a special case of Markov Chains

Suppose I have a finite set say $C=\{c_0,c_1,\ldots,c_R\}$ which are some disjoint subsets of the space say $\{0,1\}^m$. The cardinality of the union of these subsets is much less than $2^m$ say.

If I start randomly from any subset of this class $C$ (say draw uniformly according to its size) then I move to the next state according to a matrix $P$ which describes probabilities of moving from any class to any other class inside $C$ or going to $\{0,1\}^m\setminus C$. If the probability of going from $\{0,1\}^m\setminus C$ to $C$ is zero is there any chance of having an invariant distribution for this model?

I find that reccurence and irreducibility of the graph ensure the existence of an invariant distribution. However, is there any chance of having an invariant distribution under this scenario?

-
a) $C$ is not a subset of $\{0,1\}^m$, but a set of subsets of $\{0,1\}^m$; thus $\{0,1\}^m\setminus C$ isn't defined. b) Your use of "set" and "class" is very confusing. Are you calling the subsets "classes inside $C$" in the second paragraph? c) It's unclear what your state space is. You start from "any subset of this class $C$" -- do you mean "any element of $C$"? Then later you refer to "the probability of going [...] to $C$" -- is $C$ also a possible state? Or is this just a sloppy way of saying "the probability of going [...] to an element of $C$"? –  joriki Nov 26 '12 at 17:13
a) Yes C is a set of subsets which are all disjoint. The complement is ${0,1}^m$\ $/union{c_i}$. b) All this $c_i$ are again sets with elements. and the probability matrix describes if I am in a set to go to another side either in C or go outside in the complement but then never come back –  Hashed Nov 26 '12 at 17:45
What I want to see actually is that if there is a chance of an invariant distribution if the graph does not have at least one of the properties recurence and irreducibility –  Hashed Nov 26 '12 at 17:49

It seems that the situation you have in mind is that the state space $S$ of the Markov chain can be partitioned into a disjoint union $S=S_0\cup S_1$ such that every transition probability $Q(x,y)$ from a state $x$ in $S_1$ to a state $y$ in $S_0$ is zero. Then the restriction of $Q$ to $S_1\times S_1$ is a transition matrix as well hence $Q$ has an invariant distribution $\pi$ which is concentrated on $S_1$, that is, such that $\pi(S_1)=1$ and $\pi(S_0)=0$. If furthermore, for every $x$ in $S_0$ there exists a path to $S_1$ which has positive probability, then every invariant distribution of $Q$ is concentrated on $S_1$.

-
Using your notation as above, lets say that $S_0=\{s_0\}$is a single state and $S_1=\{s_1,s_2,...,s_N\}$ such that the probability $p(s_0 -> s_i)=0$ for all the states but $p(s_i -> s_0)$ is positive for many states. Then the invariant distribution restricts on $S_1 \times S_1$? If I have the $(N+1)\times(N+1)$ matrix $P$ for all transitions then $\pi$ is found by solving $(0,\pi_1,...,\pi_N) P = (0,\pi_1,...,\pi_N)$, i.e ignoring the first class $s_0$ ? –  Hashed Nov 28 '12 at 10:35
You switched $S_0$ and $S_1$. With the notations of your comment, $s_0$ is called an absorbing state and the only stationary distribution is the Dirac probability at $s_0$ (as soon as $s_0$ is accessible starting from every other state). –  Did Nov 28 '12 at 12:15

In order for an invariant distribution to exist, it is necessary and sufficient that at least one state is positive recurrent. In particular, every Markov chain with a finite number of states has a stationary distribution.

If your chain is not irreducible, just pick a closed irreducible subset. Since your chain is finite, this subset will be a positive recurrent, irreducible chain and hence has an invariant distribution. Now extend this distribution to the rest of the states by giving them measure zero.

If your chain has more than one closed irreducible subset, it will have more than one invariant distribution (indeed, infinitely many).

-