Loading...
Please wait, while we are loading the content...
Similar Documents
CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002
| Content Provider | CiteSeerX |
|---|---|
| Author | Alistair, Lecturer Eriksson, Nick Chen, Li-Chung Scribes, Sinclair |
| Abstract | the number of k-matchings of G (matchings with k edges), then Z() = P m k , the matching polynomial of G. 14-1 Markov chain: We de ne a Markov chain on the space of matchings using three kinds of transitions: edge addition, edge deletion, and edge exchange (deleting an edge and adding an edge sharing one vertex with the deleted edge). We make the Markov chain lazy and use the Metropolis rule to make the stationary distribution match the Gibbs distribution, as follows. At a matching M 2 (Laziness) With probability 1=2, stay at M . Otherwise, choose an edge e = (u; v) 2 E u.a.r. (Edge addition) If both u and v are unmatched in M , then go to M + e. (Edge deletion) If e 2 M , then go to M e with probability 1= (else stay at M ). (Edge exchange) If exactly one of u and v is matched in M , let e be the unique edge in M containing u or v, and go to M + e e . If both u and v are matched, then do nothing. This Markov Chain follows the Metropolis rule. Edge addi |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Edge Addition Else Stay 14-1 Markov Chain Unique Edge Edge Deletion Deleted Edge Stationary Distribution Cs294-2 Markov Chain Monte Carlo Edge Addi Markov Chain Lazy Edge Exchange Markov Chain Foundation Application Metropolis Rule Gibbs Distribution |
| Content Type | Text |
