Jose Blanchet - Doob's h-transform, Lyapunov inequalities and Efficient Monte Carlo Methods

Optimal Monte Carlo procedures can often be characterized by positive harmonic functions associated to Doob's h-transforms. We shall illustrate how to take advantage of available information on such functions to design efficient Monte Carlo methods. Rigorous testing of the efficiency of these methods is done via Lyapunov-type inequalities. We illustrate these techniques in a wide variety of settings including counting combinatorial structures and estimation of large deviation probabilities.

Joe Blitzstein - Importance Sampling vs. MCMC for Discrete Data: Friends or Enemies?

Importance sampling and MCMC are two competing methods for estimating expectations with respect to a difficult-to-sample-from distribution. We will discuss some discrete examples for which it is possible to compare their efficiencies. Although importance sampling and MCMC are very different approaches, we argue that finding a good importance sampler is very closely connected to finding a good (fast-mixing) Markov chain: a good "move" in the chain suggests a good sequential step for importance sampling. We apply these ideas to tournament (paired comparison) data.

Arnaud Doucet - The expected auxiliary variables method for MC simulation

The expected auxiliary variable method is a general framework for Monte Carlo simulation in situations where the target distribution of interest is untractable thus preventing the implementation of classical methods. The method finds application in situations where marginal computations are of interest, transdimensional move design is difficult in model selection setups, when the normalising constant of a particular distribution is unknown but required for exact computations. I will present several examples of applications of this principle as well as some theoretical results that we have recently obtained in some scenarios.

Paul Dupuis - Importance sampling for stochastic networks

We consider two aspects of the use of importance sampling for rare event estimation. The first has to do with the estimation of different events using a common set of samples. In particular, for the problem of estimating hitting probabilities, we will describe how a change of measure based on the Freidlin­Ventsel quasipotential can be used to simultaneously estimate probabilities for different events in an asymptotically optimal fashion. We then specialize the observation to certain stochastic networks, and describe in concrete terms how to construct the sampling measure.

David Gamarnik - Correlation decay and applications to counting and optimization

Loosely speaking, a complex system exhibits a correlation decay property if correlations between components of the system decay as a function of a distance between the components. The notion appears primarily in the context of Gibbs measures in statistical physics, but appears to have algorithmic applications. We first illustrate how correlation decay property can be used to design a deterministic algorithm for counting partial matching of a graph. The running time of the algorithm is polynomial when the degree of the graph is constant and sub-exponential in the general case. Previous algorithm for this problem relied on Monte-Carlo technique and thus required randomization. We further discuss application of this method for computing an entropy (the limit of the log-partition function) of the monomer-dimer model on a grid, improving significantly previous estimates. Finally (time-permitting), we will discuss a problem of optimization on a graph where costs associated with edges have a Gaussian distribution. We show again that under certain assumption on the Gaussian parameters, the system exhibits decay of correlation which leads to designing an efficient algorithm for deriving the optimal solution.

Mark Huber - An overview of perfect sampling methods

Perfect sampling algorithms generate samples exactly from a target distribution that is typically described by an unnormalized density, where the normalization constant is difficult to compute. Early perfect samplers were based on classical Markov chain approaches, but newer approaches employ very different methods. In this talk I will give an overview of four different methodologies for creating perfect sampling algorithms: Coupling From the Past, the Randomness Recycler, Sequential Acceptance/Rejection, and Partial Recursive Acceptance/Rejection, illustrating their use through examples and simple analyses of their running times.

Pierre L'Ecuyer - Randomized Quasi-Monte Carlo for Markov Chains

Quasi-Monte Carlo (QMC) and randomized quasi-Monte Carlo (RQMC) methods usually beat the standard Monte Carlo (MC) method when estimating the integral of a smooth function $f$ in a small or moderate number of dimensions. Sometimes, a smaller ``effective'' dimension than the nominal dimension of $f$ can be obtained by sampling the function in a different way, via a change of variables, and this may make QMC and RQMC much more effective. But if $f$ depends on the sample path of a Markov chain over a large number of steps, it is usually hard to find a change of variables that reduces the effective dimension to a small value. So one may conclude that QMC and RQMC methods are not effective for such Markov chains. In this talk, we review some key ideas of classical QMC and RQMC methods, and we present an RQMC method, named array-RQMC, designed to simulate Markov chains over a large number of steps. We provide examples showing that properly adapted RQMC and array-RQMC methods can dramatically reduce the variance compared with standard MC when simulating Markov chains.

Jun S. Liu - Monte Carlo Methods for Studying Protein Structures

I will describe some of our recent efforts in the development of Monte Carlo strategies (both MCMC and SMC) for simulating and optimizing molecular structures. I will illustrate these ideas using examples from Hydrophobic-Hydrophilic (HP) protein model (both 2-D and 3-D) optimization, protein side-chain entropy (SCE) estimation, and near-native structure (NNS) simulations. By applying the new SMC and MCMC schemes, we were able to achieve the best results for all the 2-D and 3-D HP structural optimization examples we can find in the literature. In particular, the new approach achieved better results for these HP models than a modified PERM algorithm and the equi-energy Sampler (Kou et al. 2006). For the SCE and NNS problems, we can characterize accurately many important ensemble properties of NNS and compute efficiently the SCE of a given structural backbone for any given energy function. We also found that widely used pairwise potential functions behaved surprisingly badly for stabilizing near native protein structures, and adding a term representing the SCE of the protein can help greatly in discriminating true native structures from decoys.

Prasad Tetali - Some recent applications and analyses of Markov Chains

I will describe a few recent contributions to this topic, thanks to joint work with various collaborators. The first is the notion of a spectral profile which provides a unified analytic framework to derive analytic and isoperimetric bounds on mixing times in finite Markov chains. The second is a birthday paradox for finite Markov chains. Applications include analyses of some card shuffles, and Pollard's rho algorithm for the discrete logarithm problem in cyclic groups.