CONTENTS 1 Introduction············· 1.1 Our results........ 1 1.2 Related work 44444.4.4。 2 1.3 Organization of the paper..··. 2 Dynamic inference problem 3 2.1 Markov random fields... 3 2.2 Probabilistic inference and sampling 3 2.3 Dynamic inference problem ........................ x 3 Main results 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 5 4 Preliminaries 4.4 6 5 Outlines of algorithm 8 6 Dynamic Gibbs sampling......... 9 6.1 Coupling for dynamic instances.......... 10 6.2 Data structure for Gibbs sampling 17 6.3 Single--sample dynamic Gibbs sampling algorithm.·.··....... 6.4 Multi-sample dynamic Gibbs sampling algorithm 21 7 Proofs for dynamic Gibbs sampling..····..············ 24 7.1 Analysis of the couplings...·.·················· 24 7.2 Implementation of the algorithms............................. 29 7.3 Dynamic Gibbs sampling for specific models·······.··.··········· 30 8 Proofs for dynamic inference 37 8.1 Proof of the main theorem..··.······.·············· 37 8.2 Dynamic inference on specific models 37 9 Conclusion············· 38 References.....·.········· 38Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Organization of the paper. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Dynamic inference problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Markov random fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Probabilistic inference and sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Dynamic inference problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5 Outlines of algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6 Dynamic Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.1 Coupling for dynamic instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.2 Data structure for Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.3 Single-sample dynamic Gibbs sampling algorithm . . . . . . . . . . . . . . . . . . . . 18 6.4 Multi-sample dynamic Gibbs sampling algorithm . . . . . . . . . . . . . . . . . . . . 21 7 Proofs for dynamic Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.1 Analysis of the couplings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.2 Implementation of the algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.3 Dynamic Gibbs sampling for specific models . . . . . . . . . . . . . . . . . . . . . . 30 8 Proofs for dynamic inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 8.1 Proof of the main theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 8.2 Dynamic inference on specific models . . . . . . . . . . . . . . . . . . . . . . . . . . 37 9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38