Sample from a multivariate gaussian distribution given a linear constraint on samples

Given a covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$, I want to produce a sample $x \in \mathbb{R}^n$ from the corresponding multivariate normal distribution, but conditioning on $x$ satisfying some constraint.

The simplest constraint is $sum(x) = 0$. More generally, I could mandate a set of linear equalities $A x = b$.

Most generally, I would ask that $x$ satisfy a constraint like $f(x) = 0$.

The very most general question is, if I know how to sample from a multivariate distribution $\mathcal{D}$, how would I sample from that distribution conditioned on the constraint $f(x) = 0$?

How could I do this? I'd imagine there's a good solution for at least the Gaussian + linear case.

My current guess at a solution is something like Gibbs sampling:

1. Initialize $x$ to be something
2. Randomly choose two indices $i,j$ and fix each component of $x$ except $x_i$ and $x_j$.
3. Let $x_j = g(x_i)$, where $g$ is such that $x$ will satisfy the given constraint.
4. The only free variable left is $x_i$. Sample $x_i$ from the single-variate distribution, which (e.g. for a gaussian dist.) is proportional to $\exp\left( x^\intercal \Sigma^{-1} x \right)$ where only $x_i$ is free, $x_j$ is a function of $x_i$, and the rest are fixed.
5. Go back to step 2 to repeat a few hundred times for a good sample.

From a probabilistic perspective, if $X\sim\mathcal{N}_n(0,\Sigma)$, then the distribution of $X$ conditional on $AX=b$ is arbitrary because the subspace defined by the constraint has probability zero.
One way of defining the conditional distribution is to do a change of variables: find a projection matrix $B_1$ on the subspace $\{AX=b\}$ and an orthogonal subspace with projection matrix $B_2$, then consider the linear change of variable from $X$ to $Y=(B_1X,B_2X)$. Conditional on $AX=b$, the distribution of $Y$ is a Dirac mass on the first part and a $\mathcal{N}_p(0,B_2\Sigma B_2^\text{T})$ on the second part (since $B_1X$ and $B_2X$ are independent).
• Sorry, I totally understand it now. Thanks so much! Any similar things for the more general case? Like if the constraint was $A \left(x^3\right) = b$? Or if the distribution was something else we could sample from? – chausies Sep 13 '17 at 13:37