Gibbs sampling for reducible chain

Question

I am new to Gibbs sampling and I ran into a problem with irreducibility. For the Gibbs sampler to work the Markov chain has to be irreducible. But that assumption is not satisfied in my probability distribution. Is there a way to overcome this problem and still do sampling ?

If I explain this in an example. Assume I have a Markov model and my state vector is a binary vector. Let $X_t$ be the state vector at time $t$ and $x_{t,i}$ is the $i^{th}$ element of state vector at time $t$. In my transition probabilities, probability of going from 0 to 1 is equal to the number of ones in previous time step divided by total elements. For example, if $X_{t-1}=[0,0,1,0]$, in next time step each element can go to 1 with a probability of 0.25. All element can go from 1 to 0 with some probability say $\gamma$. Assuming transition probabilities are independent given the previous state, I can write follows.

$P(X_t\vert X_{t-1})= \prod_\limits{i=1}^4P(x_{t,i}\vert X_{t-1})$

I am drawing samples from this model. I am sampling in the increasing order of time and $i$. First the first element of $X_1$, next the second element of $X_1$ and so on. Now assume at a particular sample I got the following samples for $t-1,t,t+1$.

$X_{t-1}=[0,0,1,0]$, $X_{t}=[1,0,0,0]$,$X_{t+1}=[0,0,1,0]$

Now assume I am drawing the next sample given these values, and let's say the 1 in $X_{t-1}$ (3rd element) flipped back to 0 (This can happen if $\gamma > 0$). Then assume I am sampling the 1st element at time $t$. This probability can be given as follows,

$P(x_{t,1}\vert X_{t-1},x_{t,2},x_{t,3},x_{t,4},X_{t+1})\propto P(x_{t,1} \vert X_{t-1})P(X_{t+1}\vert x_{t,1},x_{t,2},x_{t,3},x_{t,4}) = P(x_{t,1} \vert X_{t-1})\prod_\limits{i=1}^4P(x_{t+1,i}\vert x_{t,1},x_{t,2},x_{t,3},x_{t,4})$

Since there are no ones in new sample at time $t-1$ the value $P(x_{t,1} \vert X_{t-1})$ will be non-zero only if $x_{t,1}=0$. But in the next product term $P(x_{t+1,3}|x_{t,1},x_{t,2},x_{t,3},x_{t,4})$ will become zero since $x_{t+1,3}=1$ (this is given from previous sample) and all the elements in previous time step is zero, when $x_{t,1}=0$.

Because of this situation I can't sample $x_{t,1}$. Since $P(x_{t,1}=0)=0$ and $P(x_{t,1}=1)=0$ omitting conditioning variables. I think this is due to non-irreducibility of my model. (There's no way to go to state 1 if all the elements in previous state is zero).

According to Xi'an do I have to change the transition model if I were to use Gibbs sampling ? Or is there any work around for this ?

I have a long sequance of $X_t$'s with at least about 100 components. So I think for example to take MAP estimate I have to maximize over about $2^{100*T}$, which is impossible. That's why I moved to Gibbs sampling. I am glad to hear if there's any other suggestions to do a inference in this type of a distribution. FYI,In addition to this there is a observation model on top of this more like a HMM.

Answer 1

If your Gibbs sampler produces a non-irreducible Markov chain, it means there are parts of the space with positive mass under the target distribution that are never visited by the chain (for some starting values). In order to produce an irreducible chain, you need adding moves to the original Gibbs sampler, for instance by using re-parametrisations that link the disconnected parts of the support that the original Markov chain cannot simultaneously visit.

However, your example has nothing to do with Gibbs sampling so I do not understand the question. If the distribution to be simulated is of the form $$\prod_{t=1}^T \prod_\limits{i=1}^4P(x_{t,i}\vert X_{t-1})$$ with a fixed value for $X_0$, it proceeds by simulating once $X_1$ by simulating its components, then $X_2$ by simulating its components, and so on until $X_T$. There is no reason to cycle iteratively through the $X_t$ and to condition upon the neighbours as in Gibbs sampling.

If you insist on using Gibbs sampling for a reason I cannot fathom!, your counterexample does not work because you cannot simulate values for any $x_{it}$ that is incompatible with the other components of $X_t$ and/or the next and/or the previous values $X_{t+1}$ and $X_{t-1}$. In essence, the current value of the variable to be simulated should always be acceptable as the next value.

"This happens with probability $\gamma > 0$" is invalid, because $x_{3(t-1)}$ needs to be simulated conditional on $X_{t-2}$ and $X_t$, not on its own.

A basic Gibbs sampler applied to this problem produces a Markov chain that is not irreducible because the identically zero sequence is a trapping state and it can be reached with positive probability from any starting sequence, moving backward by replacing the rightmost non-zero $X_t$ by $(0,...,0)$ [this happens with positive probability], one term at a time. To find the MAP of this system (whether or not this makes sense, since the null sequence has the highest probability of $1$), I would suggest dynamic programming.