资源描述：
《THE MARKOV CHAIN MONTE CARLO REVOLUTION.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、BULLETIN(NewSeries)OFTHEAMERICANMATHEMATICALSOCIETYVolume46,Number2,April2009,Pages179–205S0273-0979(08)01238-XArticleelectronicallypublishedonNovember20,2008THEMARKOVCHAINMONTECARLOREVOLUTIONPERSIDIACONISAbstract.Theuseofsimulationforhigh-dimensionalintractablecomputa-tions
2、hasrevolutionizedappliedmathematics.Designing,improvingandun-derstandingthenewtoolsleadsto(andleanson)fascinatingmathematics,fromrepresentationtheorythroughmicro-localanalysis.1.IntroductionManybasicscientificproblemsarenowroutinelysolvedbysimulation:afancyrandomwalkisperform
3、edonthesystemofinterest.Averagescomputedfromthewalkgiveusefulanswerstoformerlyintractableproblems.HereisanexampledrawnfromcourseworkofStanfordstudentsMarcCoramandPhilBeineke.Example1(Cryptography).Stanford’sStatisticsDepartmenthasadrop-incon-sultingservice.Oneday,apsychologi
4、stfromthestateprisonsystemshowedupwithacollectionofcodedmessages.Figure1showspartofatypicalexample.Figure1:Theproblemwastodecodethesemessages.Marcguessedthatthecodewasasimplesubstitutioncipher,eachsymbolstandingforaletter,number,punctuationmarkorspace.Thus,thereisanunknownfu
5、nctionff:{codespace}−→{usualalphabet}.OnestandardapproachtodecryptingistousethestatisticsofwrittenEnglishtoguessatprobablechoicesforf,trytheseout,andseeifthedecryptedmessagesmakesense.ReceivedbytheeditorsAugust5,2008.2000MathematicsSubjectClassification.Primary60J20.c2008Ame
6、ricanMathematicalSocietyRevertstopublicdomain28yearsfrompublication179180PERSIDIACONISTogetthestatistics,Marcdownloadedastandardtext(e.g.,WarandPeace)andrecordedthefirst-ordertransitions:theproportionofconsecutivetextsymbolsfromxtoy.ThisgivesamatrixM(x,y)oftransitions.Onemayt
7、henassociateaplausibilitytofviaPl(f)=M(f(si),f(si+1)),iwheresirunsoverconsecutivesymbolsinthecodedmessage.FunctionsfwhichhavehighvaluesofPl(f)aregoodcandidatesfordecryption.Maximizingf’sweresearchedforbyrunningthefollowingMarkovchainMonteCarloalgorithm:•Startwithapreliminar
8、yguess,sayf.•ComputePl(f).•Changetof∗bymakingarandomtranspositionofthevalue
