Monte Carlo methods for sampling high-dimensional binary vectors.

Summary This thesis is devoted to the study of Monte Carlo methods for sampling high dimensional binary vectors from complex target laws. If the state-space is too large for an exhaustive enumeration, these methods allow to estimate the expectation of a given law with respect to a function of interest. Standard approaches are mainly based on random walk Markov chain Monte Carlo methods, where the stationary law of the chain is the distribution of interest and the trajectory mean converges to the expectation by the ergodic theorem. We propose a new sampling algorithm based on sequential Monte Carlo methods that are more robust to the multimodality problem thanks to a simulated annealing step. The performance of the sequential Monte Carlo sampler depends on the ability to sample according to auxiliary laws that are, in some sense, close to the law of interest. The main work of this thesis presents strategies to construct parametric families for sampling binary vectors with dependencies. The usefulness of this approach is demonstrated in the context of Bayesian variable selection and combinatorial optimization of pseudo-Boolean functions.