Uniform acceleration expansions for Markov chains

UniformAccelerationExpansionsforMarkovChainswithTime-VaryingRates1WilliamA.MasseyBellLaboratories,Room2C-320MurrayHill,[e-mail]&TLaboratories,RoomA117,180ParkAvenue,Building103,FlorhamPark,[e-mail]10,1997AbstractWestudyuniformacceleration(UA)expansionsofnite-statecontinuous-timeMarkovchainswithtime-varyingtransitionrates.TheUAexpansionscanbeusedtojustify,evaluate,andrenethepointwisestationaryapproximation,whichisthesteady-statedistributionassociatedwiththetime-dependentgeneratoratthetimeofinterest.WeobtainUAapproximationsfromtheseUAasymptoticexpansions.Wederiveatime-varyinganalogtotheuniformizationrepresentationoftransitionproba-bilitiesforchainswithconstanttransitionrates,andapplyittoestablishasymptoticresultsrelatedtotheUAasymptoticexpansion.Theseasymptoticresultscanserveasappropriatetime-varyinganalogstothenotionsofstationarydistributionsandlimitingdistributions.WeillustratetheUAapproximationsbydoinganumericalexampleforthetime-varyingErlanglossmodel.1AcceptedforpublicationintheAnnalsofAppliedProbability.AMS1991subjectclassications.60J27,60K30.Keywordsandphrases:Time-inhomogeneousMarkovchains,time-dependentbehavior,nonstationaryqueueingmodels,pointwisestationaryapproximation,eigenvaluebounds,nonnegativematrices,asymptoticexpansions,Poisson’sequation,Erlanglossmodel.11IntroductionInmanyappliedsettings,suchaswithqueueingsystems,physicalrealityindicatesthatitisappropriatetousenonstationarymodels.Forexample,arrivalratesinservicesystemstypicallyvarysubstantiallybytimeofday;e.g.,seep.259ofHall[7].However,iftherateofchangeissucientlyslow,thenitisnaturaltoapproximatethetime-dependentdistributionatanytimetbythesteady-statedistributionofthemodelwithtransitioncharacteristicsatthattimet.Inparticular,foranonstationarycontinuous-timeMarkovchain(CTMC)withtime-dependentgeneratorfA(t):t0g,wewouldapproximatethetime-dependentprobabilityvectorp(t)attimetbythesteady-stateprobabilityvector(t)associatedwithA(t),obtainedbysolving(t)A(t)=0and(t)1T=1,withtheusualregularityconditionsguaranteeingauniquesolution.(Weregardvectorsasrowvectors,sothat1Tisacolumnvectorof1’swithTthematrixtranspose.)Somevariantoftheapproximationprocedurejustdescribedisroutinelyusedintheperformanceanalysisoftelecommunicationssystemsandinmanyotherappliedsettings.Ithasbeenstudiedandcalledthepointwisestationaryapproximation(PSA)byGreenandKolesar[6],Whitt[26]andEick,MasseyandWhitt[4].Forexample,Whitt[26]provedthatPSAisasymptoticallycorrectforMt=Mt=squeuesandmoregeneraltime-dependentbirth-and-deathprocessesasthebirthanddeathratesincrease,whichisequivalent(byachangeoftimescale)tohavingtherateschangemoreslowly.InthispaperweproposeawaytoquantitativelyevaluatePSAanddeveloprenementstoit(withouthavingtosolvefortheactualtime-dependentdistribution).Inparticular,wefocusonaclassofasymptoticapproximationscalleduniformacceleration(UA)asymptoticexpansionsforCTMCs.TheUAframeworkprovidesanaturalwaytojustify,evaluateandrenethePSAbecausethePSAisthersttermoftheUAexpansion.Whenthenextfewtermsarerelativelysmall,wecanbecondentthatthePSAisagoodapproximation,butwhentheyarenot,thenthePSAcanberegardedasunreliable.TherstfewtermsoftheUAexpansionprovideaconvenientcheckonPSAbecausetheyareessentiallynomorediculttocomputethanPSAitself.Inparticular,supposethatA(t)isthetime-dependentgeneratorforanonstationaryCTMC.ThentheUAapproximationofordernforthedistributionattimetisp(t)nXk=0(k)(t);(1.1)where,foreachk,thevector(k)isasolutionofPoisson’sequation(k)(t)A(t)=y(k)(t);(1.2)withy(0)(t)=0;(0)(t)1T=1;(1.3)y(k)(t)=ddt(k1)(t)and(k)(t)1T=0fork1:(1.4)From(1.2)and(1.3),weseethat(0)(t)isindeedthestationarydistributionassociatedwithA(t),sothat(0)(t)isthePSA.However,tocalculatethehigher-orderterms(k)(t)2fork1,weneedthederivativesof(k)(t)fork0,butthesederivativescanalsobecalculatedbysolvingPoissonequations.Forexample,bydierentiating(1.2)fork=0,weseethatd(0)dt(t)A(t)=(0)(t)dAdt(t):(1.5)Similarly,d(1)dt(t)A(t)=d2dt2(0)(t)(1)(t)ddtA(t)(1.6)andd2(0)dt2(t)A(t)=2d(0)dt(t)dAdt(t)(0)(t)d2Adt2(t):(1.7)Moregenerally(byinduction),dj(n)dtj(t)A(t)=dj+1(n1)dtj+1(t)j1Xk=0jk!dk(n)dtk(t)djkAdtjk(t);(1.8)where(i)(t)0.Inorderforthe(n)vectorstohavetherequiredderivativesandfortheUAapproximationtobewelldened,weassumethatthegeneratorpossessesalltherequiredderivativesatt.Weremarkthatthederivativesof(0)(t)arealsoofinterestinthesensitivityanalysisofthestationarydistributiontochangesinthegeneratorA(t),nowregardedasthegen-eratorforastationaryCTMCsubjecttopossiblechangeinthetransitionintensities.ItisknownthatsuchsensitivityanalysiscanbeperformedbysolvingPoisson’sequation;e.g.,seeSchweitzer[23].Thus,tocalculatetherstn+1terms(0)(t);(1)(t);:::;(n)(t)intheUAapproximation(1.1),weneedtosolvePoisson’sequation(n+1)(n+2)=2timeswithdierent(known)righthandsides.In(1.1)wearenotinterestedinlargen,becausethefullseriesisnotaconvergentseries.Itisinsteadanasymptoticexpansion;see(3.12)below.Indeed,higher-ordertermsarelikelyt