A Brief History of Markov Chain Monte Carlo and Randomized Quasi-Monte Carlo Sampler

Abstract

A Brief History of Markov Chain Monte Carlo and Randomized Quasi-Monte Carlo Sampler Yuchung J. Wang Department of Mathematical Sciences, Rutgers University, USA ?: Since 1990, Markov Chain Monte Carlo (MCMC) has revolutionizes statistical computations because it makes many Bayesian calculations feasible. I will begin with introductions of Markov chain and two generic algorithms of MCMC: Metropolis-Hastings algorithm and the Gibbs sampler. Even after twenty some years of theoretical development, MCMC still have unsettled issues such as where to initiate the chain, the length of burn-in, MCMC sample size, the convergence diagnostic, and most urgent, the estimation of Monte Carlo error. The singular cause of all these issues is the dependence among samples generated by MCMC. As long as such dependence is not quantified, all of the issues shall remain. A Beta-binomial example is used to illustrate the discrepancy between a theoretical result on burn-in and the simulations. I suggest that Markov chain is probably not the best paradigm to study MCMC because many Markov-chain-type algorithms were never analyzed as Markov chains. Based on a characterization of probability density function (pdf), odds may offer a different revenue to understand MCMC. Thus, an odds-based sampler, which is capable of generating independent samples from any pdf, is proposed. We name it randomized Quasi-Monte Carlo sampler because it takes advantages of the computational efficiency of Quasi Monte Carlo. Some numerical results will be presented and comparisons with MCMC algorithms are discussed. The talk is indented to provide a general understanding of the current status of MCMC and its possible remedies. Materials of the talk are taken from my joint works with Kun-Lin Kou, and with Jianhui Ning, Yongdao Zhou and professor Kai-Tai Fang. I met both Kun-Lin Kou and Jianhui Ning when I visited the institute in 2009. ?