# Uniform sampling of constrained binary vectors by Gibbs sampling

General statement of the problem: Let $x,y$ be two binary vectors, connected by the following constrains:

$$y=f(x),\qquad x=g(y)$$

That is, $x$ determines $y$, and $y$ determines $x$. There are many pairs $(x,y)$ satisfying both constrains, and I want to sample them uniformly.

Note that $x$ and $y$ can have many components. Assume that $f(x)$ and $g(y)$ are easy to compute.

Gibbs sampling

Define:

$$p(y|x)=\delta_{y,f(x)}, \quad p(x|y)=\delta_{x,g(y)}$$

These distributions are trivial to sample. Hence I devise a Gibbs sampling of the following form. Starting from a random $x_1$, compute:

$$y_1=f(x_1),x_2=g(y_1),y_2=f(x_2),\dots$$

Assume that this sequence converges to a solution $(x,y)$ for every starting value $x_1$. The set of solutions obtained this way should, according to the Gibbs sampling methodology, represent a uniform sample of the space of solutions $(x,y)$.

This is my intuition. I need to prove or disprove that the solutions obtained this way give or not a uniform sample of all solutions. If the answer is negative, please explain what assumptions of the Gibbs sampling strategy that I may be violating.

• Given that $y$ is a deterministic function of x, $p(y|x) = 0$ for all $y \neq f(x)$ and $=1$ for $y = f(x)$. Should be clear that unless $x = g(f(x))$, i.e., $f$ and $g$ are inverses of each other, you'll have a situation where $p(y|x) = 1$ yet $p(x|y)=0$, contradictory, for some $(x,y)$ pair. If they are inverses, you'll have a very fast and ineffective sampler; you'll start with an $x$, generate the corresponding $y$, which you could have just calculated via $y=f(x)$, generate $x$ back again, which you already knew was the appropriate $x$, and you'll never sample another $(x,y)$ pair. – jbowman Mar 23 '16 at 17:01
• @jbowman $p(y|x)=1$ and $p(x|y)=0$ whenever $y=f(x)$ but $x\ne g(y)$, which may occur if $(x,y)$ is not a solution. – becko Mar 23 '16 at 17:12
• Right. So $f$ and $g$ must be inverses of each other, and for every $x$, you'll have exactly one $y$, which can be calculated via $f$ - no sampling required, and similarly for $x | y$, if you start your sampler with a particular $x$, you'll just get the corresponding $y$, then the original $x$ back again, then the same $y$ again, ad infinitum. – jbowman Mar 23 '16 at 17:15
• @jbowman No. $f$ and $g$ are inverse of each other only inside the subset of solutions. For non-solutions $(x,y)$, obviously $x\ne g(f(x))$. – becko Mar 23 '16 at 17:17
• Using a Gibbs sampler with Dirac masses as proposals means it is stuck forever with the starting values. Hence, it immediately converges to its stationary which is the Dirac mass. Obviously, there is no point in using a Gibbs sampler in this setting. – Xi'an Apr 7 '16 at 9:53