What is an efficient way of sampling from a discrete multivariate normal distribution with pdf

$$ p(z) = \frac{1}{Z} e ^ {-\frac{1}{2}(z-\mu)^\top\Sigma^{-1}(z-\mu)} $$ such that $z \in \mathbb{Z}_k^n$? Here $\mathbb{Z}_k = \{z : -k \le z \le k, z\in\mathbb{Z}\}$.

I've contemplated rejection sampling based on drawing uniform samples from $\mathbb{Z}_k^n$, but this scales poorly with $n$.

I have found some extended discussions of sampling from 1D discrete Gaussians, but in my case I can not assume that $\Sigma$ is the identity, so I'm not sure how that is helpful to me.


From my experiments, block Gibbs sampling is much better at higher dimensions than rejection sampling which doesn't work at all in dimensions above 5, even for modestly sized grids. The math is a bit more involved to derive the correct formulas for block Gibbs but it is well worth it.

| cite | improve this answer | |

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.