markov chains and mixing times

《markov chains and mixing times》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、MarkovChainsandMixingTimesDavidA.LevinYuvalPeresElizabethL.WilmerUniversityofOregonE-mailaddress:dlevin@uoregon.eduURL:http://www.uoregon.edu/~dlevinMicrosoftResearch,UniversityofWashingtonandUCBerkeleyE-mailaddress:peres@microsoft.comURL:http://research.mi

2、crosoft.com/~peres/OberlinCollegeE-mailaddress:elizabeth.wilmer@oberlin.eduURL:http://www.oberlin.edu/math/faculty/wilmer.htmlContentsPrefacexiOverviewxiiFortheReaderxiiiFortheInstructorxivFortheExpertxviAcknowledgementsxviiPartI:BasicMethodsandExamples1Cha

3、pter1.IntroductiontoFiniteMarkovChains31.1.FiniteMarkovChains31.2.RandomMappingRepresentation61.3.IrreducibilityandAperiodicity81.4.RandomWalksonGraphs91.5.StationaryDistributions101.6.ReversibilityandTimeReversals141.7.ClassifyingtheStatesofaMarkovChain*16

4、Exercises18Notes20Chapter2.Classical(andUseful)MarkovChains212.1.Gambler’sRuin212.2.CouponCollecting222.3.TheHypercubeandtheEhrenfestUrnModel232.4.TheP´olyaUrnModel252.5.Birth-and-DeathChains262.6.RandomWalksonGroups272.7.RandomWalksonZandReflectionPrinciple

5、s30Exercises34Notes35Chapter3.MarkovChainMonteCarlo:MetropolisandGlauberChains373.1.Introduction373.2.MetropolisChains373.3.GlauberDynamics40Exercises44Notes44Chapter4.IntroductiontoMarkovChainMixing474.1.TotalVariationDistance47vviCONTENTS4.2.CouplingandTo

6、talVariationDistance494.3.TheConvergenceTheorem524.4.StandardizingDistancefromStationarity534.5.MixingTime554.6.MixingandTimeReversal554.7.ErgodicTheorem*58Exercises59Notes60Chapter5.Coupling635.1.Definition635.2.BoundingTotalVariationDistance645.3.Examples6

7、55.4.GrandCouplings70Exercises73Notes74Chapter6.StrongStationaryTimes756.1.Top-to-RandomShuffle756.2.Definitions766.3.AchievingEquilibrium776.4.StrongStationaryTimesandBoundingDistance786.5.Examples806.6.StationaryTimesandCesaroMixingTime*83Exercises84Notes85C

8、hapter7.LowerBoundsonMixingTimes877.1.CountingandDiameterBounds877.2.BottleneckRatio887.3.DistinguishingStatistics927.4.Examples96Exercises98Notes98Chapter8.TheSymmetricGroupandShufflingCards998.1.TheSym