Contents
List of Figures xvii
List of Tables xix
Preface xxi
1 Introduction 1
1.1 Two examples 1
1.2 What is a perfect simulation algorithm? 2
1.3 The Fundamental Theorem of perfect simulation 3
1.4 A little bit of measure theory 5
1.4.1 Integrals 6
1.4.2 Densities 7
1.5 Notation 8
1.5.1 Distributions 9
1.5.2 Conditional distributions 9
1.6 A few applications 10
1.6.1 Markov random fields 11
1.6.2 Permutations 12
1.7 Markov chains and approximate simulation 13
1.8 Designing Markov chains 16
1.8.1 Gibbs sampling 17
1.8.2 Metropolis-Hastings 18
1.8.3 Auxiliary random variables 19
1.8.4 Slice sampler 20
1.8.5 Shift chains 20
1.9 Uniform random variables 21
1.10 Computational complexity 23
2 Acceptance/Rejection 25
2.1 The method 25
2.1.1 Example: drawing from the unit circle 26
2.2 Dealing with densities 27
2.2.1 Example: from Cauchy to normal 29
2.3 Union of sets 30
2.3.1 Example: AR for disjunctive normal form 30
xi
xii CONTENTS
2.4 Randomized approximation for #P complete problems 32
2.5 Gamma Bernoulli approximation scheme 34
2.5.1 Application: exact p-values 36
2.5.1.1 Testing for Hardy-Weinberg equilibrium 36
2.5.1.2 Testing for differential gene expression 37
2.6 Approximate densities for pe rfect simulation 37
2.6.1 Examp le: First passage time of Brownian motion 38
2.7 Simulation using Markov and Chernoff inequalities 39
2.7.1 Markov’s inequality as an AR algorithm 39
2.7.2 Chernoff bounds as an AR algorithm 40
2.7.3 Example: generating from the tails of a binomial random
variable 41
2.8 Where AR fails 42
3 Coupling from the Past 43
3.1 What is a coupling? 43
3.2 From the past 45
3.2.1 Varying the block size 48
3.2.2 Recu rsion as history 49
3.3 Monotonic CFTP 50
3.3.1 The Ising model 51
3.3.2 The ha rd-core gas model on bipartite graphs 52
3.3.3 Monotonicity and mixing times 53
3.4 Slice samplers 55
3.5 Drawbacks to CFTP 57
3.5.1 N oninterruptibility 57
3.5.2 Read twice 60
4 Bounding Chains 61
4.1 What is a bounding chain? 61
4.2 The hard-core gas model 62
4.2.1 The Dyer-Greenhill shifting chain 64
4.2.2 Bounding chains for the Strauss model 66
4.3 Swendsen-Wang bounding chain 66
4.4 Linear extensions of a partial order 68
4.5 Self-organizing lists 73
4.6 Using simple coupling with bounding chains 76
4.6.1 Sink-free orientations 76
5 Advanced Techniques Using Coalescence 81
5.1 Read-once coupling from the past 81
5.1.1 Example: ROCFTP for the Ising model 84
5.2 Fill, Machida, Mur doch, and Rosenthal’s method 85
5.2.1 Reversing a Markov chain 86
5.2.2 General FMMR 87
CONTENTS xiii
5.2.3 Example: FMMR for the Ising model 88
5.2.4 Doubling time 89
5.3 Variable chains 89
5.3.1 Antivoter model 89
5.4 Dealing with infinite graphs 91
5.5 Clan of ancestors 94
5.6 Deciding the length of time to run 95
6 Coalescence on Continuous and Unbounded State Spaces 97
6.1 Splitting chains 97
6.2 Multigamma coupling 98
6.2.1 Example: hierarchical Poisson/gamma model 99
6.3 Multishift coupling 100
6.3.1 Random walk with normals 102
6.4 Auto models 103
6.4.1 Example: autonormal model 104
6.5 Metropolis-Hastings for continuous state spaces 105
6.5.1 Example: truncated autonormal 105
6.6 Discrete auxiliar y variables 107
6.7 Dominated coupling from the past 109
6.7.1 Ex ample: Vervaat perpetuities 110
6.8 Using continuous state spaces for permutations 113
6.8.1 Height-2 posets 117
7 Spatial Point Processes 121
7.1 Acceptance/rejection 122
7.1.1 Covering points 123
7.2 Thinning 124
7.2.1 Example: a normal-intensity PPP 125
7.2.2 Using thinning to make the window easier 125
7.3 Jump processes 126
7.3.1 Example: Strauss process 127
7.3.2 Locally stable 128
7.4 Dominated coupling from the past for point processes 128
7.4.1 Example: dominated CFTP for the Strauss process 131
7.4.2 Running time 131
7.5 Shift moves 132
7.6 Cluster processes 135
7.6.1 Example: Gaussian daughters 136
7.7 Continuous-time Markov chains 137
7.7.1 Monotonic CFTP for Jackson queuing networks 137
xiv CONTENTS
8 The Randomness Recycler 141
8.1 Strong stationary stopping time 141
8.1.1 Example: SSST for simple symmetric random walk on
{1,2,...,n} 142
8.2 Example: RR for the Ising model 145
8.3 The general randomness recycler 149
8.3.1 Simple symmetric random walk 151
8.3.2 The Ising model 152
8.3.3 Using Metropolis-Hastings and the design property 153
8.4 Edge-based RR 154
8.5 Dimension building 157
8.5.1 Move ahead one chain 157
8.6 Application: sink-free orientations of a graph 159
9 Advanced Acceptance/Rejection 161
9.1 Sequential acceptance/rejection 161
9.2 Application: approximating permanents 163
9.2.1 Basic AR 164
9.2.2 Sequential AR 164
9.2.3 Union of D
i
bound 166
9.2.4 Generalized Bregman inequality 168
9.2.5 Lower bounds on permanents 171
9.2.6 Sinkhorn balancing 172
9.3 Partially recursive acceptance/rejection 176
9.3.1 Rearranging the order 177
9.3.2 Why use PRAR? 178
9.4 Rooted spanning trees by popping 179
10 Stochastic Differential Equations 183
10.1 Brownian motion and the Brownian bridge 184
10.2 An exponential Bernoulli factory 185
10.3 Retrospective exact simulation 186
10.3.1 Somewhat bounded 191
10.3.2 Example: stochastic logistic growth model 194
10.3.3 Unbounded 195
11 Applications and Limitations of Perfect Simulation 199
11.1 Doubly intractable distributions 199
11.2 Approximating integrals and sums 201
11.2.1 TPA 201
11.2.2 TPA for Gibbs distributions 203
11.3 Omnithermal approximation 203
11.3.1 Maximum likelihood estimators for spatial processes 204
11.3.2 Doubly intractable distributions with one spatial parameter 205
11.3.3 Example: Mat´ern type III processes 205
CONTENTS xv
11.4 Running time of TPA 208
11.5 The paired product estimator 209
11.6 Concentration of the running time 211
11.6.1 Subpolynomial tails on the runtime 213
11.6.2 Concentration for CFTP 215
11.7 Relationship between sampling and approximation 215
11.8 Limits on perfect simu lation 216
11.9 The future of perfect simulation 218
Bibliography 219
Index 227
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.