MIT 6 856J - Study Guide (2 pages)

Previewing page 1 of 2 page document View the full content.
View Full Document

Study Guide



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

Study Guide

24 views


Pages:
2
School:
Massachusetts Institute of Technology
Course:
6 856j - Randomized Algorithms

Unformatted text preview:

6 856 Problem Set 13 Final Dec 2nd 2002 1 a The loops make it aperiodic and so we merely need show irreducibility strong connectedness to get unique stationary distribution We need to show that from a pair T1 r1 we can get to another pair T2 r2 Note rst that for a given spanning tree T we can always get from T r1 to T r2 simply by moving the root along the edges of the tree So it remains to show that we can get from one spanning tree to another Note that since all spanning trees have the same number of edges the set of edges that belong to T1 and not T2 must be equal in size to the set that belongs to T2 and not T1 s t the union of these two sets U is even in size Pick any edge e in T2 T1 This creates a cycle in T1 e hence there must be some e on the cycle that is also in T1 T2 We walk the root to an endpoint of e and move the root over e to add e and remove the edge after e in the direction of root movement as dictated by the rooted spanning tree transition rule But now we can continue doing this around the cycle until we add the edge before e and delete e Now we have added e to and removed e from T1 and reduced the di erence set U in size by 2 We continue until U 0 at which point we have changed T1 into T2 and thus this MC is irreducible b Other than the self transition there are exactly d rooted spanning trees that can transition to a given rooted spanning tree To see this consider the edge incident on r that must be dropped from the spanning tree when we transition to r as root If it is an edge in the given spanning tree then this corresponds to the rooted tree with the same spanning tree but rooted at a neighbor of r If the edge is not in the given spanning tree then it determines the rooted spanning tree that transitions to the given one since it determines the neighbor v of r that was root and designates that the edge v r is not in this spanning tree but will be in the given one Thus each such edge corresponds to exactly one distinct rooted spanning tree and



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?