Improvement of efficiency in generating random $U(

arXiv:hep-lat/9210016v110Oct1992IMPROVEMENTOFEFFICIENCYINGENERATINGRANDOMU(1)VARIABLESWITHBOLTZMANNDISTRIBUTIONTetsuyaHattoriFacultyofEngineering,UtsunomiyaUniversity,Ishii-cho,Utsunomiya,Tochigi321,Japane-mailaddress:[e-mail]Engineering,UtsunomiyaUniversity,Ishii-cho,Utsunomiya,Tochigi321,Japane-mailaddress:[e-mail]1,2008AbstractAmethodforgeneratingrandomU(1)variableswithBoltzmanndis-tributionispresented.Itisbasedontherejectionmethodwithtransfor-mationofvariables.Highefficiencyisachievedforallrangeoftempara-turesorcouplingparameters,whichmakesthepresentmethodespeciallysuitableforparallelandpipelinevectorprocessingmachines.Resultsofcomputerrunsarepresentedtoillustratetheefficiency.Anideatofindsuchalgorithmsisalsopresented,whichmaybeapplicabletootherdis-tributionsofinterestinMonteCarlosimulations.Subjectclassification:65C10,81E25,82A68.Keywords:Randomnumbergeneration,MonteCarlomethod,Spinsystem,Parallelprocessor.1Introduction.MonteCarlonumericalintegrationmethod,orMonteCarlosimulation,hasbeenwidelyusedinthenumericalstudyofquantumfieldtheroieswithlat-ticeformalismandstatisticalmechanicsofspinsystems.InperformingMonteCarlosimulations,onemustgeneratesequencesofrandomnumberswithgivenprobabilitydistributions.Eachrandomnumberisusedto‘update’aspinoragaugevariable.Probabilitydistributionswhichappearinsuchcalculations1haveparameterdependences.Theseparameterscarrytheinformationoftem-peratureandotherthermodynamicquantities,andalsothatoftheneighboringspinstates.Forafixedprobabilitydistributiontherearealgorithms(see,forexample,[5]andreferencestherein)whichmaybeveryefficientingeneratingrandomnumbers.InMonteCarlosimulations,however,wehavefluctuationsintheneighboringspins,whichresultsinchangesoftheparameterswithinasingleprogram.Onefacestheproblemoffindinganalgorithmsuitabletoaclassofdistributionsparametrizedbytheparameters.Theseparametersarechangedoverawiderange,sothatwemustfindamethodwhichmaintainhighefficiencyforallrangeofparameters,especiallyinthelimitwhereaparametertendsto∞andthedistributionbecomessingular.Anotheraspectwhichweconsider,istheefficiencyinparallelorpipelinevectorprocessing.Asfarasweknow,muchofthecurrentlyavailablevectorprocessorsworkefficientlywhenthereareno‘if-branches’intheprogram.Westudyamethodbasedonarejectionmethodcombinedwithachangeofvariables[1],whichisanapproachthatiswidelyused.Inthecaseofrejec-tionmethod,toavoid‘if-branches’wehavetofixthenumberofiterationsoftherejectiontrials.Itisparticularlyimportanttohavehighacceptancerateuniformlyintheparameters.TheaimofthepresentstudyistofindasuitablemethodforgeneratingasequenceofrandomU(1)numberswhichweusetoupdatesiteorlinkvariablesofacanonicalensembleforU(1)latticegaugetheoriesorU(1)spinsytems,fromthepointofviewmentionedabove.AnexampleofaprogramforourproposalisgiveninappendixC.Insection2wesetuptheproblem.Insection3wegiveourstrategyforthesolution,andinsection4wegiveananswertotheproblem.Wepresenttheresultsofourefficiencytestsofthealgorithminsection5.2RandomU(1)variableandrejectionmethod.InthefollowingwecallasequenceofrandomU(1)numbers,arandomU(1)variable:ArandomU(1)variableisasequenceofnumbers(theanglevariables)θ1,θ2,θ3,···,(1)whosedistributionP([θ,θ+dθ])=fa(θ)dθisgivenbythedensityfunctionfa(θ)=Naexp(acos(θ−θ0)),whereNaisanormalizationconstant.Inthepracticalapplications,theparam-eteraisproportionaltotheinversetemperature1/Tortheinversecoupling21/g2,andbothaandtheconstantθ0containtheeffectofinteractionswithothersitesorlinkvariables.Bytheshiftofvariableθ′=θ−θ0ifa0,andθ′=θ−θ0−πifa0,wemayassumewithoutlossofgeneralitythatθ0=0anda≥0.Hencefa(θ)=Naexp(acosθ),−π≤θπ,a0,1Na=Zπ−πexp(acosθ)dθ.(2)Therighthandsideofeq.(2)is(moduloconstant)anintegralrepresentationofmodifiedBesselfunctionI0(a).Oncomputerswestartwithuniformrandomvariablesω1,ω2,ω3,···,(3)withtheprobabilitydistributionP([ω,ω+dω])=dω,0≤ω1.IfweknowanexpressionforafunctionX(ω)expressibleasacomputerprogramofsmalltimeconsumptionsuchthatthesequenceθi=X(ωi),i=1,2,3,···,istherandomU(1)variable(1),thenthereisinprinciplenoproblem.SuchafunctionX(x)isformallygivenbyX(x)=F−1(x);F(t)=P([−π≤θt])=Zt−πfa(θ)dθ.(Hereandinthefollowing,F−1istheinversefunctionofF;F−1(F(x))=x.)Unfortunately,wedonotknowasuitableexpressionofX(x)forrandomU(1)variables.(Notethatwehavetheparameteradependence.)Usuallytherejectionmethodisadoptedtosolvetheproblem.Therejectionmethod,combinedwithtransformationofvariables,isdefinedasfollows.Let˜f(θ)besomeapproximatedensityfunctiontothedensityfunctionfa(θ).Weassumethatthedensityfunctionsarecontinuous.NotethattheyarenormalizedtosatisfyZπ−πf(θ)dθ=1.Supposethatthereisamonotonicfunctionhwhichsatisfiesh(0)=−π,h(1)=π,and˜f(h(x))h′(x)=1,0x1,(4)3whereh′isthederivativeofh,h′=dhdx.(Forthemoment,wesuppresspossibleparameterdependencesof˜fandh.)Defineafunctiongbyg(x)=R(a)fa(h(x))˜f(h(x)),0≤x1,(5)R(a)=min−π≤θπ(˜f(θ)fa(θ)).(6)Letωjandω′jwithj=1,2,3,···,betwosequencesofindependentuniformrandomvariablesasin(3).Defineasubsequence˜ωi=ωji,i=1,2,3,···,ofthesequence{ωj}byse