Monte Carlo Statistical Methods

Markov Chain Monte Carlo MethodsMarkov Chain Monte Carlo MethodsChristian P. RobertUniversit´e Paris-Dauphine, IuF, & CRESthttp://www.ceremade.dauphine.fr/~xianNovember 17, 2010Markov Chain Monte Carlo MethodsTextbook: Monte Carlo Statistical Methodsby Christian. P. Robert and George CasellaSlides: Adapted from (mostly)http://www.ceremade.dauphine.fr/~xian/coursBC.pdfOther suggestedreading...Markov Chain Monte Carlo MethodsOutlineMotivations, Random Variable Generation Chapters 1 & 2Monte Carlo Integration Chapter 3Notions on Markov Chains Chapter 6The Metropolis-Hastings Algorithm Chapter 7The Gibbs Sampler Chapters 8–10Further Topics Chapters 11∗ & 14∗Markov Chain Monte Carlo MethodsMotivation and leading exampleMotivation and leading exampleMotivation and leading exampleIntroductionLikelihood methodsMissing variable modelsBayesian MethodsBayesian troublesRandom variable generationMonte Carlo IntegrationNotions on Markov ChainsThe Metropolis-Hastings AlgorithmThe Gibbs SamplerFurther TopicsMarkov Chain Monte Carlo MethodsMotivation and leading exampleIntroductionLatent structures make life harder!Even simple models may lead to computational complications, asin latent variable modelsf (x|θ) =f (x, x |θ) dxIf (x, x ) observed, fine!If only x observed, trouble!Markov Chain Monte Carlo MethodsMotivation and leading exampleIntroductionExample (Mixture models)Models of mixtures of distributions:X ∼ fj with probability pj,for j = 1, 2, . . . , k, with overall densityX ∼ p1f1(x) + · · · + pkfk(x) .For a sample of independent random variables (X1, · · · , Xn),sample densityn{p1f1(xi) + · · · + pkfk(xi)} .i=1Expanding this product involves kn elementary terms: prohibitiveto compute in large samples.Markov Chain Monte Carlo MethodsMotivation and leading exampleIntroduction321µ 20−1−10123µ1Case of the 0.3N (µ1, 1) + 0.7N (µ2, 1) likelihoodMarkov Chain Monte Carlo MethodsMotivation and leading exampleLikelihood methodsMaximum likelihood methodsGo Bayes!!◦ For an iid sample X1, . . . , Xn from a population with densityf (x|θ1, . . . , θk), the likelihood function isL(x|θ)=L(x1, . . . , xn|θ1, . . . , θk)n=f (xi|θ1, . . . , θk).i=1ˆθn = arg max L(x|θ)θ◦ Global justifications from asymptotics◦ Computational difficulty depends on structure, eg latentvariablesMarkov Chain Monte Carlo MethodsMotivation and leading exampleLikelihood methodsExample (Mixtures again)For a mixture of two normal distributions,pN (µ, τ 2) + (1 − p)N (θ, σ2) ,likelihood proportional tonxi − µxi − θpτ −1ϕ+ (1 − p) σ−1 ϕτσi=1containing 2n terms.Markov Chain Monte Carlo MethodsMotivation and leading exampleLikelihood methodsStandard maximization techniques often fail to find the globalmaximum because of multimodality or undesirable behavior(usually at the frontier of the domain) of the likelihood function.ExampleIn the special casef (x|µ, σ) = (1 − ) exp{(−1/2)x2} +exp{(−1/2σ2)(x − µ)2}σ(1)with> 0 known, whatever n, the likelihood is unbounded:lim L(x1, . . . , xn|µ = x1, σ) = ∞σ→0Document Outline

• Motivation and leading example
  • Introduction
  • Likelihood methods
  • Missing variable models
  • Bayesian Methods
  • Bayesian troubles
• Random variable generation
  • Basic methods
  • Uniform pseudo-random generator
  • Beyond Uniform distributions
  • Transformation methods
  • Accept-Reject Methods
  • Fundamental theorem of simulation
  • Log-concave densities
• Monte Carlo Integration
  • Introduction
  • Monte Carlo integration
  • Importance Sampling
  • Acceleration methods
  • Bayesian importance sampling
• Notions on Markov Chains
  • Basics
  • Irreducibility
  • Transience and Recurrence
  • Invariant measures
  • Ergodicity and convergence
  • Limit theorems
  • Quantitative convergence rates
  • Coupling
  • Renewal and CLT
• The Metropolis-Hastings Algorithm
  • Monte Carlo Methods based on Markov Chains
  • The Metropolis--Hastings algorithm
  • A collection of Metropolis-Hastings algorithms
  • Extensions
• The Gibbs Sampler
  • General Principles
  • Completion
  • Convergence
  • The Hammersley-Clifford theorem
  • Hierarchical models
  • Data Augmentation
  • Improper Priors
• Further Topics
  • MCMC tools for variable dimension problems
  • Introduction
  • Green's method
  • Birth and Death processes
  • Sequential importance sampling
  • Adaptive MCMC
  • Importance sampling revisited
  • Dynamic extensions
  • Population Monte Carlo