Markov Chain Monte Carlo, proposal distribution for multivariate Bernoulli distribution?

Question

Is there a suitable proposal distribution for multivariate Bernoulli model ?

for example I want to sample from a probability distribution

    p(x) = p*(x) / Z;

where x = {0,1}^M and Z is the normalization constant, Which is intractable to directly draw independent samples, so I resort to MCMC.

For multivariate continuous data, it is trivial to use Gaussian as a proposal distribution. Is there a suitable proposal distribution on such binary type data ?

p.s. I don't want to use Gibbs sampling because it is too slow for me.

Thanks

Answer 1

I think I found exactly what I want, which appears in last year's NIPS conference:

"Auxiliary-variable Exact Hamiltonian Monte Carlo Samplers for Binary Distributions"

Ari Pakman et al.

http://www.stat.columbia.edu/~liam/research/pubs/pakman-exact-binary-hmc.pdf

Answer 2

You're going to have to explain your model better. For standard variants of the multivariate Bernoulli model, Z is the dimensionality of x since the sum of probabilities over possible outcomes for each marginal is 1, and there's no dependence between the x_is.