CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2008)
Lecturer Alistair, Sinclair Scribes, Kamin Whitehouse, Bhaskara Marthi
niversal constant C. Proof: We will assume W = 0; the extension to general W is simple. Let the w i be scaled so that min|w i = 1. Assume that max|w i = B. We will first show that there exists a...
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2008)
Lecturer Alistair, Sinclair Scribes, Brighten Godfrey, Kamalika Chaudhuri
p evolution of M from time i to time j: F i = f j-1 f j-2 . . . f i+1 f i (10.2) The standard "forward simulation" of M for t steps, starting at time 0, is thus given by F 0 . (Note,...
Lecturer Alistair, Sinclair Scribes, Kaushik Datta, Elitza Maneva
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. After...
Lecturer Alistair, Sinclair Scribes, Itzik Parnafes, Alice Zheng
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. Reminder...
Definition 8.1 Let f: # # (2007)
Lecturer Alistair, Sinclair Scribes, Mark Paskin, David Latham
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. This...
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Brian Milch, Manjunath Krishnapur
ith X 0 = x and Y 0 = y. We define the coupling as follows: X t and Y t both choose the same i and the same b at every step. Clearly this satisfies the two conditions (i) and (ii) in the above...
Rotation f Figure 9.1: Domino Tilings (2007)
Lecturer Alistair, Sinclair Scribes, Sourav Chatterji, Sumit Gulwani, Lozenge Tilings
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. 9.1...
Lecturer Alistair, Sinclair Scribes, Li-chung Chen, Nick Eriksson
Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications. They may be distributed outside this class only with the permission of the Instructor. Last...
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Yanlei Diao, Xiaofeng Ren
e Metropolis MC is reversible w.r.t. #(x) = w(x)/Z. Proof: Recall that a Markov Chain P is reversible w.r.t a probabilistic distribution q if #x, y q(x)P (x, y) = q(y)P (x, y). If x y, then both...
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Gabor Pete, Sam Riesenfeld
utions to the "0-1 knapsack problem" with n objects with weights a i and knapsack capacity b. Theorem 16.1 For any {a i=1 and b, # mix = O(n 4.5+# ). We will prove a weaker polynomial bound...
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Richard Bourgon, Bhaskara Marthi
n e. This upper bound is in fact tight, up to the lower order term, and we now sketch why that's true: 4-1 We can identify a speci c event with a probability under p x substantially dierent from...