Monte Carlo Methods in Statistical Mechanics Found

MonteCarloMethodsinStatisticalMechanics:FoundationsandNewAlgorithmsAlanD.SokalDepartmentofPhysicsNewYorkUniversity4WashingtonPlaceNewYork,NY10003USAE-mail:[e-mail]ummerSchoolon\FunctionalIntegration:BasicsandApplicationsSeptember1996ThesenotesareanupdatedversionoflecturesgivenattheCoursdeTroisiemeCycledelaPhysiqueenSuisseRomande(Lausanne,Switzerland)inJune1989.WethanktheTroisiemeCycledelaPhysiqueenSuisseRomandeandProfessorMichelDrozforkindlygivingpermissiontoreprintthesenotes.NotetotheReaderThefollowingnotesarebasedonmycourse\MonteCarloMethodsinStatisticalMechanics:FoundationsandNewAlgorithmsgivenattheCoursdeTroisiemeCycledelaPhysiqueenSuisseRomande(Lausanne,Switzerland)inJune1989,andonmycourse\Multi-GridMonteCarloforLatticeFieldTheoriesgivenattheWinterCollegeonMultilevelTechniquesinComputationalPhysics(Trieste,Italy)inJanuary{February1991.Thereaderiswarnedthatsomeofthismaterialisout-of-date(thisisparticularlytrueasregardsreportsofnumericalwork).Forlackoftime,Ihavemadenoattempttoupdatethetext,butIhaveaddedfootnotesmarked\NoteAdded1996thatcorrectafewerrorsandgiveadditionalbibliography.MyrsttwolecturesatCargese1996werebasedonthematerialincludedhere.Mythirdlecturedescribedthenewnite-size-scalingextrapolationmethodof[97,98,99,100,101,102,103].1IntroductionThegoaloftheselecturesistogiveanintroductiontocurrentresearchonMonteCarlomethodsinstatisticalmechanicsandquantumeldtheory,withanemphasison:1)theconceptualfoundationsofthemethod,includingthepossibledangersandmisuses,andthecorrectuseofstatisticalerroranalysis;and2)newMonteCarloalgorithmsforproblemsincriticalphenomenaandquantumeldtheory,aimedatreducingoreliminatingthe\criticalslowing-downfoundinconventionalalgorithms.Theselecturesareaimedatamixedaudienceoftheoretical,computationalandmath-ematicalphysicists|someofwhomarecurrentlydoingorwanttodoMonteCarlostudiesthemselves,othersofwhomwanttobeabletoevaluatethereliabilityofpub-lishedMonteCarlowork.Beforeembarkingon9hoursoflecturesonMonteCarlomethods,letmeoerawarning:MonteCarloisanextremelybadmethod;itshouldbeusedonlywhenallalternativemethodsareworse.Whyisthisso?Firstly,allnumericalmethodsarepotentiallydangerous,comparedtoanalyticmethods;therearemorewaystomakemistakes.Secondly,asnumericalmethodsgo,MonteCarloisoneoftheleastecient;itshouldbeusedonlyonthoseintractableproblemsforwhichallothernumericalmethodsareevenlessecient.1Letmebemorepreciseaboutthislatterpoint.VirtuallyallMonteCarlomethodshavethepropertythatthestatisticalerrorbehavesaserror1pcomputationalbudget(orworse);thisisanessentiallyuniversalconsequenceofthecentrallimittheorem.Itmaybepossibletoimprovetheproportionalityconstantinthisrelationbyafactorof106ormore|thisisoneoftheprincipalsubjectsoftheselectures|buttheoverall1=pnbehaviorisinescapable.Thisshouldbecontrastedwithtraditionaldeterministicnumericalmethodswhoserateofconvergenceistypicallysomethinglike1=n4orenore2n.Therefore,MonteCarlomethodsshouldbeusedonlyonthoseextremelydicultproblemsinwhichallalternativenumericalmethodsbehaveevenworsethan1=pn.Consider,forexample,theproblemofnumericalintegrationinddimensions,andletuscompareMonteCarlointegrationwithatraditionaldeterministicmethodsuchasSimpson’srule.Asiswellknown,theerrorinSimpson’srulewithnnodalpointsbehavesasymptoticallyasn4=d(forsmoothintegrands).Inlowdimension(d8)thisismuchbetterthanMonteCarlointegration,butinhighdimension(d8)itismuchworse.SoitisnotsurprisingthatMonteCarloisthemethodofchoiceforperforminghigh-dimensionalintegrals.Itisstillabadmethod:withanerrorproportionalton1=2,itisdiculttoachievemorethan4or5digitsaccuracy.Butnumericalintegrationinhighdimensionisverydicult;thoughMonteCarloisbad,allotherknownmethodsareworse.1Insummary,MonteCarlomethodsshouldbeusedonlywhenneitheranalyticmeth-odsnordeterministicnumericalmethodsareworkable(orecient).OnegeneraldomainofapplicationofMonteCarlomethodswillbe,therefore,tosystemswithmanydegreesoffreedom,farfromtheperturbativeregime.Butsuchsystemsarepreciselytheonesofgreatestinterestinstatisticalmechanicsandquantumeldtheory!Itisappropriatetoclosethisintroductionwithageneralmethodologicalobservation,ablyarticulatedbyWoodandErpenbeck[3]::::these[MonteCarlo]investigationssharesomeofthefeaturesofordinaryexperimentalwork,inthattheyaresusceptibletobothstatisticalandsys-tematicerrors.Withregardtothesematters,webelievethatpapersshouldmeetmuchthesamestandardsasarenormallyrequiredforexperimentalinvestigations.Wehaveinmindtheinclusionofestimatesofstatistical1Thisdiscussionofnumericalintegrationisgrosslyoversimplied.Firstly,therearedeterministicmethodsbetterthanSimpson’srule;andtherearealsosophisticatedMonteCarlomethodswhoseasymptoticbehavior(onsmoothintegrands)behavesasnpwithpstrictlygreaterthan1=2[1,2].Secondly,forallthesealgorithms(exceptstandardMonteCarlo),theasymptoticbehaviorasn!1maybeirrelevantinpractice,becauseitisachievedonlyatridiculouslylargevaluesofn.Forexample,tocarryoutSimpson’srulewitheven10nodesperaxis(averycoarsemesh)requiresn=10d,whichisunachievableford10.2