PMC for combinatoric spaces

I received this interesting [edited] email from Xiannian Fan at CUNY:

I am trying to use PMC to solve Bayesian network structure learning problem (which is in a combinatorial space, not continuous space).

In PMC, the proposal distributions q_i,t can be very flexible, even specific to each iteration and each instance. My problem occurs due to the combinatorial space.

For importance sampling, the requirement for proposal distribution, q, is:

support (p) ⊂ support (q)             (*)

For PMC, what is the support of the proposal distribution in iteration t? is it

support (p) ⊂ U support(q_i,t)    (**)

or does (*) apply to every q_i,t?

For continuous problem, this is not a big issue. We can use random walk of Normal distribution to do local move satisfying (*). But for combination search, local moving only result in finite states choice, just not satisfying (*). For example for a permutation (1,3,2,4), random swap has only choose(4,2)=6 neighbor states.

Fairly interesting question about population Monte Carlo (PMC), a sequential version of importance sampling we worked on with French colleagues in the early 2000’s.  (The name population Monte Carlo comes from Iba, 2000.)  While MCMC samplers do not have to cover the whole support of p at each iteration, it is much harder for importance samplers as their core justification is to provide an unbiased estimator to for all integrals of interest. Thus, when using the PMC estimate,

1/n ∑_i,t {p(x_i,t)/q_i,t(x_i,t)}h(q_i,t),  x_i,t~q_i,t(x)

this estimator is only unbiased when the supports of the q_i,t “s are all containing the support of p. The only other cases I can think of are

1. associating the q_i,t “s with a partition S_i,t of the support of p and using instead

   ∑_i,t {p(x_i,t)/q_i,t(x_i,t)}h(q_i,t), x_i,t~q_i,t(x)

2. resorting to AMIS under the assumption (**) and using instead

   1/n ∑_i,t {p(x_i,t)/∑_j,t q_j,t(x_i,t)}h(q_i,t), x_i,t~q_i,t(x)

but I am open to further suggestions!