[math.PR]26Jan2005 Asymptoticanalysisofaparticlesystemwithmean-fieldinteraction AnatoliManita∗, FacultyofMathematicsandMechanics,MoscowStateUniversity,119992,Moscow,Russia. E-mail:manita@mech.math.msu.su VadimShcherbakov†, CWI,Postbus94079,1090GB,Amsterdam,TheNetherlandsE-mail:
V.Shcherbakov@cwi.nl Abstract WestudyasystemofNinteractingparticlesonZ.Thestochasticdynamicsconsistsofponents:afreemotionofeachparticle(independentrandomwalks)andapair-wiseinteractionbetweenparticles.Theinteractionbelongstotheclassofmean-fieldinteractionsandmodelsarollbacksynchronizationinworksofprocessorsforadistributedsimulation.FirstofallwestudyanempiricalmeasuregeneratedbytheparticleconfigurationonR.Weprovethatifspace,timeandaparameteroftheinteractionareappropriatelyscaled(hydrodynamicalscale),thentheempiricalmeasureconvergesweaklytoadeterministiclimitasNgoestoinfinity.Thelimitprocessisdefinedasaweaksolutionofsomepartialdifferentialequation.Wealsostudythelongtimeevolutionoftheparticlesystemwithfixednumberofparticles.TheMarkovchainformedbyindividualpositionsoftheparticlesisnotergodic.NeverthelessitispossibletointroducerelativecoordinatesandprovethatthenewMarkovchainisergodicwhilethesystemasawholemoveswithanasymptoticallyconstantmeanspeedwhichdiffersfromthemeandriftofthefreeparticlemotion. MSC2000:60K35,60J27,60F99. 1Introduction Westudyaninteractingparticlesystemwhichmodelsasetofprocessorsperformingparallelsimulations.Thesystemcanbedescribedasfollows.ConsiderN≥2particlesmovinginZ.Letxi(t)bethepositionattimetofthei−thparticle,1≤i≤
N.Eachparticlehasthreeclocks. ∗SupportedbyRussianFoundationofBasicResearch(RFBRgrant02-01-00945).†SupportedbyRussianFoundationofBasicResearch(RFBRgrant01-01-00275).OnleavefromLaboratoryofLargeRandomSystems,FacultyofMathematicsandMechanics,MoscowStateUniversity,119992,Moscow,Russia.
1 2
A.Manita,
V.Shcherbakov Thefirst,thesecondandthethirdclock,attachedtothei−thparticle,ringatthemomentsoftime givenbyamutuallyindependentPoissonprocessesΠi,α,Πi,βandΠi,µNwithintensitiesα,βandµNcorrespondingly.ThesetriplesofPoissonprocessesfordifferentindexesarealsoindependent. Consideraparticlewithindexi.Ifthefirstattachedclockrings,thentheparticlejumpstothe nearestrightsite:xi→xi+1,ifthesecondattachedclockrings,thentheparticlejumpstothe nearestleftsite:xi→xi−
1.Atmomentswhenthethirdattachedclockringsaparticlewithindex jischosenwithprobability1/Nandifxi>xj,thenthei−thparticleisrelocated:xi→xj.Itis supposedthatallthesechangesurimmediately. Thetypeoftheinteractionbetweentheparticlesismotivatedbystudyingofprobabilisticmod- elsinthetheoryofparallelsimulationsputerscience([16],[22,23]and[6,11]).The mainpeculiarityofthemodelsisthatagroupofprocessorsperformingalarge-scalesimulation isconsideredandeachprocessordoesaspecificpartofthetask.Theprocessorssharedatado- ingsimulationsthereforetheiractivitymustbesynchronized.Inpractice,thissynchronization isachievedbyapplyingaso-calledrollbackprocedurewhichisbasedonamassivemessageex- changebetweendifferentprocessors(see[
2,Sect.1.4andCh.8]).Onesaysthatxi(t)isalocal timeofthei-thprocessorwhiletisareal(absolute)time.Ifweinterpretthevariablexi(t)as anamountofjobdonebytheprocessoritillthetimemomentt,thentheinteractiondescribed aboveimitatesthissynchronizationprocedure.Notethatfromapointofviewofgeneralstochastic particlesystemstheinteractionbetweentheparticlesisessentiallynon-local. Weareinterestedintheanalysisofasymptoticbehaviourofthisparticlesystem.Firstofall weconsiderthesituationasthenumberofparticlesgoestoinfinity.ForeveryfiniteNandtwe candefineanempiricalmeasuregeneratedbytheparticleconfiguration.Itisapointmeasurewith atomsatintegerpoints.Anatomatapointkequalstoaproportionofparticleswithcoordinate kattimet.Itisconvenientinourcasetoconsideranempiricaltailfunctioncorrespondingto 1N themeasure. Itmeansthatweconsiderξx,N(t)=
N 1(xi(t)≥x)theproportionofparticles i=
1 havingcoordinatesnotlessthanx∈
R.TheproblemistofindanappropriatetimescaletN andasequenceofinteractionparametersµNtoobtainanon-triviallimitdynamicsoftheprocess ξ
N,[xN](tN)asN→∞.Thecasesα=βandα=βrequiredifferentscalingoftimeandthe interactionconstantµ
N.Weprovethatthereexistnon-triviallimitdeterministicprocessesinboth casesasNgoestoinfinityifwerescaletimeandtheinteractionconstantastN=tN,µN=µ/NinthefirstcaseandastN=tN2,µN=µ/N2inthesecondcaserespectively.Theprocesses aredefinedasweaksolutionsofsomepartialdifferentialequations(PDE).Itshouldbenotedthat thePDErelatingtothezerodriftsituationisafamousKolmogorov–Petrowski–Piscounov-equation (KPP-equation,[9]).Thisresultwasannouncedin[19]. Anotherissueweaddressinthepaperisstudyingofthelongtimeevolutionoftheparticle systemwithfixednumberofparticles.ItiseasytoseethattheMarkovchainx(t)={xi(t),i= 1,...,N},t≥0,isnotergodic.Neverthelesstheparticlesystempossessessomerelativestabil- 26/01/2005 Asymptoticanalysisofastochasticmodelforputations
3 ity.Weintroducenewcoordinatesyi(t)=xi(t)−minjxj(t),i=1,...,N,andprovethatthecountableMarkovchainy(t)={yi(t),i=1,...,N},t≥0,isergodicandconvergesexponentiallyfasttoitsstationarydistribution.Thereforethesystemofstochasticinteractingparticlespossessessomerelativestability.Weshowalsothatthecenterofmassofthesystemmoveswithanasymptoticallyconstantspeed.Itappearsthatduetotheinteractionbetweentheparticlesthisspeeddiffersfromthemeandriftofthefreeparticlemotion. Itshouldbenotedthatthechoiceoftheinteractionmayvarydependingonasituation.Variousmodificationsofthemodelcanbeconsideredandsimilarresultscanbeobtainedusingthesamemethods.Wehavechosenthedescribedmodeljustforthesakeofconcreteness. Probabilisticmodelsforputationconsideredbeforebyotherauthors.Thepaper[16]dealswithamodelconsistingoftwointeractingprocessors(N=2).Itcontainsarigorousstudyofthelong-timebehaviorofthesystemandformulaeforsomeperformancecharacteristics.Unfortunately,therearenottoomanymathematicalresultsaboutmulti-processormodels([12,13,14,22,23]).Usuallyponentsofthesepapershaveaformofpreparatoryconsiderationsbeforesomelargenumericalsimulation.Thepaper[6]isofspecialinterestbecauseitrigorouslystudiesabehaviorofsomemodelofputationwithNprocessorunitsinthelimitN→∞.Astochasticdynamicsof[6]isdifferentfromthedynamicsstudiedinthepresentpaperandmainresultsof[6]concernaso-calledthermodynamicallimit.Theauthorsprovethatinthelimittheevolutionofthesystemcanbedescribedbysomeintegro-differentialequation.Inthepresentstudyweproposeamodelwhichdynamicsiseasyfromthepointofviewofnumericalsimulationsand,atthesametime,providesuswithanewprobabilisticinterpretationofsomeimportantPDEsincludingtheclassicalKPP-equation. Thepaperanisedasfollows.Weformallydefinetheparticlesystem,introducesomenotationandformulatethemainresultsinSection2.Sections3and4containtheproofsofthemainresults.InSection5wediscusssolutionsofthelimitingequations. Acknowledgments.WearethankfultoDr.T.Voznesenskaya(FacultyofComputationalMathematicsandics,MoscowUniversity)whofirstintroducedustostochasticalgorithmsforputations.TheauthorswouldliketothankProf.V.Bogachev(FacultyofMechanicsandMathematics,MoscowUniversity)forthehelpfuldiscussionsonconvergenceofmeasuresonologicalvectorspacesandforthesuggestedreferences.WearealsogratefultoProf.V.Malyshevforhiswarmencouragementandmentsonthepresentmanuscript.
4 A.Manita,
V.Shcherbakov 2Themodelandmainresults Formally,theprocessx(t)={xi(t),i=1,...,N},describingpositionsoftheparticles,isacontinuoustimecountableMarkovchaintakingvaluesinZNandhavingthefollowinggenerator
N GNg(x)= αgx+ei(N)−g(x)+βgx−e(iN)−g(x)+ i=
1 N(N) µ
N + gx−ei(xi−xj)−g(x)I{xi>xj}
N,
(1) i=1j=i wherex=(x1,...,xN)∈ZN,g:ZN→Risaboundedfunction,e(iN)isaN-dimensional vectorwithallponentsexcepti−thwhichequalsto1,I{xi>xj}isanindicatoroftheset {xi>xj}. Define 1N ξN,k(t)=
N I{xi(t)≥k},k∈
Z.
(2) i=
1 TheprocessξN(t)={ξN,k(t),k∈Z}isaMarkovonewithastatespaceHNthesetofallnon- negativeandnonincreasingsequencesz={zk,k∈Z}suchthatzk∈{l/N,l=0,1,...,N}for anyk∈Zand limzk=
1, k→−∞ limzk=
0. k→+∞ ThegeneratoroftheprocessξN(t)isgivenbythefollowingformula LNf(z)=N((f(z+ek/N)−f(z))α(zk−1−zk)+(f(z−ek/N)−f(z))β(zk−zk+1)) k
(3) +NµN(f(z−(el+1+...+ek)/N)−f(z))(zk−zk+1)(zl−zl+1), lN,[Nx](t),x∈
R.TheprocessζN(t)takesvaluesinH=H(R)thesetofallnon-negativerightcontinuouswithleftlimitsnonincreasingfunctionshavingthefollowinglimits limψ(x)=1,limψ(x)=
0. x→−∞ x→∞ 26/01/2005 Asymptoticanalysisofastochasticmodelforputations
5 DenotebyS(R)theSchwartzspaceofinfinitelydifferentiablefunctionssuchthatforallm,n∈Z+ fm,n=sup|xmf(n)(x)|<∞. x∈
R RecallthatS(R)equippedwithaologygivenbyseminorms·m,nisaFrechetspace([18]). Defineforeveryh∈Hafunctional (h,f)=h(x)f(x)dx,f∈S(R),
R ontheSchwartzspaceS(R).Thefollowingboundyieldsthatforeachh∈H(h,·)isacontinuouslinearfunctionalonS(R) |(h,f)|≤ |f(x)|1+x2dx≤π(f∞+x2f∞)≡π(f0,0+x2f2,0),1+x2
R where·∞isthesupremumnorm.ThusthesetoffunctionsH(R)isnaturallyembeddedintothespaceofallcontinuouslinearfunctionalsonS(R),namelyintothespaceS′(R)oftempereddistributions.WewillinterpretζN(t)asastochasticprocesstakingitsvaluesinthespaceS′(R). TherearetworeasonsforembeddingH(R)intoS′(R)andconsideringtheS′(R)-valuedprocesses.ThefirstreasonisthatduetosomeologicalpropertiesofS′(R)wecanusein Section3manypowerfulresultsfromthetheoryofweakconvergenceofprobabilitydistributionsologicalvectorfields.And,secondly,thechoiceofS′(R)asastatespaceisconvenientfrom thepointofviewofpossiblefuturestudyofstochasticfluctuationfieldsaroundthedeterministic limitsobtainedinourmaintheorem2.1.Inthesequelwemainlydealwiththeology(s.t.)onS′(R)(seeSectionA.1). FromnowwefixsomeT>0andconsiderζNasarandomelementinaSkorokhodspaceD([
0,T],S′(R))ofallmappingsof[
0,T]to(S′(R),s.t.)thatarerightcontinuousandhavelefthandlimitsintheologyonS′(R).Notethat(S′(R),s.t.)isnotaologicalspacethereforeitisnotevidenthowtodefinetheologyonthespaceD([
0,T],S′(R)). Todothiswefollow[15]andrefertoSectionA.1.Nowweareabletoconsiderprobabilitydistributionsoftheprocesses(ζN(tNa),t∈[
0,T]), a=1,2,asprobabilitymeasuresonameasurablespaceD([
0,T],S′(R)),BD([
0,T],S′(R))whereBD([
0,T],S′(R))isacorrespondingBorelσ-algebra.Itwasprovedin[7]thatBD([
0,T],S′(R))=CD([
0,T],S′(R)),whereCD([
0,T],S′(R))isaσ-algebraofcylindricalsubsets. ConsidertwofollowingCauchyproblems ut(t,x)=−λux(t,x)+µ(u2(t,x)−u(t,x)),
(4) u(0,x)=ψ(x)
6 A.Manita,
V.Shcherbakov and ut(t,x)=γuxx(t,x)+µ(u2(t,x)−u(t,x)),
(5) u(0,x)=ψ(x) whereut,uxanduxxarefirstandsecondderivativesofuwithrespecttotandx.Noticethattheequation(5)isaparticularcaseofthefamousKolmogorov–Petrowski–Piscounov-equation(KPP- equation,[9]).Wewilldealwithweaksolutionsoftheequations(4)and(5)inthesenseof Definition2.1.FixT>0anddenotebyC0∞,T=C0∞([
0,T]×R)thespaceofinfinitelydifferentiablefunctions withfinitesupportandequaltozerofort=
T. Definition2.1(i)Theboundedmeasurablefunctionu(t,x)iscalledaweak(orgeneralized)so- lutionoftheCauchyproblem(4)intheregion[
0,T]×R,ifthefollowingintegralequationholdsforanyfunctionf∈C0∞,
T T u(t,x)(ft(t,x)+λfx(t,x))+µu(t,x)(1−u(t,x))f(t,x))dxdt 0R +u(0,x)f(0,x)dx=
0 R (ii)Theboundedmeasurablefunctionu(t,x)iscalledaweak(orgeneralized)solutionofthe Cauchyproblem(5)intheregion[
0,T]×R,ifthefollowingintegralequationholdsforanyfunctionf∈C0∞,
T T u(t,x)(ft(t,x)+γfxx(t,x))+µu(t,x)(1−u(t,x))f(t,x))dxdt 0R +u(0,x)f(0,x)dx=
0 R InSubsection3.5wewillshowthatthebothofCauchyproblems(4)and(5)haveuniqueweaksolutionsinthesenseofDefinition2.1.Herewewantjusttomentionthatthisproblemisnottrivial.Indeed,theequation(4)isanexampleofaquasilinearfirstorderpartialdifferentialequation.Itisknownthatinageneralcasesuchtypeofequationsmighthavemorethanoneweaksolutionanditisonlypossibletoguaranteeuniquenessofthesolutionwhichsatisfiestotheso-calledentropy 26/01/2005 Asymptoticanalysisofastochasticmodelforputations
7 condition.ThemostgeneralformofthisconditionwasintroducedbyKruzhkovin[10],wherehealsoprovedhisfamousuniquenesstheorem.Fortunately,inourparticularcaseoftheequation(4)thesituationisquitesimpleduetosimplicityofcharacteristics,theyaregivenbythestraightlinesx(t)=λt+C,donotintersectwitheachotheranddonotproducetheshocks.Detaileddiscussionsoftheproblemofuniquenessforequations(4)and(5)arepresentedinSubsection3.5. Thefirsttheoremweareformulatingdescribestheevolutionofthesystematthehydrodynamicalscale. Theorem2.1AssumethataninitialparticleconfigurationξN
(0)={ξN,k
(0),k∈Z}issuchthatforanyfunctionf∈S(R)
1 limN→∞
N ξN,k(0)f(k/N)=ψ(x)f(x)dx,
(6) k
R whereψ∈H(R). (i)Ifα−β=λ=0andµN=µ/N,thenthesequence{Q(NT,)λ}∞N=2ofprobabilitydistributionsof random processes {ζN(tN), t ∈ [
0 ,
T ]} ∞N=
2 converges weakly as
N → ∞ to the probability measureQ(λT)onD([
0,T],S′(R))supportedbyatrajectoryu(t,x),whichisauniqueweak solutionoftheequation(4)withtheinitialconditionu(0,x)=ψ(x)andasafunctionofx u(t,·)∈H(R),foranyt≥
0. (ii)Ifα=β=γ>
0,µN=µ/N2,thenthesequence{QN(
T,)γ}∞N=2ofprobabilitydistributionsof random processes {ζN(tN2), t ∈ [
0 ,
T ]} ∞N=
2 converges weakly as
N → ∞ to the probability measureQ(γT)onD([
0,T],S′(R))supportedbyatrajectoryu(t,x),whichisauniqueweak solutionoftheequation(5)withtheinitialconditionu(0,x)=ψ(x)andasafunctionofx u(t,·)∈H(R),foranyt≥
0. 2.2Longtimebehavioroftheparticlesystemwiththefixednumberofparticles Thenumberofparticlesisfixedinthissection.Considerthefollowingstochasticprocessy(t)=(y1(t),...,yN(t)),where yi(t)=xi(t)−minxj(t).j Notethatxk−xl=yk−ylforanypairk,l.Itiseasytoseethaty(t)isacontinuoustimeMarkovchainonthestatespace Γ=Γk⊂ZN+, k
8 A.Manita,
V.Shcherbakov whereΓk:={(z1,...,zk−1,0,zk+1,...,zN):zj∈Z+}.Theorem2.2TheMarkovchain(y(t),t≥0)isergodicandconvergesexponentiallyfasttoitsstationarydistribution |P(y(t)=y)−π(y)|≤C1exp(−C2t) y∈Γ uniformlyininitialdistributionsofy
(0). 3ProofofTheorem2.1 3.1Planoftheproof Theproofoftheconvergenceusesthenextwell-knowngeneralidea(see,forexample,[21,§5]).Let{an}beasequenceinsomeologicalspaceandassumethat{an}satisfiestothefollowingtwoproperties:(a)foranysubsequenceof{an}thereisaconvergingsubsequence(thispropertyiscalledapactness);(b){an}containsatmostonelimitpoint.Thenthesequence{an}hasalimit. Inoursituationtheroleof{an}isplayedbythesequences{QN(
T,)λ}∞N=2and{Q(NT,)γ}∞N=
2.Ourproofconsistsofthefollowingsteps. Step1.WefixanarbitraryT>0andprovethatthesequencesofprobabilitymeasures{Q(NT,λ)}∞N=2and{QN(
T,)γ}∞N=2aretight.WeusetheMitomatheorem([15])andapplymartingaletechniqueswidelyusedinthetheoryofhydrodynamicallimitsofinteractingparticlesystems([4,8]). ItisimportanttonotethatifologicalspaceVisnotmetrisablethen,generallyspeaking,thetightnessofafamilyofdistributionsonVdoesnotimplyapactness(see,forexample,[
3,V.2,§8.6]).So,ingeneral,theaboveproperty(a)doesnotfollowdirectlyfromthestep1.ButinourconcretecaseV=D([
0,T],S′(R))wecanproceedasfollows.Itwasshownin[7]thatpactsubsetofD([
0,T],S′(R))ismetrisable.Duetothispropertywecanapplythetheoremfrom[21,Th.2,§5]whichstatesthat(underassumptionofmetrisabilitypactsubsets)thetightnessofafamilyofmeasuresimpliesitspactness.Allthisjustifiesthenextstep. Step2.Weshowthatameasurethatisalimitofsomesubsequenceofthesequence{QN(
T,)λ}∞N=2(or{Q(NT,)γ}∞N=2)issupportedbytheweaksolutionsofthepartialdifferentialequation
(4)(or,correspondingly,
(5)).Thenwenotethateachoftheequations(4)and(5)hasauniqueweaksolution(Subsection3.5).Thisgivestheaboveproperty(b). 26/01/2005 Asymptoticanalysisofastochasticmodelforputations
9 3.2Technicallemmas Westartwithsomeboundswhichwillbeusedthroughouttheproof.Denote1 Rf(z)=Nf(k/N)zk,k forz∈HNandf∈S(R). Lemma3.1(i)Ifα=βandµN=µ/N,thenforanyz∈HN
C |LNRf(z)|≤
N,
(7) and NLNR2(z)−2Rf(z)LNRf(z)=O1.
(8) f
N (ii)Ifα=βandµN=µ/N2,thenforanyz∈HN
C |LNRf(z)|≤N2,
(9) and N2LNR2(z)−2Rf(z)LNRf(z)=O1. (10) f N2 InbothcasesC=C(f,α,β,µ). ProofofLemma3.1.Wewillprovethebounds(7)and
(8),theotheronescanbeprovedsimilarly.Westartwiththebound
(7).Usingtheequations f(k/N)Rf(z+ek/N)−Rf(z)=N2, f(k/N)Rf(z−ek/N)−Rf(z)=−N2wegetthatforeveryz∈HN 1LNRf(z)=Nzk(βf((k−1)/N)−(α+β)f(k/N)+αf((k+1)/N) k µ−N2f(k/N)zk(1−zk). k 10
A.Manita,
V.Shcherbakov Foranyfunctionf∈S(R)consideritsupperDarbouxsum UN+(f)=N1 maxf(y). y∈[k/N,(k+1)/N] k∈
Z (11) SinceUN+(f)→f(x)dxasN→∞,thesequenceUN+(f)∞N=1isboundedinNforanyfixedf.Wehaveuniformlyinz∈HN 1|LNRf(z)|≤
N |α(f((k+1)/N)−f(k/N))+β(f(k/N)−f((k−1)/N))| k +µ
N 1|f(k/N)|Nk ≤N1|α−β|UN+(|fx|)+µUN+(|f|), wherefx=df(x)/dx.Sothebound(7)isproved.Letusprovethebound
(8).NotethatLN=L(N0)+L(N1),where L(N0)f(z)=
N (f(z+ek/N)−f(z))α(zk−1−zk)+ k N(f(z−ek/N)−f(z))β(zk−zk+1) k andL(N1)f(z)=µ(f(z−(el+1+...+ek)/N)−f(z))(zk−zk+1)(zl−zl+1). lN αf(k/N)(zk−1−zk)+N3 k f2(k/N)(zk−1−zk) k β−2Rf(z)
N βf(k/N)(zk−zk+1)+N3 k f2(k/N)(zk−zk+1) k =2Rf(z)L(N0)Rf(z)+ON12.(12) Directcalculationgivesthatforanyfunctiongk,j(z)=zkzj,k(1)R2(z)=−2Rf(z)µf(k/N)zk(1−zk) Nf N2 k +2µf(k/N)f(j/N)zj(1−zk)+µf2(k/N)zk(1−zk) N4 N4 kT,λ)theprobabilitydistributiononthepathspaceD([
0,T],HN)correspondingtotheprocessξN(t)andbyEN(
T,λ)theexpectationwithrespecttothismeasure. 12
A.Manita,
V.Shcherbakov Theorem4.1in[15](seealsoSectionA.2)yieldsthattightnessofthesequenceof{QN(
T,)λ}∞N=
2 willbeprovedifweprovethesameforasequenceofdistributionsofone-dimensionalprojection {(ζN(tN),f),t ∈ [
0 ,
T ]} ∞N=
2 for every f ∈ S(R). So fix f ∈ S(R) and consider the sequence of distributions
oftheprocesses(ζN(tN),f),t∈[
0,T].Notethattheprobabilitydistributionofa process(ζN(tN),f)isaprobabilitymeasureonD([
0,T],R)theSkorokhodspaceofreal-valued functions. BydefinitionoftheprocessζN(tN)wehavethat (k+1)/N (ζN(tN),f)=ξN,k(tN) k k/N f(x)dx. Itiseasytoseethat (ζN(tN),f)=Rf(ξN(tN))+φN(t), wheretherandomprocessφN(t)isbounded|φN(t)|N.Thereforeitsufficestoprovetightnessofthesequenceofdistributionsofrandomprocesses {Rf(ξN(tN)), t ∈ [
0,
T ]} ∞N=
2 . Introducetworandomprocesses t Wf,N(t)=Rf(ξN(tN))−Rf(ξN
(0))−NLNRf(ξN(sN))ds, (16)
0 andt Vf,N(t)=(Wf,N(t))2−Zf,N(s)ds,
0 where Zf,N(s)=NLNRf2(ξN(sN))−2Rf(ξN(sN))LNRf(ξN(sN)). (17) Itiswellknown(Theorem2.6.3in[4]orLemmaA1.5.1in[8])thattheprocessesWf,N(t)andVf,N(t)aremartingales. Thebound(7)yieldsthat τ+θ NLNRf(ξN(sN))ds≤Cθ τ (a.s.) foranytimemomentτ.Thusthesequenceofprobabilitydistributionsofrandomprocesses {
N t0 LNRf(ξN(sN))ds, t ∈ [
0,
T ]} ∞N=
2 is tight by Theorems A.2 and A.3 from Appendix. 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 13 Thebound(8)yieldsthat τ+θ  EN(
T,λ)(Wf,N(τ+θ)−Wf,N(τ))2=EN(
T,λ)Zf,N(s)ds≤CNθ.(18) τ foranypingtimeτ≥0sinceVf,N(s)ismartingale.UsingthisestimateandChebyshev inequalityweobtainthatthesequenceofprobabilitydistributionsofmartingales{Wf,N(t),t∈ [
0 ,
T ]} ∞N=
2 is also tight by Theorem A.3. Thusthesequenceofprobabilitydistributionsofthe processes {Rf(ξN(tN)), t ∈ [
0,
T ]} ∞N=
2 is tight by the equation (16) and the assumption
(6) and, hence,thesequenceofprobabilitymeasures{Q(NT,)λ}∞N=2istightbyTheorem4.1in[15]. 3.4Characterizationofalimitpoint Wearegoingtoshownowthatthereisauniquelimitpointofthesequence{Q(NT,)λ}∞N=2andthislimitpointissupportedbytrajectorieswhichareweaksolutionsofthepartialdifferentialequation(4)inthesenseofDefinition2.1. Letf(s,x)∈C0∞,Tanddenote 1Rf(t,ξN(tN))=NξN,k(tN)f(t,k/N), k Defineasbeforetworandomprocesses t Wf′,N(t)=Rf(t,ξN(tN))−Rf(
0,ξN
(0))−(∂/∂s+NLN)Rf(s,ξN(sN))ds,
0 andwhere t Vf′,N(t)=(Wf′,N(t))2−Zf′,N(s)ds,
0 Zf′,N(s)=NLNRf2(s,ξN(sN))−2Rf(s,ξN(sN))LNRf(s,ξN(sN)). 14
A.Manita,
V.Shcherbakov ByLemmaA1.5.1in[8]theprocessesWf′,N(t)andVf′,N(t)aremartingales.Itiseasytoseethat t Wf′,N(t)=(ζ(tN),f)−(ζN(sN),fs+λfx+µf)ds−(ζ
(0),f) 0t +µRf(s,ξ2(sN))ds+O1.(19)N
0 Wearegoingtoapproximatethenonlineartermin(19)bysomequantitiesmakingsenseinthespaceofgeneralisedfunctionssincewetreattheprocessesdistributionsasprobabilitymeasuresonaspaceD([
0,T],S′(R)).Letκ∈C0∞(R)beanon-negativefunctionsuchthatRκ(y)dy=
1.Denoteκε(y)=κ(y/ε)/ε,for0<ε≤1andlet(κε∗ϕ(s))(x)=Rκε(x−y)ϕ(y,s)dybeaconvolutionofageneralisedfunctionϕ(s,·)withthetestfunctionκε(y). Lemma3.2Thefollowinguniformestimateholds Rf(s,ξ2(sN))−((κε∗ζN(sN))2,f)≤F1(ε)+F2(εN) wherethefunctionsF1andF2donotdependonξandsand limF1(ε)=limF2(r)=
0. ε↓
0 r→+∞ Proof.Fordefinitenessweassumethatκ(x)=0forx∈(−∞,−1−δ′)∪(1+δ′,∞)forsomepositiveδ′.Itiseasytoseethatifx∈[k/N,(k+1)/N)forsomek,then (j+1)/N (κε∗ζN(sN))(x)= j =1N ξN,j(sN) j/N κε(x−y)dy κε((k−j)/N)ξN,j(sN)+g1(
N,ε,x,ξN(sN)) j wherethefunctiong1(
N,ε,x,ξN(sN))canbeboundedasfollows (j+1)/N k−j |g1(
N,ε,x,s,ξN(sN))|≤ κε(x−y)−κεNdy jj/N ≤12max 1κ′w·
1 Nmw∈[(m−1)/N,m/N]ε
2 ε
N =
2 max |κ′(v)|=2UN+ε(|κ′|) (Nε)2mv∈[(m−1)/(Nε),m/(Nε)]Nε 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 15 (seethe(11)forthenotationU+).NotethatifεisfixedthenUN+ε(|κ′|)=O(1)asN→∞.Thisrepresentationimpliesthat
2 ((κε∗ζN(sN))2,f)=1f(k/N)1κε((k−j)/N)ξN,j(sN)+O1NkNjε
N Therefore|Rf(s,ξ2(sN))−((κε∗ζN(sN))2,f)|≤Jf,s(δ′,ε,N)+K(ε,N)+O1,ε
N whereJf,s(δ′,ε,N)=2N
1 |f(s,k/N)|
N κε((k−j)/N)|ξN,k(sN)−ξN,j(sN)| k j:|j−k|<(1+δ′)ε
N and
1 m K(ε,N)=Const·NκεN−
1. m Evidently,K(ε,N)=Const·1κm−1and,hence,K(ε,N)tendsto0inthelimitNεmNε "εisfixed,N→∞".SowecanincludeK(ε,N)intoF2(εN).ConsidernowthetermJf,s(δ′,ε,N).Usingmonotonicityoftrajectoriesweobtainthatforany jsuchthat|j−k|<(1+δ′)ε
N |ξN,k(sN)−ξN,j(sN)|≤ξN,k−[(1+δ′)εN](sN)−ξN,k+[(1+δ′)εN](sN). ThuswehavethatJf,s(δ′,ε,N)≤2N |f(s,k/N)|(ξN,k−[(1+δ′)εN](sN)−ξN,k+[(1+δ′)εN](sN)). k Integratingbypartswegetthefollowingbound Jf,s(δ′,ε,N)≤2(|f(s,(k+[(1+δ′)εN])/N)|−|f(s,(k−[(1+δ′)εN])/N)|)ξN,k(sN)Nk ≤2|f(s,(k+[(1+δ′)εN])/N)−f(s,(k−[(1+δ′)εN])/N)|Nk ≤Const·MD·(1+δ′)ε, whereM=maxx,s|fx(s,x)|,Disadiameterofsuppfx(s,x).Notethatthelastinequalityisuniformintrajectories.Lemma3.2isproved. 16
A.Manita,
V.Shcherbakov Lemma3.3Foreveryδ>
0 
T  limsuplimsupPλ(
T,N)ε→0N→∞
0 Rf(s,ξ2(sN))−((κε∗ζN(sN))2,f)ds>δ=
0. TheproofofthislemmaisomittedbecauseitisadirectconsequenceofLemma3.2.Itiseasytoseethatforanyf∈C0∞,TamapFf,
T,ε(ϕ):D([
0,T],S′)→R+definedby
T Ff,
T,ε(ϕ)=ϕ(s),fs+λfx+µf)−µ((κε∗ϕ(s))2,f)ds+(ϕ
(0),f) 0 iscontinuous,thereforeforanyδ>0theset{ϕ∈D([
0,T],S′):Ff,
T,ε(ϕ)>δ}isopenandhence limsupQ(λT)(ϕ:Ff,
T,ε(ϕ)>δ)≤limsupliminfQ(NT,)λ(ϕ:Ff,
T,ε(ϕ)>δ), ε→
0 ε→0N→∞ whereQ(λT)isalimitpointofthesequence{Q(NT,)λ}∞N=
2.Obviouslythat QN(
T,)λ(ϕ:Ff,
T,ε(ϕ)>δ)≤PN(
T,λ)sup|Wf′,N(t)|>δ/2t≤TT+PN(
T,λ)(Rf(s,ξ2(sN))−((κε∗ζN(sN))2,f)ds0 (20)>δ/2. Itiseasytoseethatthebound(8)obtainedinLemma3.1fortheprocessZf,N(s)isalsovalidfortheprocessZf′,N(s),thereforeforanyt t  E(T)(W′(t))2=E(T) Z′(s)ds≤Ct,
N,λf,
N N,λ f,
N 
N 0 sinceVf′,N(t)isamartingale.Kolmogorovinequalityimpliesthatforanyδ>
0 PN(
T,λ) sup|Wf′,N(t)|≥δ t≤
T 
T  ≤δ−2E(T)(W′(T))2=δ−2E(T) Z′(s)ds≤CT.(21)
N,λf,
N N,λ f,
N Nδ
2 0 Thesecondtermin(20)vanishestozerobyLemma3.3asN→∞andε→
0.Thereforeforany f∈C0∞,Tandδ>
0 limsupQλ(T)(ϕ:Ff,
T,ε(ϕ)>δ)=
0. (22) ε→
0 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 17 LetusprovethatwecanreplacetheconvolutioninFf,
T,εbyitslimitwhichiswelldefinedwithrespecttothemeasureQλ(T).FirstofallwenotethatforanyC>0BC(R)thesetofmeasurablefunctionshsuchthath∞≤CisaclosedsubsetofS′(R)inbothstrongandology.Indeed,considerasequenceoffunctionsgn∈BC,n≥1andassumethissequenceconvergesinS′tosometempereddistributionG∈S′.Wearegoingtoshowthatthisgeneralizedfunctionis determinatedbysomemeasurablefunctionboundedbythesameconstantC.Itiseasytoseethat foreveryn≥
1 gn(x)f(x)dx≤CfL1,f∈
S, R where·L1isanorminL1thespaceofallintegrablefunctions.SothelimitlinearfunctionalGonSisalsocontinuousinL1-norm |G(f)|≤CfL1,f∈
S. ThespaceSisalinearsubspaceofL1thereforebyHahn-BanachTheorem(TheoremIII-
5,[18])thelinearfunctionalGcanbeextendedtoacontinuouslinearfunctionalG˜onL1withthesamenormandsuchthatG˜|S=
G.UsingthetheoremaboutthegeneralformofacontinuouslinearfunctionalonL1([18])weobtainthat G(f)=g(x)f(x)dx,f∈L1,
R wheregisameasurableboundedfunction.Obviouslythatg∞≤
C.ObviouslythatforanyN≥2andfixedt∈[
0,T]wehavethatQ(NT,)λ(ϕ(t,·)∈B1)=1,where ϕ(t,·)=ϕ(t)isacoordinatevariableonD([
0,T],S′).Thereforeifsomesubsequence{QN(T′),λ}of {Q(NT,λ)}∞N=2convergesweaklytoalimitpointQ(λT),thenforanyfixedt∈[
0,T] Q(λT)(ϕ(t)∈B1)≥limsupQ(NT′),λ(ϕ(t)∈B1)=
1, (23) N′→∞ sinceB1isclosed.NextlemmagivesanimportantpropertyoftheconvolutiononthesetofboundedfunctionsL∞. Lemma3.4Fixϕ∈L∞.Then1)forany0≤s≤
T ((κε∗ϕ(s))2,f)−ϕ2(s,x)f(x)dx→
0 R (ε→0) 18
A.Manita,
V.Shcherbakov 2)forany0≤t≤T t ((κε∗ϕ(s))2,f)−ϕ2(s,x)f(x)dx R0 ds→
0 (ε→0). ProofofLemma3.4. ((κε∗ϕ(s))2,f)−ϕ2(s,x)f(x)dx
R ≤
R 2 (κε∗ϕ(s)(x)−ϕ2(s,x)|f(x)|dx ≤2ϕ∞
R (κε∗ϕ(s)(x)−ϕ(s,x)|f(x)|dx Togetthelastinequalityweusedtheidentitya2−b2=(a+b)(a−b)andthefactthatκε∗ϕ∞≤ϕ∞.Tofinishtheproofitsufficestoapplyawell-knownresultaboutconvergenceof(κε∗ϕ)(s,·)toϕ(s)inL1loc.Thisprovesthefirststatementofthelemma.Togetthesecondstatementweuseagaintheboundednessofϕandκε∗ϕandapplytheLebesguetheorem.Lemma 3.4isproved. OnthesetsuppQλ(T)wecandefineafunctional
T Ff0,T(ϕ)=(ϕ(s),fs+λfx+µf)−µ(ϕ2(s),f))ds+(ϕ
(0),f).
0 Theequation(23)andLemma3.4yieldthatforanyϕ∈suppQ(λT)Ff,
T,ε(ϕ)→Ff0,T(ϕ)asε→
0.Thisimpliesthatforanyδ1>
0 Q(λT)ϕ:|Ff,
T,ε(ϕ)−Ff0,T(ϕ)|>δ1→0(ε→0). Combiningthiswith(22)wegetthatalimitpointofthesequence{QN(
T,)λ}∞N=2isconcentratedonthetrajectoriesϕ(t,·),t∈[
0,T],takingvaluesinthesetofregularboundedfunctionsand satisfyingthefollowingintegralequation
T (ϕ(s),fs+λfx+µf)−µ(ϕ2(s),f))ds+(ϕ
(0),f)=0 0 foranyf∈C0∞,
T.Itmeansthateachsuchatrajectoryisaweaksolutionoftheequation(4)inthesenseofDefinition2.1. 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 19 3.5Uniquenessofaweaksolution Thefirstorderequation.UsingthemethodofTheorem1inthecelebratedpaper[17]ofOleinikwewillshowherethatforanymeasurableboundedinitialfunctionψ(x)theremightbeatmostoneweaksolutionoftheequation(4)inthesenseofDefinition2.1andnoentropyconditionisrequired. Letu(t,x)andv(t,x)betwoweaksolutionsoftheequation(4)intheregion[
0,T]×Rwiththesameinitialconditionψ(notnecessarilyfromH).Definition2.1impliesthat
T ((u(t,x)−v(t,x))(ft(t,x)+λfx(t,x)+µ(1−u(t,x)−v(t,x))f(t,x))dxdt=
0,(24) 0R for any f ∈
C ∞
0,T . Consider the following sequence of equations ft(t,x)+λfx(t,x)+gn(t,x)f(t,x)=F(t,x), (25) withanyinfinitelydifferentiablefunctionFequaltozerooutsideofacertainboundedregion, lyinginthehalf-planet≥δ1>0,whereδ1isanarbitrarysmallnumber.Thefunctionsgn(t,x)areuniformlyboundedforallx,t,n≥1andconvergesinL1loctothefunctiong(t,x)=µ(1−u(t,x)−v(t,x))asn→∞.Thesolutionfn(t,x)∈C0∞,Toftheequation(25)isgivenbythefollowingformula(formula(2.8)in[17]) t s    fn(t,x)=F(s,x+λ(s−t))expgn(τ,x+λ(τ−t))dτds.  
T t Equation(24)yieldsthat (u(t,x)−v(t,x))F(t,x)dxdt= (g(t,x)−gn(t,x))f(t,x))dxdt. (26) R+
R R+
R Therightsideof(26)isarbitrarysmallforsufficientlylargenand,sincetheleftsideof(26)doesnotdependonn,soitisequaltozero.Thereforeu=v,sinceFisarbitrary. Anexistenceofaweaksolutionoftheequation(4)followsfromthegeneraltheoryforquasilinearequationsofthefirstorder(forexample,Theorem8in[17]).Intheparticularcaseoftheequation(4)itispossibletoobtainanexplicitformulaforaweaksolution.FirstofallwenotethattheCauchyproblem ut(t,x)=−λux(t,x)+µ(u2(t,x)−u(t,x)),u(0,x)=ψ(x), (27) 20
A.Manita,
V.Shcherbakov hasauniqueclassicalsolution,ifψ∈C1(R)andthereisanexplicitformulaforthissolution.Indeed,usingsubstitutionu◦(t,x)=u(t,x−λt)wetransformtheequation(27)intotheequation u◦t(t,x)=−µu◦(t,x)(1−u◦(t,x)),u◦(0,x)=ψ(x). Consideringxasaparameterweobtainanordinarydifferentialequationwhichissolvableandthe solutionisgivenby: u◦(t,x)= ψ(x)e−µt. (28) 1−ψ(x)+ψ(x)e−µt So,ifψ∈C1(R),thenauniqueclassicalsolutionoftheequation(27)isgivenbythefollowing formula ψ(x+λt)e−µt u(t,x)=1−ψ(x+λt)+ψ(x+λt)e−µt. (29) IfweapproximateanymeasurableboundedfunctionginL1locbyasequenceofsmoothfunctions{gn,n≥1},thenthesequenceofcorrespondingweaksolutions{un(t,x),n≥1},whereun(t,x)isdefinedbytheformula(29)withψ=gn,convergesinL1loctotheweaksolutionoftheequationwithinitialconditiongbyTheorem11in[17]orTheorem1in[10].ItiseasytoshowbydirectcalculationthattheL1loc–limitofthesequence{un(t,x),n≥1}isgivenbythesameformula(29)withψ=g. Theformula(29)yieldsthatifψ∈H(R),thenu(t,·)∈H(R)asafunctionofxforany fixedt≥
0.Ifafunctionu(t,x)isaweaksolutionoftheequation(27),thenthisfunctionis differentiableatapoint(t,x)ifftheinitialconditionψ(y)isdifferentiableatthepointy=x+λt. KPP-equation.Theequation(5)isaquasilinearparabolicequationsofthesecondorderandisaparticularcaseofthefamousKPP-equationin[9].Itisknownthatthereexistsauniqueweaksolutionu(t,x)oftheproblem ut(t,x)=γuxx(t,x)+µ(u2(t,x)−u(t,x)),u(0,x)=ψ(x), foranyboundedmeasurableinitialfunctionψ,thissolutionisinfactauniqueclassicalsolutionandifψ∈H(R),thenu(t,·)∈H(R)asafunctionofxforanyfixedt.Werefertothepaper[17]formoredetails. 4Systemwithfixednumberofparticles Inthissectionwedealwiththesituation“Nisfixed,t→∞”. 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 21 4.1ProofofTheorem2.2 Letσ(y,w)betherateoftransitionfromthestatey=(y1,...,yN)∈Γtothestatew= (w1,...,wN)∈ΓfortheMarkovy(t)chain.Defineσ(y)=σ(y,w).Fromdefinitionof w=y theparticlesystemitfollowsthat σ(y)=(α+β)N+µNI{y>y}.
N ij (i,j) SinceI{yi>yj}≤N(N−1)/2wehaveuniformlyiny∈Γ (i,j) σ∗,N≤σ(y)≤σN∗ (30) withσ∗,N=(α+β)NandσN∗=(α+β)N+µN(N−1)/2.AdiscretetimeMarkovchain{Y(n),n=0,1,...}onthestatespaceSwithtransitionprobabilities σ(y,w),y=w p(y,w)≡P{Y(n+1)=w|Y(n)=y}=σ(y) (31) 
0, y=w, isanembeddedMarkovchainofthecontinuoustimeMarkovchain(y(t),t≥0).Theorem2.2isaconsequenceofthefollowingstatement. Lemma4.1TheMarkovchain{Y(n),n=0,1,...}isirreducible,aperiodicandsatisfiestotheDoeblincondition:thereexistε>0,m0∈NandfinitesetA⊂Γsuchthat P{Y(m0)∈A|Y
(0)=Y0}≥ε, (32) foranyY0∈
S.ThereforethisMarkovchainisergodic([5]). ProofofLemma4.1.Wearegoingtoshowthatcondition(32)holdswithA={(0,...,0)}, m0=
N, min(α,β,µN/N)
N ε= σ∗ >
0.
N ThetransitionprobabilitiesoftheMarkovchain{Y(n),n=0,1,...}areuniformlyboundedfrombelowinthefollowingsense:ifapairofstates(z,v)issuchthatσ(z,v)>0(or,equivalently,p(z,v)>0)then(31)impliesthat p(z,v)>min(α,β,µN/N)/σN∗. (33) 22
A.Manita,
V.Shcherbakov Sotoprove(32)weneedonlytoshowthatforanyythereexistsasequenceofstates v0=y,v1,v2,...,vN=(0,...,0) (34) whichcanbesubsequentlyvisitedbytheMarkovchain{Y(n),n=0,1,...}.Thelastmeansthati.e.p(vn−1,vn)>0foreveryn=1,...,Nandhence
N P{Y(N)∈A|Y
(0)=y}≥p(vn−1,vn)≥ n=
1 min(α,β,µN/N)NσN∗ asaconsequenceoftheuniformbound(33).Toproveexistenceofthesequence(34)letusassumefirstthaty=(y1,...,yN)=
0.Choose andfixsomersuchthatyr=maxyi>
0.Denotebyi n0=#{j:yj=0} thenumberofleft-mostparticles.Lettheright-mostparticleyrmoven0stepstoright: vn−vn−1=e(rN),n=1,...,n0. Thiscanbedonebyusingofjumpstothenearestrightstate.SoY(n0)=vn0hasexactlyn0 particlesat0andN−n0particlesoutof0.Denotebyin0+10,a=n0+1,...,
N.LetnowtheMarkovchainYtransfereachofthese particlesto0: va−va−1=−vina0e(iaN), a=n0+1,...,
N. Itispossibleduetotransitionsprovidedbytheinteraction.pletetheproofweneedtoconsiderthecasey=(y1,...,yN)=
0.Itisquiteeasy: v1=e(1N),v2=2e1(N),v3=3e(1N),...,vN−1=(N−1)e(1N),vN=
0. Proofofthelemmaisover. DenotebyπY=πY(y),y=(y1,...,yN)∈ΓauniquestationarydistributionoftheMarkov chain{Y(n),n=0,1,...}. TheproofofTheorem2.2isnoweasy.Firstofallletusshowthattheuniformboundσ(y)≥ σ∗,NimpliesexistenceofastationarydistributionfortheMarkovchainy(t).Indeed,itiseasytocheckthatifπYisthestationarydistributionoftheembeddedMarkovchainYandQisthe infinitesimalmatrixforthechainy(t),thenavectorwithponentss=(s(w),w∈S) definedas s(w)=πY(w),σ(w) 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 23 satisfiestotheequationsQ=
0.Soforexistenceofastationarydistributionofthechainy(t)itissufficienttoshows(w)<+∞.Itiseasytocheckthelastcondition: w∈
S s(w)=πY(w)≤
1 πY(w)=
1. w∈Sw∈Sσ(w)σ∗,Nw∈
S σ∗,
N Thereforethecontinuous-timeMarkovchain(y(t),t≥0)hasastationarydistributionπ=(π(y),y∈Γ) ofthefollowingform πY(y) π(y)= σ(y).πY(w) w∈Γσ(w) Denotepyw(t)=P{y(t)=w|y
(0)=0}.Thenextstepistoprovethatthecontinuous-timeMarkovchainy(t)isergodic.TodothisweshowthatthefollowingDoeblinconditionholds:forsomej0∈Sthereexistsh>0and0<δ<1suchthatpij0(h)≥δforalli∈
S.Itiswell-known([5])thatthisconditionimpliesergodicityandmoreover |pij(t)−π(y)|≤(1−δ)[t/h]. Letτk,k≥0,bethetimeofstayoftheMarkovchainy(t)ink−thconsecutivestate.Conditiononthesequenceofthechainstatesyk,k≥0,thejointdistributionoftherandomvariablesτk,k≥0,coincideswiththejointdistributionofindependentrandomvariablesexponentiallydistributed withparametersσ(yk),k=0,1,...,n,sothetransitionprobabilitiesofthechainy(t)are pyw(t)= P{(y→w)} n(y→w) ∆n t n e−σ(w)(t−tn)σ(yk−1)e−σ(yk−1)(tk−tk−1)dt1...dtn, k=
1 wherencorrespondstothenumberofjumpsofthechainyduringthetimeinterval[0,t],theinner sumistakenoveralltrajectories(y→w)={y=y0,y1,...,yn=w}withnjumps,integrationistakenover∆tn={0=t0≤t1≤···≤tn≤t},and P{(y→w)}=p(y,y1)p(y1,y2)···p(yn−1,w) isaprobabilityofthecorrespondingpathfortheembeddedchain.Theequation(30)impliesthattheintegrandinpyw(t)isuniformlyboundedfrombelowbytheexpression (σ∗,N)nexp(−σN∗t1)···exp(−σN∗(tn−tn−1))exp(−σN∗(t−tn)), 24
A.Manita,
V.Shcherbakov and,hence, e−σ(w)(t−tn)nσ(yk−1)e−σ(yk−1)(tk−tk−1)dt1...dtn≥(σ∗n,N!
t)ne−σN∗t ∆n k=
1 t =P{Πt=n}e−(σN∗−σ∗,N)t, whereΠtisaPoissonprocesswithparameterσ∗,
N.Itprovidesuswithalowerboundforthetransitionprobabilitiesofthetime-continuouschain: pyz0(t)≥ pn(y,z0)P{Πt=n} n e−(σN∗−σ∗,N)t. Itiseasynowtogetalowerboundforprobabilitiespn(y,z0).Fixsomez0∈Sanddenoteξ=πY(z0).ItfollowsfromergodicityofthechainY,thatforanyfixedz0 pm(y,z0)≥πY(z0)/2=ξ/2>
0, forallm≥m1=m1(y).ForaDoeblinMarkovchainwehavemorestrongconclusion,namely,theabovenumberm1doesnotdependony.Letusfixsuchm1andshowthatthecontinuous-timeMarkovchainy(t)satisfiestotheDoeblincondition.Indeed, pyz0(t)≥ pn(y,z0)P{Πt=n}+ pn(y,z0)P{Πt=n}e−(σN∗−σ∗,N)t n0andput δ=ξP{Πh≥m1}e−(σN∗−σ∗,N)h.2 Proofofthetheoremisover. 4.2Evolutionofthecenterofmass ConsiderthefollowingfunctiononthestatespaceZN:m(x1,...,xN)=(x1+···+xN)/N.Soifeachparticlehasthemass1andx1(t),...,xN(t)arepositionsofparticles,thenm(x1(t),...,xN(t)) 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 25 isthecenterofmassofthesystem.WeareinterestedinevolutionofEm(x1(t),...,xN(t)).Adirectcalculationgivesthat
N (GNm)(x1,...,xN)= i=
1 α−βNN
N + i=1j=i −xi−xjN I{x >x µ
N } ijN =(α−β)−µN|xi−xj|, (35) N2ixj}+(xj−xi)I{xj>xi}=|xi−xj|. Notethatthesummand −µN|xi−xj|N2iR. 26
A.Manita,
V.Shcherbakov Definition5.1Functionw=w(x)iscalledatravellingwavesolutionofsomePDEifthereexistsv∈Rsuchthatthefunctionu(t,x)=w(x−vt)isasolutionofthisPDE.Thenumbervisspeedofthewavew. Weareinterestedonlyinthetravellingwaveshavingthefollowingproperties:U1)w(x)∈[0,1];U2)w(x)anddw(x)/dxhavelimitsasx→±∞and,besides,w(−∞)=1andw(+∞)=
0.Weidentifytwotravellingwavesw1(x)andw2(x)ifw1(x)=w2(x−c)forsomec. Foranyprobabilisticsolution0≤u(t,x)≤1wedefineafunctionr(t)suchthatu(t,r(t))≡12.Letafunctionw(x)beatravellingwavesolution.Withoutlossofgeneralitywecanassumethatw
(0)=1/2. Definition5.2Asolutionu(t,x)convergesinformtothetravellingwavew(x)if limu(t,x+r(t))=w(x), t→+∞ uniformlyonanyfiniteinterval.Thesolutionu(t,x)convergesinspeedtothetravellingwavew(x)ifthereexistsr′(t)=dr(t)/dtandlimr′(t)=v,wherevisaspeedofthetravellingwave t→+∞ w(x). Firstorderequation.Itiseasytocheckfortheequation(4)foreveryv<λthereexistsaunique (uptoshift)travellingwavesolutionhavingpropertiesU1–U2andthistravellingwavesolutionis µ −
1 givenbythefollowingformulawv(x)=1+expλ−vx . Proposition5.1IfforsomeC>
0,ν>0,theinitialprofileψ(x)∈H(R)oftheequation(4)hasthefollowingasymptoticbehavior1−ψ(x)∼Cexp(νx),asx→−∞,thenthereexistsx0∈Rsuchthatforeveryx∈
R |u(t,x)−wv(x−x0−vt)|→
0, ast→∞,wherev=λ−µ/ν. TheproofofProposition5.1isadirectcalculationbasedontheexactformula(29).Theformula(28)yieldsthatu◦(t1,x)≥u◦(t2,x)foranyt1R.Then |u(t,x)−I{y0. 26/01/2005 Asymptoticanalysisofastochasticmodelforputations 27 Secondorderequation.Theexistenceoftravellingwavesforparabolicpartialdifferentialequationswasasubjectofstudyinginmanypapersfollowedtothepaper[9].Areviewofmanyresultscanbefoundin[24](seealso[20])andpletenessofthetextwementionsomeofthem.Reformulatingthewell-knownresults([24])weobtainthattravellingwavesoftheequation(5)canmoveonlyfromtherighttotheleft.Itmeansthatthespeedofanytravellingwaveisnegativeand,moreover,isboundedawayfrom0.Proposition5.3Forequation(5)foreveryv≤v∗=−√4γµthereexistandunique(uptoshift)travellingwavesolutionwithspeedv.TherearenoothertravellingwavesolutionssatisfyingtheconditionsU1andU2. Ifafunctionf=f(x)issuchthatf(x)≤1,f(x)→1asx→−∞andthereexistsalimitκ=limx−1log(1−f(x))>0,thenthenumberκiscalledLyapunovexponentofthefunction x→−∞ f(atminusinfinity).Itiswellknown([24])thatfortheequation(5)atravellingw(x)withspeedvhasthefollowingLyapunovexponentatminusinfinity κ(v)=−v−v2−4γµ/(2γ). Hencewegetthatforthetravellingwavewithminimalinabsolutevaluespeedv∗=−√4γµtheLyapunovexponentisκ(v∗)=µ/γ. Proposition5.4([24])Assumethataninitialfunctionψ(x)hasaLyapunovexponentκ.Thena)ifκ≥µ/γthenthesolutionu(t,x)oftheproblem√(5)convergesinformandinspeedto thetravellingwavemovingwiththeminimalspeedv∗=−4γµ;b)ifκ<µ/γthenthesolutionu(t,x)oftheproblem(5)convergesinformandinspeedto thetravellingwavewithspeedv=−γκ+µ,or,inotherwords,κ(v)=κ.κ WeseefromtheaboveanalysisthatboththefirstorderPDE(4)andthesecondorderPDE(5)exhibitsimilarlong-timebehavioroftheirsolutions.ThisseemsverynaturalifwerecallfromTheorem2.1thatthebothequationsariseashydrodynamicalapproximationsofthesamestochasticparticlesystem. AAppendix A.1ologyontheSkorokhodspace RemindthatSchwartzspaceS(R)isaFrechetspace(see[18]).InthedualspaceS′(R)oftempereddistributionsthereareatleasttwowaystodefiology(bothnotmetrizable): 28
A.Manita,
V.Shcherbakov 1)ologyonS′(R),whereallfunctionals(·,φ),φ∈S(R)arecontinuous.2)ology(s.t.)onS′(R),whichisgeneratedbythesetofseminorms ρA(M)=sup|(
M,φ)|:A⊂S(R)−bounded. φ∈
A BelowweshallconsiderS′(R)asequippedwiththeology.Theproblemofintroducing oftheologyonthespaceDT(S′):=D([
0,T],S′(R))wasstudiedin[15]and[7].Wefollowthesepapers.ForeachseminormρAonS′(R)wedefinethefollo