coupling of markov chains

《coupling of markov chains》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、CHAPTERELEVEN*CouplingofMarkovChainsInourstudyofdiscretetimeMarkovchainsinChapter7,wefoundthater�l)diclarkochainsconvergetoastationarydistribution.However,wedidnotdeterminehtm(jllicklytheyconverge.whichisimportantinanumberofalgorithmicapplicatilm"."UL'ha"....ampiingusingtheMarkovch

2、ainMonteCarlotechnique.InthisL'haptcr.\cintn)ducetheconceptofcoupling,apowerfulmethodforboundingtherateofcomer�enccutMarkovchains.Wedemonstratethecouplingmethodinseveralappli�,.'atiorb.includingcard-shufflingproblems,randomwalks,andMarkovchainMonteCarll)....arnplin�ofindependentsets

3、andvertexcoloring.11.1.VariationDistanceandMixingTimeConsiderthefollowingmethodforshuffling11cards.Ateachstep.acardi"L'l1lbenindependentlyanduniformlyatrandomandputonthetopofthelkL'k.\.ccanthinkoftheshufflingprocessasaMarkovchain,wherethestateisthecurrentl)rdcrl)fthecards.Youcanchec

4、kthattheMarkovchainisfinite,irreducible.andapcrilxlic.andhenceithasastationarydistribution.Letxbeastateofthechain,andletN(x)bethesetofstatesthatcanreachxinonestep.HereIN(x)l=11.sincethetopcardinxcouldhavebeeninndifferentplaL'L'"inthepreviousstep.Ifn,istheprobabilityassociatedwithstat

5、eyinthe....rationar�distribution,thenforanystatexwehaveJ[_L7Tr.n'EN(x)Theuniformdistributionsatisfiestheseequations,andhencetheuniquestationarydistributionisuniformoverallpossiblepermutations.WeknowthatthestationarydistributionisthelimitingdistributionoftheMarkovchainasthenumberofs

6、tepsgrowstoinfinity.Ifwecouldrunthechain"forever",theninthelimitwewouldobtainastatethatwasuniformlydistributed.Inpractice,271COUPLINGOFMARKOVCHAINS4/10r-----.II3/10IIr-----II1I:2/10-+--:------.III1/10_____.L----------•0234XFigure11.1:Exampleofvariationdistance.Theareasshadedbyupwardd

7、iagonallinescorrespondtovaluesxwhereD1(x)

8、berofsteps.I