introduction_to_stochastic_processes

《introduction_to_stochastic_processes》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

IntroductiontoStochasticProcesses-LectureNotes(with33illustrations)GordanŽitkovićDepartmentofMathematicsTheUniversityofTexasatAustin Contents1Probabilityreview41.1Randomvariables..........................................41.2Countablesets.............................................51.3Discreterandomvariables.....................................51.4Expectation..............................................71.5Eventsandprobability........................................81.6Dependenceandindependence..................................91.7Conditionalprobability.......................................101.8Examples................................................122Mathematicain15min152.1BasicSyntax..............................................152.2NumericalApproximation.....................................162.3ExpressionManipulation......................................162.4ListsandFunctions.........................................172.5LinearAlgebra............................................192.6PredefinedConstants........................................202.7Calculus................................................202.8SolvingEquations..........................................222.9Graphics................................................222.10ProbabilityDistributionsandSimulation............................232.11HelpCommands...........................................242.12CommonMistakes..........................................253StochasticProcesses263.1Thecanonicalprobabilityspace.................................273.2ConstructingtheRandomWalk.................................283.3Simulation...............................................293.3.1Randomnumbergeneration...............................293.3.2SimulationofRandomVariables............................303.4MonteCarloIntegration......................................334TheSimpleRandomWalk354.1Construction..............................................354.2Themaximum............................................361 CONTENTS5Generatingfunctions405.1Definitionandfirstproperties...................................405.2Convolutionandmoments.....................................425.3RandomsumsandWald’sidentity................................446Randomwalks-advancedmethods486.1Stoppingtimes............................................486.2Wald’sidentityII...........................................506.3ThedistributionofthefirsthittingtimeT1..........................526.3.1Arecursiveformula....................................526.3.2Generating-functionapproach..............................536.3.3Doweactuallyhit1soonerorlater?.........................556.3.4Expectedtimeuntilwehit1?..............................557Branchingprocesses567.1Abitofhistory............................................567.2Amathematicalmodel.......................................567.3Constructionandsimulationofbranchingprocesses....................577.4Agenerating-functionapproach.................................587.5Extinctionprobability........................................618MarkovChains638.1TheMarkovproperty........................................638.2Examples................................................648.3Chapman-Kolmogorovrelations.................................709The“Stochastics”package749.1Installation...............................................749.2BuildingChains............................................749.3Gettinginformationaboutachain................................759.4Simulation...............................................769.5Plots...................................................769.6Examples................................................7710ClassificationofStates7910.1TheCommunicationRelation...................................7910.2Classes.................................................8110.3Transienceandrecurrence....................................8310.4Examples................................................8411MoreonTransienceandrecurrence8611.1Acriterionforrecurrence.....................................8611.2Classproperties...........................................8811.3Acanonicaldecomposition....................................89LastUpdated:December24,20102IntrotoStochasticProcesses:LectureNotes CONTENTS12Absorptionandreward9212.1Absorption...............................................9212.2Expectedreward...........................................9513StationaryandLimitingDistributions9813.1Stationaryandlimitingdistributions...............................9813.2Limitingdistributions........................................10414SolvedProblems10714.1Probabilityreview..........................................10714.2RandomWalks............................................11114.3Generatingfunctions........................................11414.4Randomwalks-advancedmethods...............................12014.5Branchingprocesses........................................12214.6Markovchains-classificationofstates.............................13314.7Markovchains-absorptionandreward............................14214.8Markovchains-stationaryandlimitingdistributions....................14814.9Markovchains-variousmultiple-choiceproblems.....................156LastUpdated:December24,20103IntrotoStochasticProcesses:LectureNotes Chapter1ProbabilityreviewTheprobableiswhatusuallyhappens.—AristotleItisatruthverycertainthatwhenitisnotinourpowertodetermine.whatistrueweoughttofollowwhatismostprobable—Descartes-“DiscourseonMethod”Itisremarkablethatasciencewhichbeganwiththeconsiderationofgamesofchanceshouldhavebecomethemostimportantobjectofhumanknowledge.—PierreSimonLaplace-“ThéorieAnalytiquedesProbabilités,1812”Anyonewhoconsidersarithmeticmethodsofproducingrandomdigitsis,ofcourse,inastateofsin.—JohnvonNeumann-quotein“ConicSections”byD.MacHaleIsayuntoyou:amanmusthavechaosyetwithinhimtobeabletogivebirthtoadancingstar:Isayuntoyou:yehavechaosyetwithinyou...—FriedrichNietzsche-“ThusSpakeZarathustra”1.1RandomvariablesProbabilityisaboutrandomvariables.Insteadofgivingaprecisedefinition,letusjustmetionthatarandomvariablecanbethoughtofasanuncertain,numerical(i.e.,withvaluesinR)quantity.WhileitistruethatwedonotknowwithcertaintywhatvaluearandomvariableXwilltake,weusuallyknowhowtocomputetheprobabilitythatitsvaluewillbeinsomesomesubsetofR.Forexample,wemightbeinterestedinP[X7],P[X2[2;3:1]]orP[X2f1;2;3g].ThecollectionofallsuchprobabilitiesiscalledthedistributionofX.Onehastobeverycarefulnottoconfusetherandomvariableitselfanditsdistribution.Thispointisparticularlyimportantwhenseveralrandomvariablesappearatthesametime.WhentworandomvariablesXandYhavethesamedistribution,i.e.,whenP[X2A]=P[Y2A]foranysetA,wesaythatXandYareequally(d)distributedandwriteX=Y.4 CHAPTER1.PROBABILITYREVIEW1.2CountablesetsAlmostallrandomvariablesinthiscoursewilltakeonlycountablymanyvalues,soitisprobablyagoodideatoreviewbreiflywhatthewordcountablemeans.Asyoumightknow,thecountableinfinityisoneofmanydifferentinfinitiesweencounterinmathematics.Simply,asetiscountableifithasthesamenumberofelementsasthesetN=f1;2;:::gofnaturalnumbers.Moreprecisely,wesaythatasetAiscountableifthereexistsafunctionf:N!Awhichisbijective(one-to-oneandonto).Youcanthinkfasthecorrespondencethat“proves”thatthereexactlyasmanyelementsofAasthereareelementsofN.Alternatively,youcanviewfasanorderingofA;itarrangesAintoaparticularorderA=fa1;a2;:::g,wherea1=f(1),a2=f(2),etc.Infinitiesarefunny,however,asthefollowingexampleshowsExample1.1.1.Nitselfiscountable;justusef(n)=n.2.N0=f0;1;2;3;:::giscountable;usef(n)=n1.YoucanseeherewhyIthinkthatinfinitiesarefunny;thesetN0andthesetN-whichisitspropersubset-havethesamesize.3.Z=f:::;2;1;0;1;2;3;:::giscountable;nowthefunctionfisabitmorecomplicated;(2k+1;k0f(k)=2k;k<0:YoucouldthinkthatZismorethan“twice-as-large”asN,butitisnot.Itisthesamesize.4.Itgetsevenweirder.ThesetNN=f(m;n):m2N;n2Ngofallpairsofnaturalnumbersisalsocountable.Ileaveittoyoutoconstructthefunctionf.5.AsimilarargumentshowsthatthesetQofallrationalnumbers(fractions)isalsocountable.6.Theset[0;1]ofallrealnumbersbetween0and1isnotcountable;thisfactwasfirstprovenbyGeorgCantorwhousedaneattrickcalledthediagonalargument.1.3DiscreterandomvariablesArandomvariableissaidtobediscreteifittakesatmostcountablymanyvalues.Moreprecisely,XissaidtobediscreteifthereexistsafiniteorcountablesetSRsuchthatP[X2S]=1,i.e.,ifweknowwithcertaintythattheonlyvaluesXcantakearethoseinS.ThesmallestsetSwiththatpropertyiscalledthesupportofX.IfwewanttostressthatthesupportcorrespondstotherandomvariableX,wewriteX.Somesupportsappearmoreoftenthentheothers:1.IfXtakesonlythevalues1;2;3;:::,wesaythatXisN-valued.2.Ifweallow0(inadditiontoN),sothatP[X2N0]=1,wesaythatXisN0-valuedLastUpdated:December24,20105IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEW3.Sometimes,itisconvenienttoallowdiscreterandomvariablestotakethevalue+1.Thisismostlythecasewhenwemodelthewaitingtimeuntilthefirstoccurenceofaneventwhichmayormaynoteverhappen.Ifitneverhappens,wewillbewaitingforever,andthewaitingtimewillbe+1.Inthosecases-whenS=f1;2;3;:::;+1g=N[f+1g-wesaythattherandomvariableisextendedN-valued.ThesameappliestothecaseofN0(insteadofN),andwetalkabouttheextendedN0-valuedrandomvariables.Sometimestheadjective“extended”isleftout,andwetalkaboutN0-valuedrandomvariables,eventhoughweallowthemtotakethevalue+1.Thissoundsmoreconfusingthatitactuallyis.4.Occasionally,wewantourrandomvariablestotakevalueswhicharenotnecessarilynum-bers(thinkaboutHandTasthepossibleoutcomesofacointoss,orthesuitofarandomlychosenplayingcard).Isthecollectionofallpossiblevalues(likefH;Tgorf~;•;|;}g)iscountable,westillcallsuchrandomvariablesdiscrete.WewillseemoreofthatwhenwestarttalkingaboutMarkovchains.Discreterandomvariablesareveryniceduetothefollowingfact:inordertobeabletocomputeanyconceivableprobabilityinvolvingadiscreterandomvariableX,itisenoughtoknowhowtocomputetheprobabilitiesP[X=x],forallx2S.Indeed,ifweareinterestedinfiguringouthowmuchP[X2B]is,forsomesetBR(B=[3;6],orB=[2;1)),wesimplypickallx2SwhicharealsoinBandsumtheirprobabilities.Inmathematicalnotation,wehaveXP[X2B]=P[X=x]:x2SBForthisreason,thedistributionofanydiscreterandomvariableXisusuallydescribedviaatablex1x2x3:::X;p1p2p3:::wherethetoprowlistsalltheelementsofS(thesupportofX)andthebottomrowliststheirprobabilities(pi=P[X=xi],i2N).WhentherandomvariableisN-valued(orN0-valued),thesituationisevensimplerbecauseweknowwhatx1;x2;:::areandweidentifythedistributionofXwiththesequencep1;p2;:::(orp0;p1;p2;:::intheN0-valuedcase),whichwecalltheprobabilitymassfunction(pmf)oftherandomvariableX.WhatabouttheextendedN0-valuedcase?ItisassimplebecausewecancomputetheprobabilityP[X=+1],ifweknowalltheprobabilitiespi=P[X=i],i2N0.Indeed,weusethefactthatP[X=0]+P[X=1]+


+P[X=1]=1;P1sothatP[X=1]=1i=1pi,wherepi=P[X=i].Inotherwords,ifyouaregivenaP1probabilitymassfunction(p0;p1;:::),yousimplyneedtocomputethesumi=1pi.Ifithappenstobeequalto1,youcansafelyconcludethatXnevertakesthevalue+1.Otherwise,theprobabilityof+1ispositive.TherandomvariablesforwhichS=f0;1gareespeciallyuseful.Theyarecalledindicators.Thenamecomesfromthefactthatyoushouldthinkofsuchvariablesassignallights;ifX=1aneventofinteresthashappened,andifX=0ithasnothappened.Inotherwords,Xindicatestheoccurenceofanevent.Thenotationweuseisquitesuggestive;forexample,ifYistheoutcomeofacoin-toss,andwewanttoknowwhetherHeads(H)occurred,wewriteX=1fY=Hg:LastUpdated:December24,20106IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEWExample1.2.SupposethattwodicearethrownsothatY1andY2arethenumbersobtained(bothY1andY2arediscreterandomvariableswithS=f1;2;3;4;5;6g).Ifweareinterestedintheprobabilitythetheirsumisatleast9,weproceedasfollows.WedefinetherandomvariableZ-thesumofY1andY2-byZ=Y1+Y2.Anotherrandomvariable,letuscallitX,isdefinedbyX=1fZ9g,i.e.,(1;Z9;X=0;Z<9:Withsuchaset-up,Xsignalswhethertheeventofinteresthashappened,andwecanstateouroriginalproblemintermsofX:“ComputeP[X=1]!”.Canyoucomputeit?1.4ExpectationForadiscreterandomvariableXwithsupport,wedefinetheexpectationE[X]ofXbyXE[X]=xP[X=x];x2Paslongasthe(possibly)infinitesumxP[X=x]absolutelyconverges.Whenthesumdoesx2notconverge,orifitconvergesonlyconditionally,wesaythattheexpectationofXisnotdefined.WhentherandomvariableinquestionisN0-valued,theexpressionabovesimplifiestoX1E[X]=ipi;i=0wherepi=P[X=i],fori2N0.Unlikeinthegeneralcase,theabsoluteconvergenceofthedefiningseriescanfailinessentiallyoneway,i.e.,whenXnlimipi=+1:n!1i=0Inthatcase,theexpectationdoesnotformallyexist.WestillwriteE[X]=+1,butreallymeanthatthedefiningsumdivergestowardsinfinity.Onceweknowwhattheexpectationis,wecaneasilydefineseveralmorecommonterms:Definition1.3.LetXbeadiscreterandomvariable.•IftheexpectationE[X]exists,wesaythatXisintegrable.•IfE[X2]<1(i.e.,ifX2isintegrable),Xiscalledsquare-integrable.m•IfE[jXj]<1,forsomem>0,wesaythatXhasafinitem-thmoment.m•IfXhasafinitem-thmoment,theexpectationE[jXE[X]j]existsandwecallitthem-thcentralmoment.ItcanbeshownthattheexpectationEpossessesthefollowingproperties,whereXandYarebothassumedtobeintegrable:LastUpdated:December24,20107IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEW1.E[X+Y]=E[X]+E[Y],for;2R(linearityofexpectation).2.E[X]E[Y]ifP[XY]=1(monotonicityofexpectation).Definition1.4.LetXbeasquare-integrablerandomvariable.WedefinethevarianceVar[X]byVar[X]=E[(Xm)2];wherem=E[X]:pThesquare-rootVar[X]iscalledthestandarddeviationofX.Remark1.5.Eachsquare-integrablerandomvariableisautomaticallyintegrable.Also,ifthem-thmomentexists,thenalllowermomentsalsoexist.Westillneedtodefinewhathappenswithrandomvariablesthattakethevalue+1,butthatisveryeasy.WestipulatethatE[X]doesnotexist,(i.e.,E[X]=+1)aslongasP[X=+1]>0.Simplyput,theexpectationofarandomvariableisinfiniteifthereisapositivechance(nomatterhowsmall)thatitwilltakethevalue+1.1.5EventsandprobabilityProbabilityisusuallyfirstexplainedintermsofthesamplespaceorprobabilityspace(whichwedenotebyinthesenotes)andvarioussubsetsofwhicharecalledevents1Eventstypicallycontainallelementaryevents,i.e.,elementsoftheprobabilityspace,usuallydenotedby!.Forexample,ifweareinterestedinthelikelihoodofgettinganoddnumberasasumofoutcomesoftwodicethrows,webuildaprobabilityspace=f(1;1);(1;2);:::;(6;1);(2;1);(2;2);:::;(2;6);:::;(6;1);(6;2);:::;(6;6)ganddefinetheeventAwhichcontainsofallpairs(k;l)2suchthatk+lisanoddnumber,i.e.,A=f(1;2);(1;4);(1;6);(2;1);(2;3);:::;(6;1);(6;3);(6;5)g:Onecanthinkofeventsasverysimplerandomvariables.Indeed,if,foraneventA,wedefinetherandomvariable1Aby(1;Ahappened,1A=0;Adidnothappen,wegettheindicatorrandomvariablementionedabove.Conversely,foranyindicatorrandomvariableX,wedefinetheindicatedeventAasthesetofallelementaryeventsatwhichXtakesthevalue1.Whatdoesallthishavetodowithprobability?Theanalogygoesonestepfurther.IfweapplythenotionofexpectationtotheindicatorrandomvariableX=1A,wegettheprobabilityofA:E[1A]=P[A]:Indeed,1Atakesthevalue1onA,andthevalue0onthecomplementAc=nA.Therefore,E[1A]=1P[A]+0P[Ac]=P[A].1Whenisinfinite,notallofitssubsetscanbeconsideredevents,duetoverystrangetechnicalreasons.Wewilldisregardthatfactfortherestofthecourse.Ifyoufeelcuriousastowhythatisthecase,googleBanach-Tarskiparadox,andtrytofindaconnection.LastUpdated:December24,20108IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEW1.6DependenceandindependenceOneofthemaindifferencesbetweenrandomvariablesand(deterministicornon-random)quan-titiesisthatintheformercasethewholeismorethanthesumofitsparts.WhatdoImeanbythat?Whentworandomvariables,sayXandY,areconsideredinthesamesetting,youmustspecifymorethanjusttheirdistributions,ifyouwanttocomputeprobabilitiesthatinvolvebothofthem.Herearetwoexamples.1.Wethrowtwodice,anddenotetheoutcomeonthefirstonebyXandthesecondonebyY.2.Wethrowtwodice,anddenotetheoutcomeofthefirstonebyX,setY=6Xandforgetabouttheseconddie.Inbothcases,bothXandYhavethesamedistribution!123456X;Y111111666666Thepairs(X;Y)are,however,verydifferentinthetwoexamples.Inthefirstone,ifthevalueofXisrevealed,itwillnotaffectourviewofthevalueofY.Indeed,thedicearenot“connected”inanyway(theyareindependentinthelanguageofprobability).Inthesecondcase,theknowledgeofXallowsustosaywhatYiswithoutanydoubt-itis6X.Thisexampleshowsthatwhenmorethanonerandomvariableisconsidered,oneneedstoobtainexternalinformationabouttheirrelationship-noteverythingcanbededucedonlybylookingattheirdistributions(pmfs,or...).Oneofthemostcommonformsofrelationshiptworandomvariablescanhaveistheoneofexample(1)above,i.e.,norelationshipatall.Moreformally,wesaythattwo(discrete)randomvariablesXandYareindependentifP[X=xandY=y]=P[X=x]P[Y=y];forallxandyintherespectivesupportsXandYofXandY.Thesameconceptcanbeappliedtoevents,andwesaythattwoeventsAandBareindependentifP[AB]=P[A]P[B]:Thenotionofindependenceiscentraltoprobabilitytheory(andthiscourse)becauseitisrelativelyeasytospotinreallife.Ifthereisnophysicalmechanismthattiestwoevents(likethetwodicewethrow),weareinclinedtodeclarethemindependent2.Oneofthemostimportanttasksinprobabilisticmodellingistheidentificationofthe(smallnumberof)independentrandomvariableswhichserveasbuildingblocksforabigcomplexsystem.Youwillseemanyexamplesofthatasweproceedthroughthecourse.2Actually,trueindependencedoesnotexistinreality,save,perhapsafewquantum-theoreticphenomena.Evenwithapparentlyindependentrandomvariables,dependencecansneakinthemostslyofways.Hereisafunnyexample:arecentsurveyhasfoundalargecorrelationbetweenthesaleofdiapersandthesaleofsix-packsofbeeracrossmanyWalmartstoresthroughoutthecountry.Atfirstthesetwoappearindependent,butIamsureyoucancomeupwithmanyanamusingstorywhytheyshould,actually,bequitedependent.LastUpdated:December24,20109IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEW1.7ConditionalprobabilityWhentworandomvariablesarenotindependent,westillwanttoknowhowtheknowledgeoftheexactvalueofoneoftheaffectsourguessesaboutthevalueoftheother.Thatiswhattheconditionalprobabilityisfor.Westartwiththedefinition,andwestateitforeventsfirst:fortwoeventsA,BsuchthatP[B]>0,theconditionalprobabilityP[AjB]ofAgivenBisdefinedas:P[AB]P[AjB]=:P[B]TheconditionalprobabilityisnotdefinedwhenP[B]=0(otherwise,wewouldbecomputing0-why?).Everystatementinthesequelwhichinvolvesconditionalprobabilitywillbeassumed0toholdonlywhenP[B]=0,withoutexplicitmention.Theconditionalprobabilitycalculationsoftenuseoneofthefollowingtwoformulas.Bothofthemusethefamiliarconceptofpartition.Ifyouforgotwhatitis,hereisadefinition:acollectionA1;A2;:::;Anofeventsiscalledapartitionofifa)A1[A2[:::An=andb)AiAj=;forallpairsi;j=1;:::;nwithi6=j.So,letA1;:::;Anbeapartitionof,andletBbeanevent.1.TheLawofTotalProbability.XnP[B]=P[BjAi]P[Ai]:i=12.Bayesformula.Fork=1;:::;n,wehaveP[BjAk]P[Ak]P[AkjB]=Pn:i=1P[BjAi]P[Ai]Eventhoughtheformulasabovearestatedforfinitepartitions,theyremaintruewhenthenumberofAk’siscountablyinfinite.Thefinitesumshavetobereplacedbyinfiniteseries,however.Randomvariablescanbesubstitutedforeventsinthedefinitionofconditionalprobabilityasfollows:fortworandomvariablesXandY,theconditionalprobabiltythatX=x,givenY=y(withxandyinrespectivesupportsXandY)isgivenbyP[X=xandY=y]P[X=xjY=y]=:P[Y=y]Theformulaaboveproducesadifferentprobabilitydistributionforeachy.ThisiscalledtheconditionaldistributionofX,givenY=y.Wegiveasimpleexampletoillustratethisconcept.LetXbethenumberofheadsobtainedwhentwocoinsarethrown,andletYbetheindicatoroftheeventthatthesecondcoinshowsheads.ThedistributionofXisBinomial:!012X111;424or,inthemorecompactnotationwhichweusewhenthesupportisclearfromthecontextX(1;1;1).TherandomvariableYhastheBernoullidistributionY=(1;1).Whathappens42422LastUpdated:December24,201010IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEWtothedistributionofX,whenwearetoldthatY=0,i.e.,thatthesecondcoinshowsheads.Inthatcasewehave8>>P[X=0;Y=0]=P[thepatternisTT]=1=4=1;x=0>P[Y=0]P[Y=0]1=22:P[X=2;Y=0]P[well,thereisnosuchpattern]0===0;x=2P[Y=0]P[Y=0]1=2Thus,theconditionaldistributionofX,givenY=0,is(1;1;0).Asimilarcalculationcanbeused22togettheconditionaldistributionofX,butnowgiventhatY=1,is(0;1;1).Themoralofthe22storyisthattheadditionalinformationcontainedinYcanalterourviewsabouttheunknownvalueofXusingtheconceptofconditionalprobability.Onefinalremarkabouttherelationshipbetweenindependenceandconditionalprobability:supposethattherandomvariablesXandYareindependent.ThentheknowledgeofYshouldnotaffecthowwethinkaboutX;indeed,thenP[X=x;Y=y]P[X=x]P[Y=y]P[X=xjY=y]===P[X=x]:P[Y=y]P[Y=y]Theconditionaldistributiondoesnotdependony,andcoincideswiththeunconditionalone.ThenotionofindependencefortworandomvariablescaneasilybegeneralizedtolargercollectionsDefinition1.6.RandomvariablesX1;X2;:::;XnaresaidtobeindependentifP[X1=x1;X2=x2;:::Xn=xn]=P[X1=x1]P[X2=x2]:::P[Xn=xn]forallx1;x2;:::;xn.Aninfinitecollectionofrandomvariablesissaidtobeindependentifallofitsfinitesubcol-lectionsareindependent.Independenceisoftenusedinthefollowingway:Proposition1.7.LetX1;:::;Xnbeindependentrandomvariables.Then1.g1(X1),...,gn(Xn)arealsoindependentfor(practically)allfunctionsg1;:::;gn,2.ifX1,...,XnareintegrablethentheproductX1:::XnisintegrableandE[X1:::Xn]=E[X1]:::E[Xn];and3.ifX1,...,Xnaresquare-integrable,thenVar[X1+


+Xn]=Var[X1]+


+Var[Xn]:EquivalentlyCov[Xi;Xj]=E[(X1E[X1])(X2E[X2])]=0;foralli6=j2f1;2;:::;ng.Remark1.8.Thelaststatementsaysthatindependentrandomvariablesareuncorrelated.Theconverseisnottrue.Thereareuncorrelatedrandomvariableswhicharenotindependent.LastUpdated:December24,201011IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEWWhenseveralrandomvariables(X1;X2;:::Xn)areconsideredinthesamesetting,weof-tengroupthemtogetherintoarandomvector.ThedistributionoftherandomvectorX=(X1;:::;Xn)isthecollectionofallprobabilitiesoftheformP[X1=x1;X2=x2;:::;Xn=xn];whenx1;x2;:::;xnrangethroughallnumbersintheappropriatesupports.Unlikeinthecaseofasinglerandomvariable,writingdownthedistributionsofrandomvectorsintablesisabitmoredifficult.Inthetwo-dimensionalcase,onewouldneedanentirematrix,andinthehigherdimensionssomesortofahologramwouldbetheonlyhope.ThedistributionsofthecomponentsX1;:::;XnoftherandomvectorXarecalledthemarginaldistributionsoftherandomvariablesX1;:::;Xn.WhenwewanttostressthefactthattherandomvariablesX1;:::;Xnareapartofthesamerandomvector,wecallthedistributionofXthejointdistributionofX1;:::;Xn.Itisimportanttonotethat,unlessrandomvariablesX1;:::;Xnareaprioriknowntobeindependent,thejointdistributionholdsmoreinformationaboutXthanallmarginaldistributionstogether.1.8ExamplesHereisashortlistofsomeofthemostimportantdiscreterandomvariables.Youwilllearnaboutgeneratingfunctionssoon.Example1.9.Bernoulli.Success(1)offailure(0)withprobabilityp(ifsuccessisencodedby1,failureby1andp=1,wecallitthecointoss).20.7.parameters:p2(0;1)(q=1p)0.6.notation:b(p).support:f0;1g0.5.pmf:p0=pandp1=q=1p0.4.generatingfunction:ps+q0.3.mean:pp.standarddeviation:pq0.2.figure:themassfunctionaBernoullidistribu-0.1tionwithp=1=3.0.0Binomial.Thenumberofsuccessesinnrepeti--0.50.00.51.0LastUpdated:December24,201012IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEWtionsofaBernoullitrialwithsuccessprobabilityp.0.30.parameters:n2N,p2(0;1)(q=1p).notation:b(n;p)0.25.support:f0;1;:::;ng
0.20.pmf:p=npkqnk,k=0;:::;nkk.generatingfunction:(ps+q)n0.15.mean:npp0.10.standarddeviation:npq.figure:massfunctionsofthreebinomialdis-0.05tributionswithn=50andp=0:05(blue),p=0:5(purple)andp=0:8(yellow).01020304050Poisson.Thenumberofspellingmistakesonemakeswhiletypingasinglepage..parameters:>00.4.notation:p(n;p).support:N00.3k.pmf:pk=ek!,k2N0.generatingfunction:e(s1)0.2.mean:p.standarddeviation:0.1.figure:massfunctionsoftwoPoissondistribu-tionswithparameters=0:9(blue)and=100510152025(purple).Geometric.ThenumberofrepetitionsofaBernoullitrialwithparameterpuntilthefirstsuccess.0.30.parameters:p2(0;1),q=1p.notation:g(p)0.25.support:N00.20.pmf:pk=pqk1,k2N0p.generatingfunction:0.151qsq.mean:pp0.10q.standarddeviation:p0.05.figure:massfunctionsoftwoGeometricdistri-butionswithparametersp=0:1(blue)andp=0:4051015202530(purple).LastUpdated:December24,201013IntrotoStochasticProcesses:LectureNotes CHAPTER1.PROBABILITYREVIEWNegativeBinomial.Thenumberoffailuresittakestoobtainrsuccessesinrepeatedindepen-dentBernoullitrialswithsuccessprobabilityp.0.30.parameters:r2N,p2(0;1)(q=1p).notation:g(n;p)0.25.support:N0
0.20.pmf:p=rprqk,k=2Nkk0rp0.15.generatingfunction:1qsq.mean:r0.10ppqr.standarddeviation:p0.05.figure:massfunctionsoftwonegativebino-mialdistributionswithr=100;p=0:6(blue)and020406080100r=25;p=0:9(purple).LastUpdated:December24,201014IntrotoStochasticProcesses:LectureNotes Chapter2Mathematicain15minMathematicaisaglorifiedcalculator.Hereishowtouseit1.2.1BasicSyntax•Symbols+,-,/,^,*areallsupportedbyMathematica.Multiplicationcanberepre-sentedbyaspacebetweenvariables.ax+banda*x+bareidentical.•Warning:Mathematicaiscase-sensitive.Forexample,thecommandtoexitisQuitandnotquitorQUIT.•Bracketsareusedaroundfunctionarguments.WriteSin[x],notSin(x)orSin{x}.•Parentheses()grouptermsformathoperations:(Sin[x]+Cos[y])*(Tan[z]+z^2).•Ifyouendanexpressionwitha;(semi-colon)itwillbeexecuted,butitsoutputwillnotbeshown.Thisisusefulforsimulations,e.g.•Braces{}areusedforlists:In[1]:=A=81,2,334LastUpdated:December24,201017IntrotoStochasticProcesses:LectureNotes CHAPTER2.MATHEMATICAIN15MIN•Iftheexpressionexprdependsonavariable(sayi),Table[expr,{i,m,n}]producesalistofthevaluesoftheexpressionexprasirangesfrommtonIn[37]:=Table@i^2,8i,0,5>1-xLastUpdated:December24,201021IntrotoStochasticProcesses:LectureNotes CHAPTER2.MATHEMATICAIN15MIN2.8SolvingEquations•AlgebraicequationsaresolvedwithSolve[lhs==rhs,x],wherexisthevariablewithre-specttowhichyouwanttosolvetheequation.Besuretouse==andnot=inequations.Mathematicareturnsthelistwithallsolutions:In[81]:=Solve@x^3x,xDOut[81]=88x®-1<,8x®0<,8x®1<<•FindRoot[f,{x,x0}]isusedtofindarootwhenSolve[]doesnotwork.Itsolvesforxnumerically,usinganinitialvalueofx0:In[82]:=FindRoot@Cos@xDx,8x,1>>>x1;0x>:::>>:xn;qn1x12.TheMethodofInverseFunctionsThebasicobservationinthismethodisthat,foranycontinuousrandomvariableXwiththedistributionfunctionFX,therandomvariableY=FX(X)isuniformlydistributedon[0;1].ByinvertingthedistributionfunctionFXandapplyingittoY,werecoverX.Therefore,ifwewishtosimulatearandomvariablewithaninvertibledistributionfunctionF,wefirstsimulateauniformrandomvariableon[0;1](usingrand)andthenapplythefunctionF1totheresult.Inotherwords,usef=F1asthetransformationfunction.Ofcourse,thismethodfailsifwecannotwriteF1inclosedform.Example3.6.(ExponentialDistribution)LetusapplythemethodofinversefunctionstothesimulationofanexponentiallydistributedrandomvariableXwithparameter.RememberthatthedensityfXofXisgivenbyfX(x)=exp(x);x>0;andsoFX(x)=1exp(x);x>0;andsoF1(y)=1log(1y):Since,1randhasthesameU[0;1]-distributionasrand,weXconcludethatf(x)=1log(x)worksasatransformationfunctioninthiscase,i.e.,thatlog(rand)hastherequiredExp()-distribution.Example3.7.(CauchyDistribution)TheCauchydistributionisdefinedthroughitsdensityfunction11fX(x)=:(1+x2)ThedistributionfunctionFXcanbedeterminedexplicitlyinthisexample:Zx
11111FX(x)=2dx=+arctan(x);andsoFX(y)=tany;1(1+x)22yieldingthatf(x)=tan((x1))isatransformationfunctionfortheCauchyrandom2variable,i.e.,tan((rand0:5))willsimulateaCauchyrandomvariableforyou.LastUpdated:December24,201031IntrotoStochasticProcesses:LectureNotes CHAPTER3.STOCHASTICPROCESSES3.TheBox-MullermethodThismethodisusefulforsimulatingnormalrandomvariables,sinceforthemthemethodofinversefunctionfails(thereisnoclosed-formexpressionforthedistributionfunctionofastandardnormal).Notethatthismethoddoesnotfallunderthatcategoryoftransformationfunctionmethodsasdescribedabove.Youwillsee,though,thatitisverysimilarinspirit.Itisbasedonaclevertrick,butthecompleteproofisabittechnical,soweomitit.Proposition3.8.Let1and2beindependentU[0;1]-distributedrandomvariables.ThentherandomvariablesppX1=2log(1)cos(2 2);X2=2log(1)sin(2 2)areindependentandstandardnormal(N(0,1)).Therefore,inordertosimulateanormalrandomvariablewithmean=0andvariance2=1,weproducecallthefunctionrandtwicetoproducetworandomnumbersrand1andrand2.ThenumbersppX1=2log(rand1)cos(2rand2);X2=2log(rand1)sin(2rand2)willbetwoindependentnormals.Notethatitisnecessarytocallthefunctionrandtwice,butwealsogettwonormalrandomnumbersoutofit.Itisnothardtowriteaprocedurewhichwillproduce2normalrandomnumbersinthiswayoneverysecondcall,returnoneofthemandstoretheotherforthenextcall.Inthespiritofthediscussionabove,thefunctionf=(f1;f2):(0;1][0;1]!R2givenbyppf1(x;y)=2log(x)cos(2y);f2(x;y)=2log(x)sin(2y):canbeconsideredatransformationfunctioninthiscase.4.MethodoftheCentralLimitTheoremThefollowingalgorithmisoftenusedtosimulateanormalrandomvariable:(a)Simulate12independentuniformrandomvariables(rands)-1; 2;:::; 12.(b)SetX=1+2+


+126.ThedistributionofXisveryclosetothedistributionofaunitnormal,althoughnotexactlyequal(e.g.P[X>6]=0,andP[Z>6]6=0,foratruenormalZ).ThereasonwhyXapproximatesthenormaldistributionwellcomesfromthefollowingtheoremTheorem3.9.LetX1;X2;:::beasequenceofindependentrandomvariables,allhav-ingthesame(square-integrable)distribution.Set=E[X1](=E[X2]=:::)and2=Var[X1](=Var[X2]=:::).Thesequenceofnormalizedrandomvariables(X1+X2+


+Xn)np;nconvergestothenormalrandomvariable(inamathematicallyprecisesense).LastUpdated:December24,201032IntrotoStochasticProcesses:LectureNotes CHAPTER3.STOCHASTICPROCESSESThechoiceofexactly12rands(asopposedto11or35)comesfrompractice:itseemstoachievesatisfactoryperformancewithrelativelylowcomputationalcost.Also,thestandardppdeviationofaU[0;1]randomvariableis1=12,sothedenominatornconvenientlybecomes1forn=12.Itmightseemabitwastefultouse12callsofrandinordertoproduceonedrawfromtheunitnormal.Ifyoutryitout,youwillsee,however,thatitisofcomparablespeedtotheBox-Mullermethoddescribedabove;whileBox-Mullerpusescomputationallyexpensivecos;sin;andlog,thismethodusesonlyadditionandsubtraction.Thefinalverdictofthecomparisonofthetwomethodswilldependonthearchitectureyouarerunningthecodeon,andthequalityoftheimplementationofthefunctionscos;sin:::.5.OthermethodsThereisanumberofothermethodsfortransformingtheoutputofrandintorandomnumberswithprescribeddensity(rejectionmethod,Poissontrick,...).YoucanreadabouttheminthefreeonlinecopyofNumericalrecipesinCathttp://www.library.cornell.edu/nr/bookcpdf.html3.4MonteCarloIntegrationHavingdescribedsomeoftheproceduresandmethodsusedforsimulationofvariousrandomobjects(variables,vectors,processes),weturntoanapplicationinprobabilityandnumericalmathematics.WestartoffbythefollowingversionoftheLawofLargeNumberswhichconstitutesthetheorybehindmostoftheMonteCarloapplicationsTheorem3.10.(LawofLargeNumbers)LetX1;X2;:::beasequenceofidenticallydistributedrandomvariables,andletg:R!Rbefunctionsuchthat=E[g(X1)](=E[g(X2)]=:::)exists.ThenZ1g(X1)+g(X2)+


+g(Xn)!=g(x)fX1(x)dx;asn!1.n1ThekeyideaofMonteCarlointegrationisthefollowingR1Supposethatthequantityyweareinterestedincanbewrittenasy=1g(x)fX(x)dxforsomerandomvariableXwithdensityfXandcomefunctiong,andthatx1;x2;:::arerandomnumbersdistributedaccordingtothedistributionwithdensityfX.Thentheaverage1(g(x1)+g(x2)+


+g(xn));nwillapproximatey.pItcanbeshownthattheaccuracyoftheapproximationbehaveslike1=n,sothatyouhavetoquadruplethenumberofsimulationsifyouwanttodoubletheprecisionofyouapproximation.LastUpdated:December24,201033IntrotoStochasticProcesses:LectureNotes CHAPTER3.STOCHASTICPROCESSESExample3.11.R11.(numericalintegration)Letgbeafunctionon[0;1].Toapproximatetheintegralg(x)dx0wecantakeasequenceofn(U[0,1])randomnumbersx1;x2;:::,Z1g(x1)+g(x2)+


+g(xn)g(x)dx;0nbecausethedensityofXU[0;1]isgivenby(1;0x1fX(x)=:0;otherwise2.(estimatingprobabilities)LetYbearandomvariablewiththedensityfunctionfY.IfweareinterestedintheprobabilityP[Y2[a;b]]forsomealg+#f(x0;x1;:::;xn):xn=lg:(4.2)ProofClaim4.4.Westartbydefiningabijectivetransformationwhichmapstrajectoriesintotrajectories.Foratrajectory(x0;x1;:::;xn)2Al,letk(l)=k(l;(x0;x1;:::;xn))bethesmallestvalueoftheindexksuchthatxkl.Inthestochastic-process-theoryparlance,k(l)isthefirsthittingtimeofthesetfl;l+1;:::g.Weknowthatk(l)iswell-defined(sinceweareonlyapplyingittotrajectoriesinAl)andthatittakesvaluesinthesetf1;:::;ng.Withk(l)atourdisposal,let(y0;y1;:::;yn)2Cbeatrajectoryobtainedfrom(x0;x1;:::;xn)bythefollowingprocedure:1.donothinguntilyougettok(l):•y0=x0,•y1=x1,...6ææææææ•yk(l)=xk(l).4ææ2.usetheflippedvaluesforthecoin-tossesæææææ2ææææfromk(l)onwards:ææææ•yy=(xx),2468101214k(l)+1k(l)k(l)+1k(l)æ•yk(l)+2yk(l)+1=(xk(l)+2xk(l)+1),-2...•ynyn1=(xnxn1).Thepictureontherightshowstwotrajectories:ablueoneanditsreflectioninred,withn=15,l=4andk(l)=8.Graphically,(y0;:::;yn)lookslike(x0;:::;xn)untilithitsthelevell,andthenfollowsitsreflectionaroundthelevellsothatykl=lxk,forkk(l).Ifk(l)=n,then(x0;x1;:::;xn)=(y0;y1;:::;yn).Itisclearthat(y0;y1;:::;yn)isinC.Letusdenotethistransformationby:Al!C;(x0;x1;:::;xn)=(y0;y1;:::;yn)andcallitthereflectionmap.Thefirstimportantpropertyofthereflexionmapisthatitisitsowninverse:applytoany(y0;y1;:::;yn)inAl,andyouwillgettheoriginal(x0;x1;:::;xn).Inotherwords=Id,i.e.isaninvolution.ItfollowsimmediatelythatisabijectionfromAlontoAl.Togettothesecondimportantpropertyof,letussplitthesetAlintothreepartsaccordingtothevalueofxn:1.A>=f(x;x;:::;x)2A:x>lg,l01nln2.A==f(x0;x1;:::;xn)2Al:xn=lg,andl3.A<=f(x;x;:::;x)2A:x)=A<;(A<)=A>;and(A=)=A=:llllllWeshouldnotethat,inthedefinitionofA>andA=,theaprioristipulationthat(x;x;:::;x)2ll01nAlisunncessary.Indeed,ifxnl,youmustalreadybeinAl.Therefore,bythebijectivityof,LastUpdated:December24,201037IntrotoStochasticProcesses:LectureNotes CHAPTER4.THESIMPLERANDOMWALKwehave#A<=#A>=#f(x;x;:::;x):x>lg;ll01nnandso#Al=2#f(x0;x1;:::;xn):xn>lg+#f(x0;x1;:::;xn):xn=lg;justasweclaimed.Nowthatwehave(4.2),wecaneasilyrewriteitasfollows:XXXP[Mnl]=P[Xn=l]+2P[Xn=j]=P[Xn=j]+P[Xn=j]:j>lj>ljlFinally,wesubtractP[Mnl+1]fromP[Mnl]togettheexpressionforP[Mn=l]:P[Mn=l]=P[Xn=l+1]+P[Xn=l]:ItremainstonotethatonlyoneoftheprobabilitiesP[Xn=l+1]andP[Xn=l]isnon-zero,thefirstoneifnandlhavedifferentparityandthesecondoneotherwise.Ineithercasethenon-zeroprobabilityisgivenbynnn+l+12:bc2Letususethereflectionprincipletosolveaclassicalproblemincombinatorics.Example4.5(TheBallotProblem).Supposethattwocandidates,DaisyandOscar,arerunningforoffice,andn2Nvoterscasttheirballots.Votesarecountedbythesameofficial,onebyone,untilallnofthemhavebeenprocessed(likeintheolddays).Aftereachballotisopened,theofficialrecordsthenumberofvoteseachcandidatehasreceivedsofar.Attheend,theofficialannouncesthatDaisyhaswonbyamarginofm>0votes,i.e.,thatDaisygot(n+m)=2votesandOscartheremaining(nm)=2votes.WhatistheprobabilitythatatnotimeduringthecountinghasOscarbeeninthelead?Weassumethattheorderinwhichtheofficialcountsthevotesiscompletelyindependentoftheactualvotes,andthateachvoterchoosesDaisywithprobabilityp2(0;1)andOscarwithprobabilityq=1p.Forkn,letXkbethenumberofvotesreceivedbyDaisyminusthenumberofvotesreceivedbyOscarinthefirstkballots.Whenthek+1-stvoteiscounted,Xkeitherincreasesby1(ifthevotewasforDaisy),ordecreasesby1otherwise.ThevotesareindependentofeachotherandX0=0,soXk,0knis(thebeginningof)asimplerandomwalk.Theprobabilityofanup-stepisp2(0;1),sothisrandomwalkisnotnecessarilysymmetric.Theballotproblemcannowberestatedasfollows:WhatistheprobabilitythatXk0forallk2f0;:::;ng,giventhatXn=m?Thefirststeptowardsunderstandingthesolutionistherealizationthattheexactvalueofpdoesnotmatter.Indeed,weareinterestedintheconditionalprobabilityP[FjG]=P[FG]=P[G],whereFdenotesthefamilyofalltrajectoriesthatalwaysstaynon-negativeandGthefamilyofthoseLastUpdated:December24,201038IntrotoStochasticProcesses:LectureNotes CHAPTER4.THESIMPLERANDOMWALKthatreachmattimen.EachtrajectoryinGhas(n+m)=2up-stepsand(nm)=2down-steps,soitsprobabilityweightisalwaysequaltop(n+m)=2q(nm)=2.Therefore,P[FG]#(FG)p(n+m)=2q(nm)=2#(FG)P[FjG]===:(4.3)P[G]#Gp(n+m)=2q(nm)=2#G
nWealreadyknowhowtocountthenumberofpathsinG-itisequalto-so“all”(n+m)=2thatremainstobedoneistocountthenumberofpathsinGF.ThepathsinGFformaportionofallthepathsinGwhichdon’thitthelevell=1,sothat#(GF)=#G#H,whereHisthesetofallpathswhichfinishatm,butcross(or,atleast,touch)thelevell=1intheprocess.Canweusethereflectionprincipletofind#H?Yes,wedo.Infact,youcanconvinceyourselfthatthereflectionofanypathinHaroundthelevell=1afteritsfirsthittingtimeofthatlevelpoducesapaththatstartsat0andendsatm2.Conversely,thesameprocedureappliedtosuchapathyieldsapathinH.Thenumberofpaths
nfrom0tom2iseasytocount-itisequalto.Puttingeverythingtogether,weget(n+m)=2+1

nnkk+12k+1nn+mP[FjG]=
=;wherek=:nk+12k
Thelastequalityfollowsfromthedefinitionofbinomialcoefficientsn=n!.kk!(nk)!TheBallotproblemhasalonghistory(goingbacktoatleast1887)andhasspurredalotofresearchincombinatoricsandprobability.Infact,peoplestillwriteresearchpapersonsomeofitsgeneralizations.Whenposedoutsidethecontextofprobability,itisoftenphrasedas“inhowmanywayscanthecountingbeperformed...”(thedifferencebeingonlyinthenormalizing
nfactorappearingin(4.3)above).Aspecialcasem=0seemstobeevenmorepopular-theknumberof2n-steppathsfrom0to0nevergoingbelowzeroiscalledtheCatalannumberandequalsto12nCn=:n+1nCanyouderivethisexpressionfrom(4.3)?Ifyouwanttotestyourunderstandingabitfurther,hereisanidentity(calledSegner’srecurrenceformula)satisfiedbytheCatalannumbersXnCn=Ci1Cni;n2N:i=1CanyouproveitusingtheBallot-probleminterpretation?LastUpdated:December24,201039IntrotoStochasticProcesses:LectureNotes Chapter5GeneratingfunctionsThepath-countingmethodusedinthepreviouslectureonlyworksforcomputationsrelatedtothefirstnstepsoftherandomwalk,wherenisgiveninadvance.Wewillseelaterthatmostoftheinterestingquestionsdonotfallintothiscategory.Forexample,thedistributionofthetimeittakesfortherandomwalktohitthelevell6=0islikethat.Thereisnowaytogiveana-prioriboundonthenumberofstepsitwilltaketogettol(infact,theexpectationofthisrandomvariableis+1).Todealwithawiderclassofpropertiesofrandomwalks(andotherprocesses),weneedtodevelopsomenewmathematicaltools.5.1DefinitionandfirstpropertiesThedistributionofanN0-valuedrandomvariableXiscompletelydeterminedbythesequencefpngn2N0ofnumbersin[0;1]givenbypn=P[X=n];n2N0:Asasequenceofrealnumbers,fpngn2N0canbeusedtoconstructapowerseries:X1P(s)=psk:(5.1)Xkk=0PItfollowsfromthefactthatjpnj1thattheradiusofconvergence1offpngn2N0isatnleastequalto1.Therefore,PXiswelldefinedfors2[1;1],and,perhaps,elsewhere,too.P1kDefinition5.1.ThefunctionPXgivenbyPX(s)=k=0pksiscalledthegeneratingfunctionoftherandomvariableX,or,moreprecisely,ofitspmffpngn2N0.Beforeweproceed,letusfindanexpressionforthegeneratingfunctionsofsomeofthepopularN0-valuedrandomvariables.Example5.2.P11kRemember,thattheradiusofconvergenceofapowerseriesakxisthelargestnumberR2[0;1]suchPk=01kthatakxconvergesabsolutelywheneverjxj1in(3),inExample5.2.ForthedistributionwithCP111pmfgivenbypk=(k+1)2,whereC=(k=0(k+1)2),theradiusofconvergenceisexactlyequalto1.Canyouseewhy?5.2ConvolutionandmomentsThetruepowerofgeneratingfunctionscomesfromthefactthattheybehaveverywellundertheusualoperationsinprobability.Definition5.6.Letfpngn2N0andfqngn2N0betwoprobability-massfunctions.Theconvolutionpqoffpngn2N0andfqngn2N0isthesequencefrngn2N0,whereXnrn=pkqnk;n2N0:k=0Thisabstractly-definedoperationwillbecomemuchcleareronceweprovethefollowingproposition:Proposition5.7.LetX;YbetwoindependentN0-valuedrandomvariableswithpmfsfpngn2N0andfqngn2N0.ThenthesumZ=X+YisalsoN0-valuedanditspmfistheconvolutionoffpngn2N0andfqngn2N0inthesenseofDefinition5.6.Proof.Clearly,ZisN0-valued.Toobtainanexpressionforitspmf,weusethelawoftotalprobability:XnP[Z=n]=P[X=k]P[Z=njX=k]:k=0However,P[Z=njX=k]=P[X+Y=njX=k]=P[Y=nkjX=k]=P[Y=nk],wherethelastequalityfollowsfromindependenceofXandY.Therefore,XnXnP[Z=n]=P[X=k]P[Y=nk]=pkqnk:k=0k=0Corollary5.8.Letfpngn2N0andfpngn2N0beanytwopmfs.1.Convolutioniscommutative,i.e.,pq=qp.LastUpdated:December24,201042IntrotoStochasticProcesses:LectureNotes CHAPTER5.GENERATINGFUNCTIONSP12.Theconvolutionoftwopmfsisapmf,i.e.rn0,foralln2N0andk=0rk=1,forr=pq.Corollary5.9.Letfpngn2N0andfpngn2N0beanytwopmfs,andletX1X1P(s)=pskandQ(s)=qskkkk=0k=0P1kbetheirgeneratingfunctions.ThenthegeneratingfunctionR(s)=k=0rks,oftheconvolu-tionr=pqisgivenbyR(s)=P(s)Q(s):Equivalently,thegeneratingfunctionPX+YofthesumoftwoindependentN0-valuedrandomvariablesisequaltotheproductPX+Y(s)=PX(s)PY(s);ofthegeneratingfunctionsPXandPYofXandY.Example5.10.1.Thebinomialb(n;p)distributionisasumofnindependentBernoullisb(p).Therefore,ifweapplyCorrolary5.9ntimestothegeneratingfunction(q+ps)oftheBernoullib(p)distributionweimmediatelygetthatthegeneratingfunctionofthebinomialis(q+ps):::(q+ps)=(q+ps)n.2.Moregenerally,wecanshowthatthesumofmindependentrandomvariableswiththeb(n;p)distributionhasabinomialdistributionb(mn;p).Ifyoutrytosumbinomialswithdifferentvaluesoftheparameterpyouwillnotgetabinomial.3.Whatisevenmoreinteresting,thefollowingstatementcanbeshown:SupposethatthesumZoftwoindependentN0-valuedrandomvariablesXandYisbinomiallydistributedwithparametersnandp.ThenbothXandYarebinomialwithparametersnX;pandny;pwherenX+nY=n.Inotherwords,theonlywaytogetabinomialasasumofindependentrandomvariablesisthetrivialone.Anotherusefulthingaboutgeneratingfunctionsisthattheymakethecomputationofmo-mentseasier.Proposition5.11.Letfpngn2N0beapmfofanN0-valuedrandomvariableXandletP(s)beitsgeneratingfunction.Forn2Nthefollowingtwostatementsareequivalent1.E[Xn]<1,dnP(s)dnP(s)2.dsnexists(inthesensethattheleftlimitlims%1dsnexists)s=1Ineithercase,wehavendE[X(X1)(X2):::(Xn+1)]=P(s):dsns=1LastUpdated:December24,201043IntrotoStochasticProcesses:LectureNotes CHAPTER5.GENERATINGFUNCTIONSThequantitiesE[X];E[X(X1)];E[X(X1)(X2)];:::arecalledfactorialmomentsoftherandomvariableX.Youcangettheclassicalmomentsfromthefactorialmomentsbysolvingasystemoflinearequations.Itisverysimpleforthefirstfew:E[X]=E[X];E[X2]=E[X(X1)]+E[X];E[X3]=E[X(X1)(X2)]]+3E[X(X1)]+E[X];:::Ausefulidentitywhichfollowsdirectlyfromtheaboveresultsisthefollowing:Var[X]=P00(1)+P0(1)(P0(1))2;anditisvalidifthefirsttwoderivativesofPat1exist.Example5.12.LetXbeaPoissonrandomvariablewithparameter.ItsgeneratingfunctionisgivenbyP(s)=e(s1):XdnnTherefore,dsnPX(1)=,andso,thesequence(E[X];E[X(X1)];E[X(X1)(X2)];:::)offactorialmomentsofXisjust(;2;3;:::).ItfollowsthatE[X]=;E[X2]=2+;Var[X]=E[X3]=3+32+;:::5.3RandomsumsandWald’sidentityOurnextapplicationofgeneratingfunctioninthetheoryofstochasticprocessesdealswiththeso-calledrandomsums.Letfngn2Nbeasequenceofrandomvariables,andletNbearandomtime(arandomtimeissimplyanN0[f+1g-valuerandomvariable).Wecandefinetherandomvariable(XN0;N(!)=0;Y=kbyY(!)=PN(!)for!2:k=0k=1k(!);N(!)1Moregenerally,foranarbitrarystochasticprocessfXngn2N0andarandomtimeN(withP[N=+1]=0),wedefinetherandomvariableXNbyXN(!)=XN(!)(!),for!2.WhenNisaconstant(N=n),thenXNissimplyequaltoXn.Ingeneral,thinkofXPNasavaluenofthestochastiprocessPXtakenatthetimewhichisitselfrandom.IfXn=k=1k,thenNXN=k=1k.Example5.13.Letfngn2Nbetheincrementsofasymmetricsimplerandomwalk(coin-tosses),andletNhavethefollowingdistribution012N1=31=31=3LastUpdated:December24,201044IntrotoStochasticProcesses:LectureNotes CHAPTER5.GENERATINGFUNCTIONSwhichisindependentoffngn2N(itisveryimportanttospecifythedependencestructurePNbetweenNandfngn2Ninthissetting!).LetuscomputethedistributionofY=k=0kinthiscase.Thisiswherewe,typically,usetheformulaoftotalprobability:P[Y=m]=P[Y=mjN=0]P[N=0]+P[Y=mjN=1]P[N=1]+P[Y=mjN=2]P[N=2]XNXN=P[k=mjN=0]P[N=0]+P[k=mjN=1]P[N=1]k=0k=0XN+P[k=mjN=2]P[N=2]k=01=(P[0=m]+P[1=m]+P[1+2=m]):3Whenm=1(forexample),weget0+1+0P[Y=1]=2=1=6:3Performthecomputationforsomeothervaluesofmforyourself.WhathappenswhenNandfngn2Naredependent?Thiswillusuallybethecaseinpractice,asthevalueofthetimeNwhenwestopaddingincrementswilltypicallydependonthebehaviourofthesumitself.Example5.14.Letfngn2Nbeasabove-wecanthinkofasituationwhereagamblerisrepeatedlyplayingthesamegameinwhichacoinistossedandthegamblerwinsadollariftheoutcomeisheadsandloosesadollarotherwise.A“smart”gamblerentersthegameanddecidesonthefollowingtactic:Let’sseehowthefirstgamegoes.IfIlose,I’llplayanother2gamesandhopefullycovermylosses,andIfIwin,I’llquitthenandthere.ThedescribedstrategyamountstothechoiceoftherandomtimeNasfollows:(1;1=1;N(!)=3;1=1:Then(1;1=1;Y(!)=1+2+3;1=1:Therefore,P[Y=1]=P[Y=1j1=1]P[1=1]+P[Y=1j1=1]P[1=1]=1
P[1=1]+P[2+3=2]P[1=1]=1(1+1)=5:248Similarly,wegetP[Y=1]=1andP[Y=3]=1.TheexpectationE[Y]isequalto1
5+488(1)
1+(3)
1=0.Thisisnotanaccident.Oneofthefirstpowerfulresultsofthebeautiful48martingaletheorystatesthatnomatterhowsmartastrategyyouemply,youcannotbeatafairgamble.LastUpdated:December24,201045IntrotoStochasticProcesses:LectureNotes CHAPTER5.GENERATINGFUNCTIONSWewillreturntothegeneral(non-independent)caseinthenextlecture.LetususegeneratingPNfunctionstogiveafulldescriptionofthedistributionofY=k=0kinthiscase.Proposition5.15.Letfngn2NbeasequenceofindependentN0-valuedrandomvariables,allofwhichsharethesamedistributionwithpmffpngn2N0andgeneratingfunctionP(s).LetNbearandomtimeindependentofPfngn2N.ThenthegeneratingfunctionPYoftherandomNsumY=k=0kisgivenbyPY(s)=PN(P(s)):Proof.WeusetheideafromExample5.13andconditiononpossiblevaluesofN.Wealsousethefollowingfact(Tonelli’stheorem)withoutproof:X1X1X1X1If8i;jaij0;thenaij=aij:(5.3)k=0i=0i=0k=0X1P(s)=skP[Y=k]Yk=0X1X1=skP[Y=kjN=i]P[N=i]k=0i=0X1X1Xi=skP[=k]P[N=i](byindependence)jk=0i=0j=0X1X1Xi=skP[=k]P[N=i](byTonelli)ji=0k=0j=0X1X1Xi=P[N=i]skP[=k](by(5.3))ji=0k=0j=0By(iterationof)Corollary5.9,weknowthatthegeneratingfunctionoftherandomvariablePiij=0j-whichisexactlywhatthesecondsumaboverepresents-is(P(s)).Therefore,thechainofequalitiesabovecanbecontinuedasX1=P[N=i](P(s))ii=0=PN(P(s)):Corollary5.16(Wald’sIdentityI).Letfngn2NandNbeasinProposition5.15.Suppose,also,thatE[N]<1andE[1]<1.ThenXNE[k]=E[N]E[1]:k=0LastUpdated:December24,201046IntrotoStochasticProcesses:LectureNotes CHAPTER5.GENERATINGFUNCTIONSProof.WejustapplythecompositionruleforderivativestotheequalityPY=PNPtogetP0(s)=P0(P(s))P0(s):YNAfterwelets%1,wegetE[Y]=P0(1)=P0(P(1))P0(1)=P0(1)P0(1)=E[N]E[]:YNN1Example5.17.EverytimeSpringfieldWildcatsplayintheSuperbowl,theirchanceofwinningisp2(0;1).ThenumberofyearsbetweentwoSuperbowlstheygettoplayinhasthePoissondistributionp(),>0.WhatistheexpectednumberofyearsYbetweentheconsequtiveSuperbowlwins?Letfngn2Nbethesequenceofindependentp()-randomvariablesmodelingthenumberofyearsbetweenconsecutiveSuperbowlappearancesbytheWildcat.Moreover,letNbeageometricg(p)randomvariablewithsuccessprobabilityp.ThenXNY=k:k=0Indeed,everytimetheWildcatslosetheSuperbowl,another
yearshavetopassbeforetheygetanotherchanceandthewholethingstopswhentheyfinallywin.TocomputetheexpectationofYweuseCorollary5.161pE[Y]=E[N]E[k]=:pLastUpdated:December24,201047IntrotoStochasticProcesses:LectureNotes Chapter6Randomwalks-advancedmethods6.1StoppingtimesThelastapplicationofgeneratingfunctionsdealtwithsumsevaluatedbetween0andsomerandomtimeN.AnespeciallyinterestingcaseoccurswhenthevalueofNdependsdirectlyontheevolutionoftheunderlyingstochasticprocess.Evenmoreimportantisthecasewheretime’sarrowistakenintoaccount.IfyouthinkofNasthetimeyoustopaddingnewtermstothesum,itisusuallythecasethatyouarenotallowed(able)toseethevaluesofthetermsyouwouldgetifyoucontinuedadding.Thinkofaninvestorinthestockmarket.Herdecisiontostopandsellherstockscandependonlyontheinformationavailableuptothemomentofthedecision.Otherwise,shewouldsellattheabsolutemaximumandbuyattheabsoluteminimum,makingtonsofmoneyintheprocess.Ofcourse,thisisnotpossibleunlessyouareclairvoyant,sothemeremortalshavetorestricttheirchoicestoso-calledstoppingtimes.Definition6.1.LetfXngn2N0beastochasticprocess.ArandomvariableTtakingvaluesinN0[f+1gissaidtobeastoppingtimewithrespecttofXngn2N0ifforeachn2N0thereexistsafunctionGn:Rn+1!f0;1gsuchthat1=Gn(X;X;:::;X);foralln2N:fT=ng01n0ThefunctionsGnarecalledthedecisionfunctions,andshouldbethoughtofasablackboxwhichtakesthevaluesoftheprocessfXngn2N0observeduptothepresentpointandoutputseither0or1.Thevalue0meanskeepgoingand1meansstop.Thewholepointisthatthedecisionhastobasedonlyontheavailableobservationsandnotonthefutureones.Example6.2.1.Thesimplestexamplesofstoppingtimesare(non-random)deterministictimes.JustsetT=5(orT=723orT=n0foranyn02N0[f+1g),nomatterwhatthestateoftheworld!2is.Thefamilyofdecisionrulesiseasytoconstruct:(n1;n=n0;G(x0;x1;:::;xn)=:0;n6=n0:DecisionfunctionsGndonotdependonthevaluesofX0;X1;:::;Xnatall.Agamblerwhostopsgamblingafter20games,nomatterofwhatthewinningsoflossesareusessucharule.48 CHAPTER6.RANDOMWALKS-ADVANCEDMETHODS2.Probablythemostwell-knownexamplesofstoppingtimesare(first)hittingtimes.Theycanbedefinedforgeneralstochasticprocesses,butwewillsticktosimplerandomwalksPnforthepurposesofthisexample.So,letXn=k=0kbeasimplerandomwalk,andletTlbethefirsttimeXhitsthelevell2N.Moreprecisely,weusethefollowingslightlynon-intuitivebutmathematicallycorrectdefinitionTl=minfn2N0:Xn=lg:Thesetfn2N0:Xn=lgisthecollectionofalltime-pointsatwhichXvisitsthelevell.Theearliestone-theminimumofthatset-isthefirsthittingtimeofl.Instatesoftheworld!2inwhichthelevelljustnevergetreached,i.e.,whenfn2N0:Xn=lgisanemptyset,wesetTl(!)=+1.InordertoshowthatTlisindeedastoppingtime,weneedtoconstructthedecisionfunctionsGn,n2N0.Letusstartwithn=0.WewouldhaveTl=0inthe(impossible)caseX0=l,sowealwayshaveG0(X0)=0.Howaboutn2N.ForthevalueofTltobeequaltoexactlyn,twothingsmusthappen:(a)Xn=l(thelevellmustactuallybehitattimen),and(b)Xn16=l,Xn26=l,...,X16=l,X06=l(thelevellhasnotbeenhitbefore).Therefore,(n1;x06=l;x16=l;:::;xn16=l;xn=lG(x0;x1;:::;xn)=0;otherwise:ThehittingtimeT2ofthelevell=2foraparticulartrajectoryofasymmetricsimplerandomwalkisdepictedbelow:64251015202530-2T2TM-4-6:3.Howaboutsomethingthatisnotastoppingtime?Letn0beanarbitrarytime-horizonandletTMbethelasttimeduring0;:::;n0thattherandomwalkvisitsitsmaximumduring0;:::;n0(seepictureabove).Ifyouboughtastockattimet=0,hadtosellitsometimebeforen0andhadtheabilitytopredictthefuture,thisisoneofthepointsyouwouldchoosetosellitat.Ofcourse,itisimpossibletodecidewhetherTM=n,forsomen20;:::;n01withouttheknowledgeofthevaluesoftherandomwalkaftern.Moreprecisely,letussketchtheproofofthefactthatTMisnotastoppingtime.Suppose,tothecontrary,thatitis,andletGnbethefamilyofdecisionfunctions.Considerthefollowingtwotrajectories:(0;1;2;3;:::;n1;n)and(0;1;2;3;:::;n1;n2).ThedifferonlyinthedirectionoftheLastUpdated:December24,201049IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODSlaststep.TheyalsodifferinthefactthatTM=nforthefirstoneandTM=n1forthesecondone.Ontheotherhand,bythedefinitionofthedecisionfunctions,wehave1=Gn1(X;:::;X):fTM=n1g0n1Theright-handsideisequalforbothtrajectories,whiletheleft-handsideequalsto0forthefirstoneand1forthesecondone.Acontradiction.6.2Wald’sidentityIIHavingdefinedthenotionofastoppingtime,letusetrytocomputesomethingaboutit.Therandomvariablesfngn2Ninthestatementofthetheorembelowareonlyassumedtobein-dependentofeachotherandidenticallydistributed.Tomakethingssimpler,youcanthinkoffngn2Nasincrementsofasimplerandomwalk.Beforewestatethemainresult,hereisanextremelyusefulidentity:Proposition6.3.LetNbeanN0-valuedrandomvariable.ThenX1E[N]=P[Nk]:k=1PProof.Clearly,P[Nk]=P[N=j],so(notewhathappenstotheindiceswhenweswitchjkthesums)X1X1XP[Nk]=P[N=j]k=1k=1jkX1XjX1=P[n=j]=jP[N=j]j=1k=1j=1=E[N]:Theorem6.4(Wald’sIdentityII).Letfngn2Nbeasequenceofindependent,identicallydis-tributedrandomvariableswithE[j1j]<1.SetXnXn=k;n2N0:k=1IfTisanfXngn2N0-stoppingtimesuchthatE[T]<1,thenE[XT]=E[1]E[T]:PTProof.Hereisanotherwayofwritingthesumk=1k:XTX1k=k1fkTg:k=1k=1LastUpdated:December24,201050IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODSTheideabehinditissimple:addallthevaluesofkforkTandkeepaddingzeros(sincePk1fkTg=0fork>T)afterthat.TakingexpectationofbothsidesandswitchingEand(thiscanbejustified,buttheargumentistechnicalandweomitithere)yields:XTX1E[k]=E[1fkTgk]:(6.1)k=1k=1LetusexaminethetermE[k1fkTg]insomedetail.WefirstnotethatXk11fkTg=11fk>Tg=11fk1Tg=11fT=jg:j=0Therefore,Xk1E[k1fkTg]=E[k]E[k1fT=jg]:j=0BytheassumptionthatTisastoppingtime,theindicator1fT=jgcanberepresentedas1fT=jg=Gj(X0;:::;Xj),and,becauseeachXiisjustasumoftheincrements,wecanactuallywrite1fT=jgasafunctionof1;:::;jonly-say1fT=jg=Hj(1;:::;j).Bytheindependenceof(1;:::;j)fromk(becausejx.Theclassical“Gambler’sruin”problemasksthefollowingquestion:whatistheprobabilitythatthegamblerwillmakeadollarsbeforehegoesbankrupt?LastUpdated:December24,201051IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODSGambler’swealthfWngn2NismodelledbyasimplerandomwalkstartingfromPx,whosenincrementsk=WkWk1arecoin-tosses.ThenWn=x+Xn,whereXn=k=0k,n2N0.LetTbethetimethegamblerstops.WecanrepresentTintwodifferent(butequivalent)ways.Ontheonehand,wecanthinkofTasthesmallerofthetwohittingtimesTxandTaxofthelevelsxandaxfortherandomwalkfXngn2N0(rememberthatWn=x+Xn,sothesetwocorrespondtothehittingtimesfortheprocessfWngn2N0ofthelevels0anda).Ontheotherhand,wecanthinkofTasthefirsthittingtimeofthetwo-elementsetfx;axgfortheprocessfXngn2N0.Ineithercase,itisquiteclearthatTisastoppingtime(canyouwritedownthedecisionfunctions?).Wewillseelaterthattheprobabilitythatthegambler’swealthwillremainstrictlybetween0andaforeveriszero,soP[T<1]=1.Moreover,wewillprovethatE[T]<1.WhatcanwesayabouttherandomvariableXT-thegambler’swealth(minusx)attherandomtimeT?Clearly,itiseitherequaltoxortoax,andtheprobabilitiesp0andpawithwhichittakesthesevaluesareexactlywhatweareafterinthisproblem.Weknowthat,sincetherearenoothervaluesXTcantake,wemusthavep0+pa=1.Wald’sidentitygivesusthesecondequationforp0andpa:E[XT]=E[1]E[T]=0
E[T]=0;so0=E[XT]=p0(x)+pa(ax):Thesetwolinearequationswithtwounknownsyieldaxxp0=;pa=:aaItisremarkablethatthetwoprobabilitiesareproportionaltotheamountsofmoneythegamblerneedstomake(lose)inthetwooutcomes.Thesituationisdifferentwhenp6=1.26.3ThedistributionofthefirsthittingtimeT16.3.1ArecursiveformulaLetfXngn2N0beasimplerandomwalk,withtheprobabilitypofsteppingup.LetT1=minfn2N0:Xn=1gbethefirsthittingtimeoflevell=1,andletfpngn2N0beitspmf,i.e.,pn=P[T1=n],n2N0.Thegoalofthissectionistousethepowerfulgenerating-functionmethodstofindfpngn2N0.Youcannotgetfrom0to1inanevennumberofsteps,sop2n=0,n2N0.Also,p1=p-youjusthavetogouponthefirststep.Whataboutn>1?Inordertogofrom0to1inn>1steps(andnotbefore!)thefirststepneedstobedownandthenyouneedtoclimbupfrom1to1inn1steps.Climbingfrom1to1isexactlythesameasclimbingfrom1to0andthenclimbingfrom0to1.Ifittookjstepstogofrom1to0itwillhavetotaken1jstepstogofrom1to2,wherejcanbeanythingfrom1ton2,inordertofinishthejobinexactlyn1LastUpdated:December24,201052IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODSsteps.So,informulas,wehaveP[T1=n]=nX2=qP[“exactlyjstepstofirsthit0from1”and“exactlyn1jstepstofirsthit1from0”]:j=1(6.2)Takingjstepsfrom1to0isexactlythesameastakingjstepsfrom0to1,soP[“exactlyjstepstofirsthit0from1”]=P[T1=j]=pj:Bythesametoken,P[“exactlyn1jstepstofirsthit1from0”]=P[T1=n1j]=pn1j:Finally,Iclaimthatthetwoeventsareindependentofeachother1.Indeed,oncewehavereached0,thefutureincrementsoftherandomwalkbehaveexactlythesameastheincrementsofafreshrandomwalkstartingfromzero-theyareindependentofeverything.Equivalently,aknowledgeofeverythingthathappeneduntilthemomenttherandomwalkhit0forthefirsttimedoesnotchangeourperception(andestimation)ofwhatisgoingtohappenlater-inthiscasethelikelihoodofhitting1inexactlyn1jsteps.ThispropertyiscalledtheregenerationpropertyorthestrongLévypropertyofrandomwalks.Moreprecisely(butstillnotentirelyprecise),wecanmakethefollowingclaim:LetfXngn2N0beasimplerandomwalkandletTbeanyN0-valuedstoppingtime.DefinetheprocessfYngn2N0byYn=XT+nXT.ThenfYngn2N0isalsoasimplerandomwalk,anditisindependentofXuptoT.Inordertocheckyourunderstanding,trytoconvinceyourselfthattherequirementthatTbeastoppingtimeisnecessary-findanexampleofarandomtimeTwhichisnotastoppingtimewherethestatementabovefails.WecangobacktothedistributionofthehittingtimeT1,anduseournewly-foundindepen-dencetogetherwith(6.2)toobtainthefollowingrecursionnX2pn=qpjpnj1;n>1;p0=0;p1=p:(6.3)j=16.3.2Generating-functionapproachThisiswheregeneratingfunctionsstepin.Wewilluse(6.3)toderiveanequationfortheP1kgeneratingfunctionP(s)=k=0pks.Thesumontheright-handsideof(6.3)looksalittlebitlikeaconvolution,soletuscompareittothefollowingexpansionofthesquareP(s)2:X1XkP(s)2=(pp)sk:ikik=0i=01Ademandingreaderwillobjectatthispoint,sincemydefinitionsofthetwoeventsaresomewhatloose.Ibegforgiveness.LastUpdated:December24,201053IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODSPkTheinnersumi=0pipkineedstobesplitintoseveralpartstogetanexpressionwhichmatches(6.3):XkXk1(k+1)X2pp=pp+pp+pp=pp=q1p;k2:iki|0{zk}iki|k{z}0i(k+1)i1k+1i=0i=1i=100Therefore,sincethecoefficientsofP(s)2startats2,wehaveX1X1qsP(s)2=qsq1psk=psk+1=P(s)ps;k+1k+1k=2k=2whichisnothingbutaquadraticequationforP.Itadmitstwosolutions(foreachs):p114pqs2P(s)=:2qsOneofthetwosolutionsisalwaysgreaterthan1inabsolutevalue,soitcannotcorrespondtoavalueofageneratingfunction,soweconcludethatp114pqs21P(s)=;forjsjp:2qs2pqItremainstoextracttheinformationaboutfpngn2N0fromP.TheobviouswaytodoitistocomputehigherandhigherderivativesofPands=1.Thereisaneasierway,though.ThesquarerootappearingintheformulaforPisanexpressionoftheform(1+x)1=2andthe(generalized)binomialformulacanbeused:1X(1):::(k+1)(1+x)=x;where=;k2N;2R:kkk!k=0Therefore,11X111=2X111=2P(s)=(4pqs2)k=s2k1(4pq)k(1)k1;(6.4)2qs2qs2qk2pkk=0k=1andso1kk11=2p2k1=(4pq)(1);p2k2=0;k2N:2qk
1=2Thisexpressioncanbesimplifiedabitfurther:theformulaforevaluatesto:k1=2k1112k3=(1):k4k1kk2Thus,kk122k3p2k1=pq:kk2Thislastexpressionmightremindyouofsomethingrelatedtothereflectionprinciple.Anditis!Canyouderivetheformulaforp2k1fromthereflectionprinciple?Howwouldyoudealwiththefactthattherandomwalkhereisnotsymmetric?LastUpdated:December24,201054IntrotoStochasticProcesses:LectureNotes CHAPTER6.RANDOMWALKS-ADVANCEDMETHODS6.3.3Doweactuallyhit1soonerorlater?WhathappensifwetrytoevaluateP(1)?Weshouldget1,right?Infact,whatwegetisthefollowing:(p114pq1jpqj1;p1P(1)===22q2qp;p<1q2Clearly,P(1)<1whenp0.Itisremarkablethatifp=1,therandomwalkwillalwayshit1soonerorlater,12butthisdoesnotneedtohappenifp<1.Whatwehavehereisanexampleofaphenomenon2knownascriticality:manyphysicalsystemsexhibitqualitativelydifferentbehaviordependingonwhetherthevalueofcertainparameterpliesaboveorbelowcertaincriticalvaluep=pc.6.3.4Expectedtimeuntilwehit1?Anotherquestionthatgeneratingfunctionscanhelpupansweristhefollowingone:howlong,onaverage,doweneedtowaitbefore1ishit?Whenp<1P[T=+1]>0,sowecanimmediately21concludethatE[T]=+1,bydefinition.Thecasep1ismoreinteresting.Followingthe12recipefromthelectureongeneratingfunctions,wecomputethederivativeofP(s)andgetp02p114pqs2P(s)=p:14pqs22qs2Whenp=1,weget2p0111s2limP(s)=limp=+1;s%1s%11s2s2andconcludethatE[T1]=+1.Forp>1,thesituationislesssevere:201limP(s)=:s%1pqWecansummarizethesituationinthefollowingtableP[T1<1]E[T1]p<1p+12qp=11+12p>1112pqLastUpdated:December24,201055IntrotoStochasticProcesses:LectureNotes Chapter7Branchingprocesses7.1AbitofhistoryInthemid19thcenturyseveralaristocraticfamiliesinVictorianEnglandrealizedthattheirfamilynamescouldbecomeextinct.Wasitjustunfoundedparanoia,ordidsomethingrealpromptthemtocometothisconclusion?Theydecidedtoaskaround,andSirFrancisGalton(a“polymath,anthropologist,eugenicist,tropicalexplorer,geographer,inventor,meteorologist,proto-geneticist,psychometricianandstatistician”andhalf-cousinofCharlesDarwin)posedthefollowingquestion(1873,Educa-tionalTimes):Howmanymalechildren(onaverage)musteachgenerationofafamilyhaveinorderforthefamilynametocontinueinperpetuity?ThefirstcompleteanswercamefromReverendHenryWilliamWatsonsoonafter,andthetwowroteajointpaperentitledOneSirFrancisGaltontheprobabilityofextinctionoffamiliesin1874.Bytheendofthislecture,youwillbeabletogiveapreciseanswertoGalton’squestion.7.2AmathematicalmodelThemodelproposedbyWatsonwasthefollowing:1.Apopulationstartswithoneindividualattimen=0:Z0=1.2.Afteroneunitoftime(attimen=1)thesoleindividualproducesZ1identicalclonesofitselfanddies.Z1isanN0-valuedrandomvariable.3.(a)IfZ1happenstobeequalto0thepopulationisdeadandnothinghappensatanyfuturetimen2.56 CHAPTER7.BRANCHINGPROCESSES(b)IfZ1>0,aunitoftimelater,eachofZ1individualsgivesbirthtoarandomnumberofchildrenanddies.ThefirstonehasZ1;1children,thesecondoneZ1;2children,etc.Thelast,Z1thone,givesbirthtoZ1;Z1children.Weassumethatthedistributionofthenumberofchildrenisthesameforeachindividualineverygenerationandindependentofeitherthenumberofindividualsinthegenerationandofthenumberofchildrentheothershave.Thisdistribution,sharedbyallZn;iandZ1,iscalledtheoffspringdistribution.ThetotalnumberofindividualsinthesecondgenerationisnowXZ1Z2=Z1;k:k=1(c)Thethird,fourth,etc.generationsareproducedinthesameway.IfiteverhappensthatZn=0,forsomen,thenZm=0forallmn-thepopulationisextinct.Otherwise,XZnZn+1=Zn;k:k=1Definition7.1.Astochasticprocesswiththepropertiesdescribedin(1),(2)and(3)aboveiscalleda(simple)branchingprocess.Themechanismthatproducesthenextgenerationfromthepresentonecandifferfromap-plicationtoapplication.Itistheoffspringdistributionalonethatdeterminestheevolutionofabranchingprocess.Withthisnewformalism,wecanposeGalton’squestionmoreprecisely:UnderwhatconditionsontheoffspringdistributionwilltheprocessfZngn2N0nevergoextinct,i.e.,whendoesP[Zn1foralln2N0]=1(7.1)hold?7.3ConstructionandsimulationofbranchingprocessesBeforeweanswerGalton’squestion,letusfigureouthowtosimulateabranchingprocess,foragivenoffspringdistributionfpngn2N0(pk=P[Z1=k]).Thedistributionfpngn2N0isN0-valued-wehavelearnedhowtosimulatesuchdistributionsinLecture3.Wecan,therefore,assumethatatransformationfunctionFisknown,i.e.,thattherandomvariable=F()isN0-valuedwithpmffpngn2N0,whereU[0;1].Sometimeagoweassumedthataprobabilityspacewithasequencefngn2N0ofindependentU[0;1]randomvariablesisgiven.Wethinkoffngn2N0asasequenceofrandomnumbersproducedbyacomputer.LetusfirstapplythefunctionFtoeachmemberoffngn2N0toobtainanindependentsequencefngn2N0ofN0-valuedrandomvariableswithpmffpngn2N0.Inthecaseofasimplerandomwalk,wewouldbedoneatthispoint-anaccumulationofthefirstnelementsoffngn2N0wouldgiveyouthevalueXnoftherandomwalkattimen.Branchingprocessesareabitmorecomplicated;theincrementZn+1ZndependsonZn:themoreLastUpdated:December24,201057IntrotoStochasticProcesses:LectureNotes CHAPTER7.BRANCHINGPROCESSESindividualsinageneration,themoreoffspringtheywillproduce.Inotherwords,weneedablackboxwithtwoinputs-“randomness”andZn-whichwillproduceZn+1.Whatdowemeanby“randomness”?Ideally,wewouldneedexactlyZn(unused)elementsoffngn2N0tosimulatethenumberofchildrenforeachofZnmembersofgenerationn.Thisisexactlyhowonewoulddoitinpractice:giventhesizeZnofgenerationn,onewoulddrawZnsimulationsfromthedistributionfpngn2N0,andsumuptheresultstogetZn+1.Mathematically,itiseasiertobemorewasteful.Thesequencefngn2N0canberearrangedintoadoublesequence1fZn;ign2N0;i2N.Inwords,insteadofonesequenceofindependentrandomvariableswithpmffpngn2N0,wehaveasequenceofsequences.Suchanabundanceallowsustofeedthewhole“row”fZn;igi2NintotheblackboxwhichproducesZn+1fromZn.YoucanthinkofZn;iasthenumberofchildrentheithindividualinthenthgenerationwouldhavehadhebeenborn.TheblackboxusesonlythefirstZnelementsoffZn;igi2Nanddiscardstherest:XZnZ0=1;Zn+1=Zn;i;i=1whereallfZn;ign2N0;i2Nareindependentofeachotherandhavethesamedistributionwithpmffpngn2N0.OncewelearnabitmoreabouttheprobabilisticstructureoffZngn2N0,wewilldescribeanotherwaytosimulateit.7.4Agenerating-functionapproachHavingdefinedandconstructedabranchingprocesswithoffspringdistributionfZngn2N0,letusanalyzeitsprobabilisticstructure.Thefirstquestiontheneedstobeansweredisthefollowing:WhatisthedistributionofZn,forn2N0?ItisclearthatZnmustbeN0-valued,soitsdistributioniscompletelydescribedbyitspmf,whichis,inturn,completelydeterminedbyitsgeneratingfunction.WhileanexplicitexpressionforthepmfofZnmaynotbeavailable,itsgeneratingfunctioncanalwaysbecomputed:Proposition7.2.LetfZngn2N0beabranchingprocess,andletthegeneratingfunctionofitsoffspringdistributionfpngn2N0begivenbyP(s).ThenthegeneratingfunctionofZnisthen-foldcompositionofPwithitself,i.e.,PZn(s)=P(P(:::P(s):::));forn1:|{z}nP’sProof.Forn=1,thedistributionofZ1isexactlyfpngn2N0,soPZ1=P(s).Supposethatthestatementofthepropositionholdsforsomen2N.ThenXZnZn+1=Zi;n;i=1canbeviewedasarandomsumofZnindependentrandomvariableswithpmffpngn2N0,wherethenumberofsummandsZnisindependentoffZn;igi2N.ByProposition5.16inthelectureon1Canyoufindaone-to-oneandontomappingfromNintoNN?LastUpdated:December24,201058IntrotoStochasticProcesses:LectureNotes CHAPTER7.BRANCHINGPROCESSESgeneratingfunctions,wehaveseenthatthegeneratingfunctionPZn+1ofZn+1isacompositionofthegeneratingfunctionP(s)ofeachofthesummandsandthegeneratingfunctionPZnoftherandomtimeZn.Therefore,PZn+1(s)=PZn(P(s))=P(P(:::P(P(s)):::)));|{z}n+1P’sandthefullstatementofthePropositionfollowsbyinduction.LetususeProposition7.2insomesimpleexamples.Example7.3.LetfZngn2N0beabranchingprocesswithoffspringdistributionfpngn2N0.Inthefirstthreeexamplesnorandomnessoccursandthepopulationgrowthcanbedescribedexactly.Intheotherexamples,moreinsterestingthingshappen.1.p0=1,pn=0,n2N:InthiscaseZ0=1andZn=0foralln2N.Thisinfertilepopulationdiesafterthefirstgeneration.2.p0=0;p1=1;pn=0,n2:Eachindividualproducesexactlyonechildbeforehe/shedies.Thepopulationsizeisalways1:Zn=1,n2N0.3.p0=0;p1=0;:::;pk=1;pn=0,nk,forsomek2:Here,therearekkidsperindividual,sothepopulationgrowsexponentially:P(s)=sk,soP(s)=((:::(sk)k:::)k)k=skn.Therefore,Z=kn,forn2N.Znn4.p0=p;p1=q=1p;pn=0,n2:Eachindividualtossesa(abiased)coinandhasonechildoftheoutcomeisheadsordieschildlessiftheoutcomeistails.ThegeneratingfunctionoftheoffspringdistributionisP(s)=p+qs.Therefore,PZn(s)=(p+q(p+q(p+q(:::(p+qs))))):|{z}npairsofparenthesesTheexpressionabovecanbesimplifiedconsiderably.Oneneedstorealizetwothings:(a)Afteralltheproductsaboveareexpanded,theresultingexpressionmustbeoftheformA+Bs,forsomeA;B.IfyouinspecttheexpressionforPZnevenmoreclosely,youwillseethatthecoefficientBnexttosisjustqn.(b)PZnisageneratingfunctionofaprobabilitydistribution,soA+B=1.Therefore,P(s)=(1qn)+qns:ZnOfcourse,thevalueofZnwillbeequalto1ifandonlyifallofthecoin-tossesofitsancestorsturnedouttobeheads.Theprobabilityofthateventisqn.Sowedidn’tneedProposition7.2afterall.LastUpdated:December24,201059IntrotoStochasticProcesses:LectureNotes CHAPTER7.BRANCHINGPROCESSESThisexamplecanbeinterpretedalternativelyasfollows.Eachindividualhasexactlyonechild,butitsgenderisdeterminedatrandom-malewithprobabilityqandfemalewithprobabilityp.Assumingthatallfemaleschangetheirlastnamewhentheymarry,andassumingthatallofthemmarry,Znisjustthenumberofindividualscarryingthefamilynameafterngenerations.5.p0=p2;p1=2pq;p2=q2;pn=0,n3:Inthiscaseeachindividualhasexactlytwochildrenandtheirgenderisfemalewithprob-abilitypandmalewithprobabilityq,independentlyofeachother.ThegeneratingfunctionPoftheoffspringdistributionfpngn2NisgivenbyP(s)=(p+qs)2.ThenP=(p+q(p+q(:::p+qs)2:::)2)2:Zn|{z}npairsofparenthesesUnliketheexampleabove,itisnotsoeasytosimplifytheaboveexpression.Proposition7.2canbeusedtocomputethemeanandvarianceofthepopulationsizeZn,forn2N.Proposition7.4.Letfpngn2N0beapmfoftheoffpsringdistributionofabranchingprocessfZngn2N0.Iffpngn2N0admitsanexpectation,i.e.,ifX1=kpk<1;k=0thenE[Z]=n:(7.2)nIfthevarianceoffpngn2N0isalsofinite,i.e.,ifX12=(k)2p<1;kk=0then(n+12n1;6=1;Var[Z]=2n(1++2+


+n)=1(7.3)n2(n+1);=1Proof.SincethedistributionofZ1isjustfpngn2N0,itisclearthatE[Z1]=andVar[Z1]=2.Weproceedbyinductionandassumethattheformulas(7.2)and(7.3)holdforn2N.ByProposition7.2,thegeneratingfunctionPZn+1isgivenasacompositionPZn+1(s)=PZn(P(s)).Therefore,ifweusetheidentityE[Zn+1]=P0(1),wegetZn+1P0(1)=P0(P(1))P0(1)=P0(1)P0(1)=E[Z]E[Z]=n=n+1:Zn+1ZnZnn1Asimilar(butmorecomplicatedandlessilluminating)argumentcanbeusedtoestablish(7.3).LastUpdated:December24,201060IntrotoStochasticProcesses:LectureNotes CHAPTER7.BRANCHINGPROCESSES7.5ExtinctionprobabilityWenowturntothecentralquestion(theoneposedbyGalton).Wedefineextinctiontobethefollowingevent:E=f!2:Zn(!)=0forsomen2Ng:ItisthepropertyofthebranchingprocessthatZm=0forallmnwheneverZn=0.Therefore,wecanwriteEasanincreasingunionofsetsEn,whereEn=f!2:Zn(!)=0g:Therefore,thesequencefP[En]gn2Nisnon-decreasingand“continuityofprobability”(seetheveryfirstlecture)impliesthatP[E]=limP[En]:n2NThenumberP[E]iscalledtheextinctionprobability.Usinggeneratingfunctions,and,inpartic-ular,thefactthatP[En]=P[Zn=0]=PZn(0)wegetP[E]=limPZn(0)=limP(P(:::P(0):::)):n2Nn2N|{z}nP’sItisamazingthatthisprobabilitycanbecomputed,eveniftheexplicitformofthegeneratingfunctionPZnisnotknown.Proposition7.5.Theextinctionprobabilityp=P[E]isthesmallestnon-negativesolutionoftheequationx=P(x);calledtheextinctionequation,wherePisthegeneratingfunctionoftheoffspringdistribution.Proof.Letusshowfirstthatp=P[E]isasolutionoftheequationx=P(x).Indeed,Pisacontinuousfunction,soP(limn!1xn)=limn!1P(xn)foreveryconvergentsequencefxngn2N0in[0;1]withxn!x1.Letustakeaparticularsequencegivenbyxn=P(P(:::P(0):::)):|{z}nP’sThen1.p=P[E]=limn2Nxn,and2.P(xn)=xn+1.Therefore,p=limxn=limxn+1=limP(xn)=P(limxn)=P(p);n!1n!1n!1n!1andsopsolvestheequationP(x)=x.Thefactthatp=P[E]isthesmallestsolutionofx=P(x)on[0;1]isabittrickiertoget.Letp0beanothersolutionofx=P(x)on[0;1].Since0p0andPisanon-decreasiingfunction,wehaveP(0)P(p0)=p0:LastUpdated:December24,201061IntrotoStochasticProcesses:LectureNotes CHAPTER7.BRANCHINGPROCESSESWecanapplythefunctionPtobothsidesoftheinequalityabovetogetP(P(0))P(P(p0))=P(p0)=p0:ContinuinginthesamewaywegetP[E]=P(P(:::P(0):::))p0;n|{z}nP’wegetp=P[E]=limn2NP[En]limn2Np0=p0,sopisnotlargerthenanyothersolutionp0ofx=P(x).Example7.6.LetuscomputeextinctionprobabilitiesinthecasesfromExample7.3.1.p0=1,pn=0,n2N:Noneedtouseanytheorems.P[E]=1inthiscase.2.p0=0;p1=1;pn=0,n2:Likeabove,thesituationisclear-P[E]=0.3.p0=0;p1=0;:::;pk=1;pn=0,nk,forsomek2:Noextinctionhere-P[E]=0.4.p0=p;p1=q=1p;pn=0,n2:SinceP(s)=p+qs,theextinctionequationiss=p+qs.Ifp=0,theonlysolutioniss=0,sonoextinctionoccurs.Ifp>0,theonlysolutioniss=1-theextinctionisguaranteed.Itisinterestingtonotethejumpintheextinctionprobabilityaspchangesfrom0toapositivenumber.5.p0=p2;p1=2pq;p2=q2;pn=0,n3:HereP(s)=(p+qs)2,sotheextinctionequationreadss=(p+qs)2:p2Thisisaquadraticinsanditssolutionsares1=1ands2=q2,ifweassumethatq>0.Whenp0.TheMarkovpropertyistypicallycheckedinthefollowingway:onecomputestheleft-handsideof(8.1)andshowsthatitsvaluedoesnotdependonin1;in2;:::;i1;i0(whyisthatenough?).AconditionP[Xn=in;:::;X0=i0]>0willbeassumed(withoutexplicitmention)everytimewewriteaconditionalexpressionliketoonein(8.1).Allchainsinthiscoursewillbehomogeneous,i.e.,theconditionalprobabilitiesP[Xn+1=jjXn=i]willnotdependonthecurrenttimen2N0,i.e.,P[Xn+1=jjXn=i]=P[Xm+1=jjXm=i],form;n2N0.Markovchainsare(relatively)easytoworkwithbecausetheMarkovpropertyallowsustocomputealltheprobabilities,expectations,etc.wemightbeinterestedinbyusingonlytwoingredients.(0)(0)(0)1.Initialprobabilitya=fai:i2Sg,ai=P[X0=i]-theinitialprobabilitydistributionoftheprocess,and2.Transitionprobabilitiespij=P[Xn+1=jjXn=i]-themechanismthattheprocessusestojumparound.63 CHAPTER8.MARKOVCHAINS(0)Indeed,ifoneknowsallaiandallpij,andwantstocomputeajointdistributionP[Xn=in;Xn1=in1;:::;X0=i0],oneneedstousethedefinitionofconditionalprobabilityandtheMarkovpropertyseveraltimes(themultiplicationtheoremfromyourelementaryprobabilitycourse)togetP[Xn=in;:::;X0=i0]=P[Xn=injXn1=in1;:::;X0=i0]P[Xn1=in1;:::;X0=i0]=P[Xn=injXn1=in1]P[Xn1=in1;:::;X0=i0]=pin1inP[Xn1=in1;:::;X0=i0]Repeatingthesameprocedure,weget(0)P[Xn=in;:::;X0=i0]=pin1inpin2in1


pi0i1ai0:WhenSisfinite,thereisnolossofgeneralityinassumingthatS=f1;2;:::;ng,andthenweusuallyorganizetheentriesofa(0)intoarowvector(0)(0)(0)(0)a=(a1;a2;:::;an);andthetransitionprobabilitiespijintoasquarematrixP,where23p11p12:::p1n66p21p22:::p2n77P=6........74....5pn1pn2:::pnnInthegeneralcase(Spossiblyinfinite),onecanstillusethevectorandmatrixnotationasbefore,butitbecomesquiteclumsyinthegeneralcase.Forexample,ifS=Z,Pisaninfinitematrix23...............6766:::p11p10p11:::77P=66:::p01p00p01:::7764:::p11p10p11:::75...............8.2ExamplesHerearesomeexamplesofMarkovchains-foreachonewewritedownthetransitionmatrix.Theinitialdistributionissometimesleftunspecifiedbecauseitdoesnotreallychangeanything.1.RandomwalksLetfXngn2N0beasimplerandomwalk.LetusshowthatitindeedhasPntheMarkovproperty(8.1).Remember,first,thatXn=k=1k,wherekareindependentcoin-tosses.Forachoiceofi0;:::;in+1(suchthati0=0andik+1ik=1)wehaveP[Xn+1=in+1jXn=in;Xn1=in1;:::;X1=i1;X0=i0]=P[Xn+1Xn=in+1injXn=in;Xn1=in1;:::;X1=i1;X0=i0]=P[n+1=in+1injXn=in;Xn1=in1;:::;X1=i1;X0=i0]=P[n+1=in+1in];LastUpdated:December24,201064IntrotoStochasticProcesses:LectureNotes CHAPTER8.MARKOVCHAINSwherethelastequalityfollowsfromthefactthattheincrementn+1isidependentofthepreviousincrements,and,therefore,ofthevaluesofX1;X2;:::;Xn.Thelastlineabovedoesnotdependonin1;:::;i1;i0,soXindeedhastheMarkovproperty.ThestatespaceSoffXngn2N0isthesetZofallintegers,andtheinitialdistributiona(0)(0)(0)isverysimple:westartat0withprobability1(sothata0=1andai=0,fori6=0.).Thetransitionprobabilitiesaresimpletowritedown8>:0;otherwise.Thesecanbewrittendowninaninfinitematrix,23.....................676:::0P000:::7676:::q0p00:::7676:::0q0p0:::7P=6766:::00q0p:::7766:::000q0:::7764:::0000q:::75........................butitdoesnothelpourunderstandingmuch.2.BranchingprocessesLetfXngn2N0beasimpleBranchingprocesswiththebranchingPdistributionfpngn2N0.Asyousurelyremember,itisconstructedasfollows:X0=1andXn+1=Xnk=1Xn;k,wherefXn;kgn2N0;k2Nisafamilyofindependentrandomvariableswithdistributionfpngn2N0.ItisnownotverydifficulttoshowthatfXngn2N0isaMarkovchainP[Xn+1=in+1jXn=in;Xn1=in1;:::;X1=i1;X0=i0]XXn=P[Xn;k=in+1jXn=in;Xn1=in1;:::;X1=i1;X0=i0]k=1Xin=P[Xn;k=in+1jXn=in;Xn1=in1;:::;X1=i1;X0=i0]k=1Xin=P[Xn;k=in+1];k=1where,justlikeintherandom-walkcase,thelastequalityfollowsfromthefactthattherandomvariablesXn;k,k2NareindependentofallXm;k,m0,itchoosesanyleafotherthantheoneitissittingonandtheoneitvisitedimmediatelybefore(withequalprobability)andjumpstoit.ThepositionfXngn2N0ofthefrogisnotaMarkovchain.Indeed,wehave1P[X3=1jX2=2;X1=3]=;whileP[X3=1jX2=2;X1=1]=0:N2Amoredramaticversionofthisexamplewouldbetheonewherethefrogremembersalltheleavesithadvisitedbefore,andonlychoosesamongtheremainingonesforthenextjump.7.Makinganon-MarkovchainintoaMarkovchainHowcanweturntheprocessofExample6.intoaMarkovchain.Obviously,theproblemisthatthefroghastorememberthenumberoftheleafitcamefrominordertodecidewheretojumpnext.Thewayoutistomakethisinformationapartofthestate.Inotherwords,weneedtochangethestatespace.InsteadofjustS=f1;2;:::;Ng,wesetS=f(i1;i2):i;j2f1;2;:::Ngg.Inwords,thestateoftheprocesswillnowcontainnotonlythenumberofthecurrentleaf(i.e.,i)butalsothenumeroftheleafwecamefrom(i.e.,j).Thereisabitoffreedomwiththeinitialstate,butwesimplyassumethatwestartfrom(1;1).Startingfromthestate(i;j),thefrogcanjumptoanystateoftheform(k;i),k6=i;j(withequalprobabilities).Notethatsomestateswillneverbevisited(like(i;i)fori6=1),sowecouldhavereducedthestatespacealittlebitrightfromthestart.8.AmorecomplicatedexampleLetfXngn2N0beasimplesymmetricrandomwalk.Theabsolute-valueprocessYn=jXnj,n2N0,isalsoaMarkovchain.Thisprocessesissometimescalledthereflectedrandomwalk.InordertoestablishtheMarkovproperty,weleti0;:::;in+1benon-negativeintegerswithik+1ik=1forall0kn(thestatespaceisS=N0).WeneedtoshowthattheconditionalprobabilityP[jXn+1j=in+1jXnj=in;:::;jX0j=i0](8.2)LastUpdated:December24,201067IntrotoStochasticProcesses:LectureNotes CHAPTER8.MARKOVCHAINSdoesnotdependonin1;:::;i0.WewriteP[jXn+1j=in+1jXnj=in;:::;jX0j=i0]=P[Xn+1=in+1jXnj=in;:::;jX0j=i0](8.3)+P[Xn+1=in+1jXnj=in;:::;jX0j=i0];andconcentrateonthefirstconditionalprobabilityontheright-handside,asummingthatin>0(thecasein=0iseasierandislefttothereaderwhoneedspractice).Letususethelawoftotalprobability(seeProblem1inHW6)withA1=fXn=ing,A2=fXn6=ingandB=fjXnj=in;:::;jX0j=ji0jg.SinceA2B=fXn=ingB,wehaveP[Xn+1=in+1jB]=P[Xn+1=in+1jBA1]P[A1jB]+P[Xn+1=in+1jBA2]P[A2jB]=P[Xn+1=in+1jBfXn=ing]P[Xn=injB]+P[Xn+1=in+1jBfXn=ing]P[Xn=injB]ConditionallyonXn=in,theprobabilitythatXn+1=in+1doesnotdependontheextrainfor-mationBmightcontain.ThereforeP[Xn+1=in+1jBfXn=ing]=P[Xn+1=in+1jXn=in];and,similarly,P[Xn+1=in+1jBfXn=ing]=P[Xn+1=in+1jXn=in]:HowaboutthetermP[Xn=injB](withP[Xn=injB]beingcompletelyanalogous)?IfweshowthatP[Xn=injB]=P[Xn=injXnj=in];(8.4)wewouldbemakinggreatprogress.Thereisarigorouswayofdoingthis,butitisquitetechnicalandnotveryilluminating.Theideaissimple,though:foreverypath(0;X1(!);:::;Xn(!)),theflippedpath(0;X1(!);:::;Xn(!))isequallylikelyandgivesexactlythesamesequenceofabsolutevalues.Therefore,theknowledgeofBdoesnotpermitustodistinguishbetweenthem.Inparticular,forevery(possible)sequenceofabsolutevaluesjx0j=i0;jx1j=i1;:::;jx0j=inthereareasmanyactualpaths(x0;x1;:::;xn)thatendupininasthosethatendupinin.Therefore,1P[Xn=injB]=P[Xn=injXnj=in]=2:Similarly,P[X=ijB]=1.nn2Goingbacktotheinitialexpression(8.4),wehaveP[X=ijB]=1P[X=ijBfX=ig]+1P[X=ijBfX=ig]:n+1n+12n+1n+1nn2n+1n+1nnGiventhatin>0,thefirstconditionalprobabilityaboveequalstoP[Xn+1=in]becauseoftheMarkovproperty;asfarasXn+1isconcerned,theinformationBfXn=ingisthesameasjustfXn=ing).Thesecondconditionalprobabilityis0:itisimpossibleforXn+1tobeequaltoin+1>0ifXn=in<0.Therefore,P[Xn+1=in+1jB]=1=4.AnessentialidenticalargumentshowsthatP[X=ijB]=1=4.ThereforeP[jXj=ijB]=1-whichisindependentn+1n+1n+1n+12LastUpdated:December24,201068IntrotoStochasticProcesses:LectureNotes CHAPTER8.MARKOVCHAINSofin1;:::;i1;i0(itlookslikeitisalsoindependentofinbutitisnot;thisprobabilityisequalto0unlessin+1in=1).9.AmorerealisticexampleInagameoftennis,thescoringsystemisasfollows:bothplayers(letuscallthemAmélieandBjörn)startwiththescoreof0.EachtimeAméliewinsapoint,herscoremovesastepupinthe1840,00(i.e.,P6=),wehaveV=,and10a+b11nn11a101baP=VDV=1b0(1ab)na+b111ba(1ab)naa=+a+bbaa+bbb23b+(1ab)naa(1ab)na4a+ba+ba+ba+b5=b+(1ab)nba(1ab)nba+ba+ba+ba+bTheexpressionforPnabovetellsusalotaboutthestructureofthemulti-stepprobabilities(n)pforlargen.Notethatthesecondmatrixontheright-handsideabovecomesmultipliedbyij(1ab)nwhichtendsto0asn!1,unlessweareintheuninterestingsituationa=b=0or(a=b=1).Therefore,n1abPforlargen:a+babThefactthattherowsoftheright-handsideaboveareequalpointstothefactthat,forlargen,(n)pdoesnotdepend(much)ontheinitialstatei.Inotherwords,thisMarkovchainforgetsitsijinitialconditionafteralongperiodoftime.Thisisarulemorethananexception,andwewillstudysuchphenomenainthefollowinglectures.LastUpdated:December24,201073IntrotoStochasticProcesses:LectureNotes Chapter9The“Stochastics”packageStochasticsisaMathematicapackage(acollectionoffunctions)forvariouscalculations,sim-ulationandvisualizationofMarkovchains.Hereisashortuser’sguide.9.1InstallationYoucandownloadthefileStochastics.mfromthecourseweb-site.Itneedstobeputinadirectory/folderonyoursystemthatMathematicaknowsabout.Theeasiestwaytodothisistotype$PathinMathematica.Theoutputwillbealistoffolders.YousimplycopythefileStochastics.minanyofthefolderslisted.RestartMathematica,andthatisit.EverytimeyouwanttousefunctionsfromStochastics,youissuethecommand<244In[7]:=TransitionMatrix@MyChainD1111Out[7]=::,,0>,80,0,1<,:0,,>>2222In[8]:=MatrixForm@TransitionMatrix@MyChainDDOut[8]//MatrixForm=1102200111022In[9]:=Probability@A,B,3,MyChainD3Out[9]=8In[10]:=Classes@MyChainDOut[10]=88A<,8B,C<>2In[15]:=RMatrix@MyChainD1Out[15]=::,0>>2In[16]:=PMatrix@MyChainD11Out[16]=:80,1<,:,>>22In[19]:=M=CanonicalForm@MyChainD1111Out[19]=:::80,1<,:,>>,880<,80<<>,:::,0>>,::>>>>2222In[20]:=MatrixForm@88MatrixForm@M@@1,1DDD,MatrixForm@M@@1,2DDD<,8MatrixForm@M@@2,1DDD,MatrixForm@M@@2,2DDD<0:79 CHAPTER10.CLASSIFICATIONOFSTATESIntuitively,icommunicateswithjisthereisanon-zerochancethattheMarkovchainXwilleventuallyvisitjifitstartsfromi.Sometimeswealsosaythatjisaconsequentofi,orthatjisaccessiblefromi.Example10.3.Inthetennisexample,everystateisaccessiblefrom(0;0)(thefactthatp2(0;1)isimportanthere),but(0;0)isnotaccessiblefromanyotherstate.Theconsequentsof(40;40)are(40;40)itself,(40;Adv),(Adv;40),“Améliewins”and“Björnwins”.Beforeweexaminesomepropertiesoftherelation!,hereisasimplebutusefulcharac-terization.Beforewegiveit,werecallthefollowingfactaboutprobability:letfAngn2N0beanincreasingsequenceofevents,i.e.,AnAn+1,foralln2N0.ThenP[[n2N0An]=limP[An];nandthesequenceinsidethelimitisnon-decreasing.(n)Proposition10.4.i!jifandonlyifpij>0forsomen2N0.Proof.TheeventA=fj<1gcanbewrittenasanincreasingunionA=[n2NAn;whereAn=fjng:Therefore,Pi[j<1]=Pi[A]=limPi[An]=limPi[jn];nnandthesequencePi[jn],n2Nisnon-decreasing.Inparticular,Pi[j<1]Pi[An];foralln2N:(10.2)(n)Suppose,first,thatpij>0forsomen.Sincejisthefirsttimejisvisited,wehave(n)Pi[An]=Pi[jn]Pi[Xj=n]=pij>0:By(10.2),wehavePi[j<1]>0,andso,i!j.Conversely,supposethati!j,i.e.,Pi[A]>0.SincePi[A]=limnPi[An],wemusthavePi[An]>0forsomen0(andthenalllargern),i.e.,Pi[jn0]>0.Whenjn0,wemusthaveX0=jorX1=jor...orXn=j,i.e.,n0fjn0g[k=0fXk=jg;andsoXn0n000,foratleastonen2f0;1;:::;n0g.Proposition10.5.Foralli;j;k2S,wehaveLastUpdated:December24,201080IntrotoStochasticProcesses:LectureNotes CHAPTER10.CLASSIFICATIONOFSTATES1.i!i,2.i!j;j!k)i!k.Proof.1.Ifwestartfromstatei2Swearealreadythere(notethat0isallowedasavalueforBin(10.1)),i.e.,i=0whenX0=i.(n)2.UsingProposition10.4,itwillbeenoughtoshowthatp>0forsomen2N.Bytheik(n1)(n2)sameProposition,weknowthatpij>0andpjk>0forsomen1;n22N0.BytheChapman-Kolmogorovrelations,withn=n1+n2,wehaveX(n)(n1)(n2)(n1)(n2)p=pppp>0:ikillkijjkl2S(n)(n1)(n2)Remark10.6.Theinequalitypikpilplkisvalidforalli;l;k2S,aslongasn1+n2=n.Itwillcomeinhandylater.10.2ClassesDefinition10.7.WesaythatthestatesiandjinSintercommunicate,denotedbyi$jifi!jandj!i.AsetBSofstatesiscalledirreducibleifi$jforalli;j2S.Unliketherelationofcommunication,therelationofintercommunicationissymmetric.More-over,wehavethefollowingthreeproperties(theresultfollowsdirectlyfromProposition10.4,soweomitit):Proposition10.8.Therelation$isanequivalencerelationofS,i.e.,foralli;j;k2S,wehave1.i$i(reflexivity),2.i$j)j$i(symmetry),and3.i$j;j$k)i$k(transitivity).Thefactthat$isanequivalencerelationallowsustosplitthestate-spaceSintoequivalenceclasseswithrespectto$.Inotherwords,wecanwriteS=S1[S2[S3[:::;whereS1;S2;:::aremutuallyexclusive(disjoint)andallstatesinaparticularSnintercommu-nicate,whilenotwostatesfromdifferentequivalenceclassesSnandSmdo.ThesetsS1;S2;:::arecalledclassesofthechainfXngn2N0.Equivalently,onecansaythatclassesaremaximalirreduciblesets,inthesensethattheyareirreducibleandnoclassisasubsetofa(strictlylarger)irreducibleset.Acookbookalgorithmforclassidentificationwouldinvolvethefollowingsteps:1.Startfromanarbitrarystate(callit1).LastUpdated:December24,201081IntrotoStochasticProcesses:LectureNotes CHAPTER10.CLASSIFICATIONOFSTATES2.Identifyallstatesjthatcommunicatewithit-don’tforgetthatalwaysi$i,foralli.3.Thatisyourfirstclass,callitC1.Iftherearenoelementsleft,thenthereisonlyoneclassC1=S.IfthereisanelementinSnC1,repeattheprocedureabovestartingfromthatelement.Thenotionofaclassisespeciallyusefulinrelationtoanothernaturalconcept:Definition10.9.AsetBSofstatesissaidtobeclosedifi6!jforalli2Bandallj2SnB.Astatei2Ssuchthatthesetfigisclosediscalledabsorbing.Hereisanicecharacterizationofclosedsets:Proposition10.10.AsetBofstatesisclosedifandonlyifpij=0foralli2Bandallj2Bc=SnB.c(n)Proof.Suppose,first,thatBisclosed.Thenfori2Bandj2B,wehavei6!j,i.e.,p=0forijalln2N.Inparticular,pij=0.c(n)Conversely,supposethatpij=0foralli2B,j2B.Weneedtoshowthati6!j(i.e.pij=0foralln2N)foralli2B,j2Bc.Suppose,tothecontrary,thatthereexisti2Bandj2Bc(n)suchthatpij>0forsomen2N.Sincepij=0,wemusthaven>1.Outofalln>1suchthat(n)c(n01)pik>0forsomek2B,wepickthesmallestone(letuscallitn0),sothatthatpik=0forallk2Bc.BytheChapman-Kolmogorovrelation,wehaveX(n)(n1)pij=pikpkjk2SXX(10.3)(n1)(n1)=pikpkj+pikpkj:k2Bk2BcThetermsinthefirstsuminthesecondlineof(10.3)areallzerobecausepkj=0(k2Bandj2Bc),andthetermsofthesecondonearealsoallzerobecausep(n1)=0forallk2Bc.ik(n)Therefore,p=0-acontradiction.ijIntuitively,asetofstatesisclosedifithasthepropertythatthechainfXngn2N0staysinitforever,onceitentersit.Ingeneral,ifBisclosed,itdoesnothavetofollowthatSnBisclosed.Also,aclassdoesnothavetobeclosed,andaclosedsetdoesnothavetobeaclass.Herearesomeexamples:Example10.11.Considerthetennischainofthepreviouslectureandconsiderthefollowingthreesetsofstates:1.B=f“Améliewins”g:closedandaclass,butSnBisnotclosed2.B=Snf(0;0)g:closed,butnotaclass,and3.B=f(0;0)g:class,butnotclosed.Thereisarelationshipbetweenclassesandthenotionofclosedness:LastUpdated:December24,201082IntrotoStochasticProcesses:LectureNotes CHAPTER10.CLASSIFICATIONOFSTATESProposition10.12.EveryclosedsetBisaunionofclasses.Proof.LetB^betheunionofallclassesCsuchthatCB6=;.Inotherwords,takealltheelementsofBandthrowinallthestateswhichintercommunicatewiththem.IclaimthatB^=B.Blearly,BB^,soweneedtoshowthatB^B.Suppose,tothecontrary,thatthereexistsj2B^nB.Byconstruction,jintercommunicateswithsomei2B.Inparticulari!j.ByclosednessofB,wemusthavej2B.Thisisacontradictionwiththeassumptionsthatj2B^nB.Example10.13.AconverseofProposition10.12isnottrue.JusttakethesetB=f(0;0);(0;15)ginthe“tennis”example.Itisaunionofclasses,butitisnotclosed.10.3TransienceandrecurrenceItisoftenimportanttoknowwhetheraMarkovchainwilleverreturntoitsinitialstate,andifso,howoften.Thenotionsoftransienceandrecurrenceaddressthisquestions.Definition10.14.The(first)visittimetostatej,denotedbyj(1)isdefinedasj(1)=minfn2N:Xn=jg:Asusualj(1)=+1ifXn6=jforalln2N.Notethatthedefinitionoftherandomvariablej(1)differsfromthedefinitionofjinthattheminimumhereistakeoverthesetNofnaturalnumbers,whilethesetofnon-negativeintegersN0isusedforj.WhenX06=j,thehittingtimejandthevisittimej(1)coincide.TheimportantdifferenceoccurswhenX0=j.Inthatcasej=0(wearealreadythere),butitisalwaystruethatj(1)1.ItcanevenhappenthatPi[i(1)=1]=1.Definition10.15.Astatei2Sissaidtobe1.recurrentifPi[i(1)<1]=1,2.positiverecurrentifEi[i(1)]<1(EimeansexpectationwhentheprobabilityisPi),3.nullrecurrentifitisrecurrent,butnotpositiverecurrent,4.transientifitisnotrecurrent.Astateisrecurrentifwearesurewewillcomebacktoiteventually(withprobability1).Itispositiverecurrentifthetimebetweentwoconsecutivevisitshasfiniteexpectation.Nullrecurrencemeansthewewillreturn,butthewaitingtimemaybeverylong.Astateistransientisthereisapositivechance(howeversmall)thatthechainwillneverreturntoit.Rememberthatthegreatestcommondenominator(GCD)ofasetAofnaturalnumbersifthelargestnumberdsuchthatddivideseachk2A,i.e.,suchthateachk2Aisoftheformk=ldforsomel2N.Definition10.16.Aperiodd(i)ofastatei2Sisthegreatestcommondenominatorofthe(n)return-timesetR(i)=fn2N:p>0gofthestatei.WhenR(i)=;,wesetd(i)=1.Astateiii2Siscalledaperiodicifd(i)=1.LastUpdated:December24,201083IntrotoStochasticProcesses:LectureNotes CHAPTER10.CLASSIFICATIONOFSTATESExample10.17.ConsidertheMarkovchainwiththreestatesandthetransitionmatrix23010P=40015:100Thereturnsetforeachstatei2f1;2;3gisgivenbyR(i)=f3;6;9;12;:::g;sod(i)=3foralli2f1;2;3g.However,ifwechangetheprobabilitiesabit:23010P^=40015;10122thesituationchangesdrastically:R(1)=f3;4;5;6;:::g;R(2)=f2;3;4;5;6;:::g;R(3)=f1;2;3;4;5;6;:::g;sothatd(i)=1fori2f1;2;3g.10.4ExamplesRandomwalks:p2(0;1).•Communicationandclasses.Clearly,itispossibletogofromanystateitoeitheri+1ori1inonestep,soi!i+1andi!i1foralli2S.Bytransitivityofcommunication,wehavei!i+1!i+2!


!i+k.Similarly,i!ikforanyk2N.Therefore,i!jforalli;j2S,andso,i$jforalli;j2S,andthewholeSisonebigclass.•Closedsets.TheonlyclosedsetisSitself.•TransienceandrecurrenceWestudiedtransienceandrecurrenceinthelecturesaboutrandomwalks(wejustdidnotcallthemthat).Thesituationhighlydependsontheproba-bilitypofmakinganup-step.Ifp>1,thereisapositiveprobabilitythatthefirststepwill2be“up”,sothatX1=1.Then,weknowthatthereisapositiveprobabilitythatthewalkwillneverhit0again.Therefore,thereisapositiveprobabilityofneverreturningto0,whichmeansthatthestate0istransient.Asimilarargumentcanbemadeforanystateiandanyprobabilityp6=1.Whathappenswhenp=1?Inordertocomebackto0,thewalkneeds22toreturntherefromitspositionattimen=1.Ifitwentup,thewehavetowaitforthewalktohit0startingfrom1.Wehaveshownthatthiswillhappensoonerorlater,butthattheexpectedtimeittakesisinfinite.ThesameargumentworksifX1=1.Allinall,0(andallotherstates)arenull-recurrent(recurrent,butnotpositiverecurrent).•Periodicity.Startingfromanystatei2S,wecanreturntoitafter2;4;6;:::steps.There-fore,thereturnsetR(i)isalwaysgivenbyR(i)=f2;4;6;:::gandsod(i)=2foralli2S.LastUpdated:December24,201084IntrotoStochasticProcesses:LectureNotes CHAPTER10.CLASSIFICATIONOFSTATESGambler’sruin:p2(0;1).•Communicationandclasses.Thewinningstateaandthelosingstate0areclearlyab-sorbing,andformone-elementclasses.Theothera1statesintercommunicateamongeachother,sotheyformaclassoftheirown.Thisclassisnotclosed(youcan-andwill-exititandgetabsorbedsoonerorlater).•Transienceandrecurrence.Theabsorbingstates0andaare(trivially)positiverecurrent.Alltheotherstatesaretransient:startingfromanystatei2f1;2;:::;a1g,thereisapositiveprobability(equaltopai)ofwinningeveryoneofthenextaigamesand,thus,gettingabsorbedinabeforereturningtoi.•Periodicity.Theabsorbingstateshaveperiod1sinceR(0)=R(a)=N.Theotherstateshaveperiod2(justlikeinthecaseofarandomwalk).DeterministicallymonotoneMarkovchain•Communicationandclasses.Astateicommunicateswiththestatejifandonlyifji.Thereforei$jifandonlyifi=j,andso,eachi2Sisinaclassbyitself.•Closedsets.TheclosedsetsarepreciselythesetsoftheformB=i;i+1;i+2;:::,fori2N.•TransienceandrecurrenceAllstatesaretransient.•Periodicity.ThereturnsetR(i)isemptyforeachi2S,sod(i)=1,foralli2S.Agameoftennis•Communicationandclasses.AllthestatesexceptforthoseinE=f(40;Adv);(40;40);(Adv;40);Améliewins;Björnwinsgintercommunicateonlywiththemselves,soeachi2SnEisinaclassbyiteself.ThewinningstatesAméliewinsandBjörnwinsareabsorbing,and,so,alsoformclasseswithoneelement.Finally,thethreestatesinf(40;Adv);(40;40);(Adv;40)gintercommunicatewitheachother,sotheyformthelastclass.(n)•Periodicity.ThestatesiinSnEhavehavethepropertythatp=0foralln2N,soiid(i)=1.Thewinningstatesareabsorbingsod(i)=1fori2fAméliewins,Björnwinsg.Finally,thereturnsetfortheremainingthreestatesisf2;4;6;:::gsotheirperiodis2.LastUpdated:December24,201085IntrotoStochasticProcesses:LectureNotes Chapter11MoreonTransienceandrecurrence11.1AcriterionforrecurrenceThedefinitionofrecurrencefromthepreviouslectureisconceptuallysimple,butitgivesusnoclueabouthowtoactuallygoaboutdecidingwhetheraparticularstateinaspecifisMarkovchainisrecurrent.AcriterionstatedentirelyintermsofthetransitionmatrixPwouldbenice.Beforewegiveit,weneedtointroducesomenotation.Fortwo(notnecessarilydifferent)states,(n)i;j2S,letfbetheprobabilitythatitwilltakeexactlynstepsforthefirstvisittoj(startingijfromi)tooccur,i.e.,(n)fij=Pi[j(1)=n]=P[Xn=j;Xn16=j;Xn26=j;:::;X26=j;X16=jjX0=i]:Letfijdenotetheprobabilitythatjwillbereachedfromieventually,i.e.,X1(n)fij=fij:n=1Clearly,wehavethefollowingequivalence:iisrecurrentifandonlyiffii=1.(n)Thereasonthequantitiesfareusefulliesinthefollowingrecursiverelationship:ijProposition11.1.Forn2Nandi;j2S,wehaveXn(n)(nm)(m)p=pf:ijjjijm=1Proof.Inpreparationfortherestoftheproof,letusreiteratethattheeventfj(1)=mgcanbewrittenasfj(1)=mg=fXm=j;Xm16=j;Xm26=j;:::;X16=jg:Usingthelawoftotalprobability,wecansplittheeventfXn=jgaccordingtothevalueoftherandomvariablej(1)(thevaluesofj(1)largerthanndonotappearinthesumsinceXncannot86 CHAPTER11.MOREONTRANSIENCEANDRECURRENCEbeequaltojinthosecases):Xn(n)pij=P[Xn=jjX0=i]=P[Xn=jjj(1)=m;X0=i]P[j(1)=mjX0=i]m=1Xn(m)=P[Xn=jjXm=j;Xm16=j;Xm26=j;:::;X16=j;X0=i]fijm=1XnXn(m)(nm)(m)=P[Xn=jjXm=j]fij=pjjfijm=1m=1AnimportantcorollarytoProposition11.1isthefollowingcharacterizationofrecurrence:Proposition11.2.Astatei2SisrecurrentifandonlyifX1(n)p=+1:iin=1Proof.Fori=j,Proposition11.1statesthatXn(n)(nm)(m)p=pf:iiiiiim=1Summingoverallnfrom1toN2N,wegetXNXNXnXNXN(n)(nm)(m)(nm)(m)pii=piifii=1fmngpiifii(11.1)n=1n=1m=1n=1m=1PN(n)(0)WesetsN=n=1piiforN2N,rememberthatpii=1,andinterchangetheorderofsummationtogetXNXNXNNXmXN(nm)(m)(m)(n)(m)sN=piifii=fiipii=fii(1+sNm)m=1n=mm=1n=0m=1ThesequencefsNgN2Nisnon-decreasing,soXN(m)sNfii(1+sN)(1+sN)fii:m=1Therefore,sNfiilim:N1+sNP1(n)sNIfn=1pii=+1,thenlimN!11+sN=1,sofii1.Ontheotherhand,fii=Pi[i(1)<1],sofii1.Therefore,fii=1,and,so,thestateiisrecurrent.LastUpdated:December24,201087IntrotoStochasticProcesses:LectureNotes CHAPTER11.MOREONTRANSIENCEANDRECURRENCEConversely,supposethatiisrecurrent,i.e.,fii=1.Wecanrepeattheprocedurefromabove(butwith+1insteadofNandusingTonelli’stheoremtointerchangetheorderofthesums)togetthatX1X1X1X1(n)(m)(n)(n)p=f(1+p)=1+p:iiiiiiiin=1m=1n=1n=1P1(n)Thiscanhappenonlyifp=+1.m=1ii11.2ClasspropertiesCertainpropertiesofstatesaresharedbetweenallelementsinaclass.Knowingwhichpropertiessharethisfeatureisusefulforasimplereason-ifyoucancheckthemforasingleclassmember,youknowautomaticallythatalltheotherelementsoftheclassshareit.Definition11.3.Apropertyiscalledaclasspropertyitholdsforallstatesinitsclass,wheneveritholdsforanyoneparticularstateinthethatclass.Putdifferently,apropertyisaclasspropertyifandonlyifeitherallstatesinaclasshaveornonedoes.Proposition11.4.Transienceandrecurrenceareclassproperties.Proof.Supposethatthestateiisrecurrent,andthatjisinitsclass,i.e.,thati$j.Then,there(m)(k)existnaturalnumbersmandksuchthatp>0andp>0.BytheChapman-Kolmogorovijjirelations,foreachn2N,wehaveXX(n+m+k)(k)(n)(m)(k)(n)(m)p=pppppp:jjjl1l1l2l2mjiiiijl12Sl22S(k)(m)Inotherwords,thereexistsapositiveconstantc(takec=pp),independentofn,suchthatjiij(n+m+k)(n)pcp:jjiiP1(n)Therefore,byrecurrenceofiwehavep=+1,andn=1iiX1X1X1X1(n)(n)(n+m+k)(n)pp=pcp=+1;jjjjjjiin=1n=m+k+1n=1n=1andso,jisrecurrent.Therefore,recurrenceisaclassproperty.Sincetransienceisjusttheoppositeofrecurrence,itisclearthattransienceisalsoaclassproperty.Proposition11.5.Periodisaclassproperty,i.e.,allelementsofaclasshavethesameperiod.LastUpdated:December24,201088IntrotoStochasticProcesses:LectureNotes CHAPTER11.MOREONTRANSIENCEANDRECURRENCEProof.Letd=d(i)betheperiodofthestatei,andletj$i.Then,thereexistnaturalnumbers(m)(k)mandksuchthatp>0andp>0.ByChapman-Kolmogorov,ijji(m+k)(m)(k)ppp>0;iiijjiandsom+k2R(i):(11.2)Similarly,foranyn2R(j),(m+k+n)(m)(n)(k)pppp>0;iiijjjjisom+k+n2R(i):(11.3)By(11.2),d(i)dividesm+k,and,by(11.3),d(i)dividesm+k+n.Therefore,d(i)dividesn,foreachn2R(j),andso,d(i)d(j),becaused(j)isthegreatestcommondivisorofR(j).Thesameargumentwithrolesofiandjswitchedshowsthatd(j)d(i).Therefore,d(i)=d(j).11.3AcanonicaldecompositionNowthatweknowthattransienceandrecurrenceareclassproperties,wecanintroducethenotionofcanonicaldecompositionofaMarkovchain.LetS1;S2;:::bethecollectionofallclasses;someofthemcontainrecurrentstatesandsometransientones.Proposition11.4tellsusthatifthereisonerecurrentstateinaclass,thanallstatesintheclassmustberecurrent.This,itmakessensetocallthewholeclassrecurrent.Similarly,theclasseswhicharenotrecurrentconsistsentirelyoftransientstates,sowecallthemtransient.Thereareatmostcountablymanystates,sothenumberofallclassesisalsoatmostcountable.Inparticular,thereareonlycountably(orfinitely)manyrecurrentclasses,andweusuallydenotethembyC1;C2;:::.TransientclassesaredenotedbyT1;T2;:::.Thereisnoparticularruleinthechoiceofindices1;2;3;:::forparticularclasses.Theonlypointisthattheycanbeenumeratedbecausethereareatmostcountablymanyofthem.Thedistinctionbetweendifferenttransientclassesisusuallynotveryimportant,sowepackalltransientstatestogetherinasetT=T1[T2[:::.Definition11.6.LetSbethestatespaceofaMarkovchainfXngn2N0.LetC1;C2;:::beitsrecurrentclasses,andT1;T2;:::thetransientones,andletT=T1[T2[:::betheirunion.ThedecompositionS=T[C1[C2[C3[:::;iscalledthecanonicaldecompositionofthe(statespaceofthe)MarkovchainfXngn2N0.Thereasonthatrecurrentclassesareimportantissimple-theycanbeinterpretedasMarkovchainsthemselves.Inorderforsuchaninterpretationtobepossible,weneedtomakesurethattheMarkovchainstaysinarecurrentclassifitstartsthere.Inotherwords,wehavethefollowingimportantproposition:LastUpdated:December24,201089IntrotoStochasticProcesses:LectureNotes CHAPTER11.MOREONTRANSIENCEANDRECURRENCEProposition11.7.Recurrentclassesareclosed.Proof.Suppose,contrarytothestatementoftheProposition,thatthereexisttwostatesi6=jsuchthat1.iisrecurrent,2.i!j,and3.j6!i.Theideaoftheproofisthefollowing:wheneverthetransitioni!joccurs(perhapsinseveralsteps),thenthechainwillneverreturntoi,sincej6!i.Byrecurrenceofi,thatisnotpossible.Thereforei6!j-acontradiction.Moreformally,therecurrenceofimeansthat(startingfromi,i.e.,underPi)theeventA=fXn=i;forinfinitelymanyn2Nghasprobability1,i.e.,Pi[A]=1.ThelawoftotalprobabilityimpliesthatX1=Pi[A]=Pi[Ajj(1)=n]Pi[j(1)=n]+Pi[Ajj(1)=+1]Pi[j(1)=+1]:(11.4)n2NOntheeventj(1)=n,thechaincanvisitthestateiatmostn1times,becauseitcannothitiafteritvisitsj(rememberj6!i).Therefore,P[Ajj(1)=n]=0,foralln2N.Itfollowsthat1=Pi[Ajj(1)=+1]Pi[j(1)=+1]:Bothofthetermsontheright-handsideaboveareprobabilitieswhoseproductequals1,whichforcesbothofthemtobeequalto1.Inparticular,Pi[j(1)=+1],or,phraseddifferently,i6!j-acontradiction.Togetherwiththecanonicaldecomposition,weintroducethecanonicalformofthetransitionmatrixP.TheideaistoorderthestatesinSwiththecanonicaldecompositioninmind.WestartfromallthestatesinC1,followedbyallthestatesinC2,etc.Finally,weincludeallthestatesinT.Theresultingmatrixlookslikethis23P100:::0660P20:::077P=6600P3:::077;6..........74.....5Q1Q2Q3::::::wheretheentriesshouldbeinterpretedasmatrices:P1isthetransitionmatrixwithinthefirstclass,i.e.,P1=(pij;i2C1;j2C1),etc.Qkcontainsthetransitionprobabilitiesfromthetransientstatestothestatesinthe(recurrent)classCk.NotethatProposition11.7impliesthateachPkisastochasticmatrix,or,equivalently,thatalltheentriesintherowofPkoutsideofPkarezeros.Wefinishthediscussionofcanonicaldecompositionwithanimportantresultandoneofitsconsequences.LastUpdated:December24,201090IntrotoStochasticProcesses:LectureNotes CHAPTER11.MOREONTRANSIENCEANDRECURRENCEProposition11.8.SupposethatthestatespaceSisfinite.Thenthereexistsatleastonerecurrentstate.Proof.ThetransitionmatrixPisstochastic,andsoareallitspowersPn.Inparticular,wehaveX(n)1=p;foralli2S:ijj2SSummingtheaboveequalityoveralln2NandswitchingtheorderofintegrationgivesXXXXX(n)(n)+1=1=p=p:ijijn2Nn2Nj2Sj2Sn2NP(n)Weconcludethatp=+1foratleastonestatej(thisiswherethefinitenessofSisn2Nijcrucial).Weclaimthatjisarecurrentstate.Suppose,tothecontrary,thatitistransient.IfwesumtheequalityfromProposition11.1overn2N,wegetXXXnXX1XX1X1(n)(nm)(m)(nm)(m)(m)(n)(n)pij=pjjfij=pjjfij=fijpjj=fijpjj:(11.5)n2Nn2Nm=1m2Nn=mm2Nn=0n=0P1(n)Transienceofjimpliesthatn=1pjj<1and,bydefinition,fij1,foranyi;j.Therefore,P(n)p<1-acontradiction.n2NijRemark11.9.IfSisnotfinite,itisnottruethatrecurrentstatesmustexist.JustremembertheDeterministically-monotoneMarkovchainexample,ortherandomwalkwithp6=1.Allstates2aretransitivethere.Inafinitestate-spacecase,wehavethefollowingdichotomy:Corollary11.10.AclassofaMarkovchainonafinitestatespaceisrecurrentifandonlyifitisclosed.Proof.Weknowthatrecurrentclassesareclosed.Inordertoshowtheconverse,weneedtoprovethattransientclassesarenotclosed.Suppose,tothecontrary,thethereexistsafinitestate-spaceMarkovchainwithaclosedtransientclassT.SinceTisclosed,wecanseeitasastatespaceoftherestrictedMarkovchain.This,new,Markovchainhasafinitenumberofstatessothereexistsarecurrentstate.ThisisacontradictionwiththeassumptionthatTconsistsonlyoftransientstates.Remark11.11.Again,finitenessisnecessary.ForarandomwalkonZ,allstatesintercommuni-cate.Inparticular,thereisonlyoneclassZitselfanditittriviallyclosed.Ifp6=1,however,all2statesaretransient,and,so,Zisaclosedandtransientclass.LastUpdated:December24,201091IntrotoStochasticProcesses:LectureNotes Chapter12AbsorptionandrewardNote:Eventhoughitisnotbyanymeansnecessary,weareassumingthat,fromthispointonwards,allMarkovchainshavefinitestatespaces.12.1AbsorptionRememberthe“Tennis”examplefromafewlecturesagoandthequestionweaskedthere,namely,howdoestheprobabilityofwinningasinglepointaffecttheprobabilityofwinningtheoverallgame?Analgorithmthatwillhelpyouanswerthatquestionwillbedescribedinthislecture.Thefirststepistounderstandthestructureofthequestionaskedinthelightofthecanonicaldecompositionofthepreviouslecture.Inthe“Tennis”example,allthestatesexceptforthewinningonesaretransient,andtherearetwoone-elementrecurrentclassesfAméliewinsgandfBjörnwinsg.Thechainstartsfromatransientstate(0;0),movesaroundabit,and,eventually,getsabsorbedinoneofthetwo.Theprobabilityweareinterestedinisnottheprobabilitythatthechainwilleventuallygetabsorbed.Thisprobabilityisalways1(thisistrueineveryfiniteMarkovchain,butwedonotgiveaproofofthis).Weare,instead,interestedintheprobabilitythattheabsorptionwilloccurrinaparticularstate-thestatefAméliewinsginthe“Tennis”example.Amoregeneralversionoftheproblemaboveisthefollowing:leti2Sbeanystate,andletjbearecurrentstate.IfthesetofallrecurrentstatesisdenotedbyC,andifCisthefirsthittingtimeofthesetC,thenXCdenotesthefirstrecurrentstatevisitedbythechain.Equivalently,XCisthevalueofXat(random)timeC;itsvalueisthenameofthestateinwhichithappenstofinditselfthefirsttimeithitsthesetofallrecurrentstates.Foranytwostatesi;j2S,theabsorptionprobabilityuijisdefinedasuij=Pi[XC=j]=Pi[thefirstrecurrentstatevisitedbyXisj]:Whenj,isnotarecurrentstate,thenuij=0;jcannotpossiblybethefirstrecurrentstatewehit-itisnotevenrecurrent.Whwni=jisarecurrentstate,thenuii=1-weareinirightfromthestart.Thesituationi2T,j2Cistheinterestingone.InmanycalculationsrelatedtoMarkovchains,themethodoffirst-stepdecompositionworksmiracles.Simply,wecuttheprobabilityspaceaccordingtowhathappenedinthefirststepand92 CHAPTER12.ABSORPTIONANDREWARDusethelawoftotalprobability(assumingi2T,j2C)Xuij=Pi[XC=j]=P[XC=jjX0=i;X1=k]P[X1=kjX0=i]k2SX=P[XC=jjX1=k]pikk2STheconditionalprobabilityP[XC=jjX1=k]isanabsorptionprobability,too.Ifk=j,thenP[XC=jjX1=k]=1.Ifk2Cnfjg,thenwearealreadyinC,butinastatedifferentfromj,soP[XC=jjX1=k]=0.Therefore,thesumabovecanbewrittenasXuij=pikukj+pij;k2Twhichisasystemoflinearequationsforthefamily(uij;i2T;j2C).Linearsystemsaretypicallybetterunderstoodwhenrepresentedinthematrixform.LetUbeaTC-matrixU=(uij;i2T;j2C),andletQbetheportionofthetransitionmatrixPcorrespondingtothetransitionsfromTtoT,i.e.Q=(pij;i2T;j2T),andletRcontainalltransitionsfromTtoC,i.e.,R=(pij)i2T;j2C.IfPCdenotesthematrixofalltransitionsfromCtoC,i.e.,PC=(pij;i2C;j2C),thenthecanonicalformofPlookslikethis:PC0P=:RQThesystem(12.1)nowbecomes:U=QU+R;i.e.,(IQ)U=R:IfthematrixIQhappenstobeinvertible,weareinbusiness,becausewethenhaveanexplicitexpressionforU:U=(IQ)1R:So,isIQinvertible?ItiswhenthestatespaceSisfinite,butyouwillnotseetheproofinthesenotes.Whentheinverse(IQ)1exists,itiscalledthefundamentalmatrixoftheMarkovchain.Example12.1.Beforeweturntothe“Tennis”example,letusanalyzeasimplercaseofGambler’sruinwitha=3.Thestates0and3areabsorbing,andalltheothersaretransient.ThereforeC1=f0g,C2=f3gandT=T1=f1;2g.ThetransitionmatrixPinthecanonicalform(therowsandcolumnsrepresentthestatesintheorder0;3;1;2)231000601007P=6741p00p50p1p0Therefore,1p00pR=andQ=:0p1p0LastUpdated:December24,201093IntrotoStochasticProcesses:LectureNotes CHAPTER12.ABSORPTIONANDREWARDThematrixIQisa22matrixsoitiseasytoinvert:111p(IQ)=:1p+p21p1So"#1pp211p1p01p+p21p+p2U==2:1p+p21p10p(1p)p1p+p21p+p2Therefore,forexample,iftheinitial“wealth”is1,theprobabilityofgettingrichbeforebankruptcyisp2=(1p+p2).Wehavealreadycalculatedthisprobabilityinoneofthehomeworkproblems(HW4,Problem
4.4).There,weobtainedthatthedesiredprobabilityequals(1q)=1(q)3.Youcancheckppthatthesetwoexpressionsarereallythesame.Example12.2.Inthe“Tennis”example,thetransitionmatrixis2020,withonly2recurrentstates(eachinitsownclass).ThematrixgiveninLecture8isalreadyinthecanonicalform(therecurrentstatescorrespondtothefirsttworows/columns).Inordertoget(IQ)1,weneedtoinvertan1818matrix.Thisisajobforacomputer,andweuseMathematica(Pisthefulltransitionmatrixand3isorderofthestate(0;0)intheinternalrepresentation).Afterweremovetheabsorbingstates,thenumberof(0;0)becomes1(intheMathematicainternalorder)andthatiswhyweareextractingtheelementinthefirstrowandfirstcolumninUtogettheresult):In[114]:=Q=P@@3;;20,3;;20DD;R=P@@3;;20,1;;2DD;In[115]:=F=Inverse@IdentityMatrix@18D-QD;In[116]:=U=F.R;In[117]:=U@@1,1DD20p5q34+4p4q+10p4q2-Out[117]=p-1+2pq:Ifweplotthisprobabilityagainstthevalueofp,wegetthefollowingpicture:1.00.80.60.40.20.20.40.60.81.0:LastUpdated:December24,201094IntrotoStochasticProcesses:LectureNotes CHAPTER12.ABSORPTIONANDREWARD12.2ExpectedrewardSupposethateachtimeyouvisitatransientstatej2Tyoureceivearewardg(j)2R.Thename“reward”isabitmisleadingsincethenegativeg(j)correspondsmoretoafinethantoareward;itisjustaname,anyway.CanwecomputetheexpectedtotalrewardbeforeabsorptionXCvi=Ei[g(Xn)]?n=0Andifwecan,whatisitgoodfor?Manythings,actually,asthefollowingtwospecialcasesshow:1.Ifg(j)=1forallj2T,thenviistheexpectedtimeuntilabsorption.Wewillcalculatev(0;0)forthe“Tennis”exampletocomputetheexpecteddurationofatennisgame.2.Ifg(k)=1andg(j)=0forj6=k,thenviistheexpectednumberofvisitstothestatekbeforeabsorption.Inthe“Tennis”example,ifk=(40;40),thevalueofv(0;0)istheexpectednumberoftimesthescore(40;40)isseeninatennisgame.Wecomputeviusingthefirst-stepdecomposition:XCXCvi=E[g(Xn)jX0=i]=g(i)+E[g(Xn)jX0=i]n=0n=1XXC=g(i)+E[g(Xn)jX0=i;X1=k]P[X1=kjX0=i](12.1)k2Sn=1XXC=g(i)+pikE[g(Xn)jX1=k]k2Sn=1Ifk2T,thenthehomogeneityofthechainimpliesthatXCXCE[g(Xn)jX1=k]=E[g(Xn)jX0=k]=vk:n=1n=0Whenk62T,thenXCE[g(Xn)jX1=k]=0;n=1becausewehave“arrived”andnomorerewardsaregoingtobecollected.Therefore,fori2TwehaveXvi=g(i)+pikvk:k2TIfweorganizeallviandallg(i)intocolumnvectorsv=(vi;i2T),g=(g(i);i2T),wegetv=Qv+g;i.e.,v=(IQ)1g:Havingderivedthegeneralforumlaforvariousrewards,wecangiveaninterpretationofthefundamentalmatrixitself.Letuspickatransientstatejandusetherewardfunctionggivenby(1;k=jg(k)=1fk=jg=0;k6=j:LastUpdated:December24,201095IntrotoStochasticProcesses:LectureNotes CHAPTER12.ABSORPTIONANDREWARDBythediscussionabove,theithentryinv=(IQ)1gistheexpectedrewardwhenwestartfromthestatei.Giventheformoftherewardfunction,viistheexpectednumberofvisitstothestatejwhenwestartfromi.Ontheotherhand,astheproductofthematrix(IQ)1andthevectorg=(0;0;:::;1;:::;0),viisnothingbutthe(i;j)-entryin(IQ)1:Proposition12.3.Fortwotransientstatesiandj,the(i;j)-thentryinthefundamentalmatrix(IQ)1istheexptecednumberofvisitstothestatejpriortoabsorbtionifthechainstartsfromthestatei(thetime0iscounted,ifi=j).Example12.4.Wecontinuetheanalysisofthe“Tennis”chainfromExample12.2.Wesetg(i)=1foralltransientstatesitofindtheexpecteddurationofatennisgame.In[87]:=G=Table@81<,8i,1,180,thenthesumis+1,soisnotadistributioneither.Intuitively,thechainneverstabilizes,itjustkeepsmovingtotherightadinfinitum.Theexamplewithmanystationarydistributionscanbeconstructedonanystatespace,buttheotherone,wherenostationarydistributionexists,hadtouseaninfiniteone.Wasthatnecessary?Yes.Beforeweshowthisfact,letusanalyzetherelationbetweenstationarydistributionsandthepropertiesofrecurrenceandtransience.Hereisourfirstresult:Proposition13.7.SupposethatthestatespaceSofaMarkovchainisfiniteandletS=C1[C2[


[Cm[Tbeitscanonicaldecomposition,Thenthefollowingtwostatementsareequivalent:1.isastationarydistribution,and2.Ck=CkPk,k=1;:::;m,andT=(0;0;:::;0),where23P100066.......77..0P=67;400Pm05RQisthecanonicalformofthetransitionmatrix,Ck=(i;i2Ck),k=1;2;:::;mandT=(i;i2T).PProof.Wewritetheequation=Pcoordinatewiseasj=i2Sipijand,bydistinguishingthecasesi2Ck,k2f1;2;:::;mg,andi2T,wegetthefollowingsytemofmatrixequations(alternatively,justwritethesystem=Pintheblock-matrixformaccordingtothecannonicaldecompositionabove):Ck=P+TR;k=1;:::;m;andT=TQ:CKCkThelastequalitycanbereadasfollows:Tisinarownull-spaceofIQ.Weknow,however,thatIQadmitsaninverse,andsoitisaregularsquarematrix.Itsrownull-space(aswellasitscolumnnull-space)mustbetrivial,and,consequently,T=0.HavingestablishedthatT=0,wecande-couplethesystemofequationsaboveandwriteitasCk=P;k=1;:::;m;andT=(0;0;:::;0);CKkLastUpdated:December24,2010102IntrotoStochasticProcesses:LectureNotes CHAPTER13.STATIONARYANDLIMITINGDISTRIBUTIONSwhichisexactlywhatweneededtoprove.Theotherimplication-theproofofwhichconsistsofaverificationofthefactthateachdistributionfrom(2)aboveisindeedastationatydistribution-islefttothereader.ThemoralofthestoryofProposition13.7isthefollowing:inordertocomputethestationarydistribution(s),classifythestatesandfindthecanonicaldecompositionofthestatespace.Then,seti=0foranytransientstatei.Whatremainsarerecurrentclasses,andyoucananalyizeeachoneseparately.Note,however,thatCkdoesnotneedtobearealdistributiononCk,sincePCkCkdoesnotneedtoequal1.However,unless=(0;0;:::;0),wecanalwaysmultiplyi2Ckiallitselementsbyaconstanttomakethesumequalto1.ThankstotheresultsofProposition13.7,wecanfocusonMarkovchainswithonlyoneclass:Definition13.8.AMarkovchainissaidtobeirreducibleifthereisonlyoneclass.WhenaMarkovchainisfiniteandirreducible,allofitsstatesmustberecurrent.Indeed,afiniteMarkovchainhasatleastonerecurrentstate,andrecurrenceisaclassproperty.Nowthatwehavedescribedthestructureofthesetofallstationarydistributions,westillneedtototacklethequestionofexistence:arethereanystationarydistributions?Inadditiontogivinganaffirmativeanswertothisquestion,wewillalsoshowhowtoconstructastationarydistributionandhowtointerpretitprobabilistically.Proposition13.9.LetfXngn2N0beanirreducibleMarkovchainwithafinitestatespace.Then,thefollowingtwostatementshold:1.Allstatesarepositiverecurrent.2.Letibeafixed(butarbitrary)recurrentstate.Let23iX(1)1j=Ei41fXn=jg5;j2Sn=0betheexpectednumberofvisitstostatejinbetweentwoconsecutivevisitstostatei.Thenthevector,givenby=1,j2S(wherem=E[(1)])isastationaryjmijiiidistribution.Remark13.10.Eventhoughitisnotexceedinglyhard,theproofofthispropositionisabittechnical,soweomitit.Itisimportant,however,tounderstandwhatthepropositionsstates:1.theexpectednumberofvisitstothestatejinbetweentwoconsecutivevisitstothestateicanberelatedtoastationarydistributionoftheMarkovchainbyj=mij,and2.whenwesetj=i,icountsthenumberofvisitstoibetweentwoconsecutivevisitstoi,whichisalwaysequalto1(thefirstvisitiscountedandthelastoneisnot).Therefore,=1,andso=1.iimiProposition13.9andRemark13.10aretypicallyusedinthefollowingway:onecomputestheuniquestationarydistributionbysolvingtheequation=Pandthendrawsconclusionsaboutmiorthej’s.Notealsothatthecomputationaboveisnotaspecialcaseofarewardcomputationofthepreviouslecture.There,youneedtostartfromatransientstateandfinishinarecurrentstate,whilehereyourstartingandfinalstatearethesame.LastUpdated:December24,2010103IntrotoStochasticProcesses:LectureNotes CHAPTER13.STATIONARYANDLIMITINGDISTRIBUTIONS13.2LimitingdistributionsExample13.5showsvividlyhowthedistributionofinkquicklyreachestheuniformequilibriumstate.Itisnocoincidencethatthis“limiting”distributionhappenstobeastationatydistribution.Beforewemakethisclaimmoreprecise,letusdefinerigorouslywhatwemeanbyalimitingdistribution:Definition13.11.Adistribution=(i;i2S)onthestatespaceSofaMarkovchainwithtransitionmatrixPiscalledalimitingdistributionif(n)limpij=j;n!1foralli;j2S.Notethatfortobealimitingdistribution,allthelimitsinDefinition13.11mustexist.Oncetheydo,isautomaticallyadistribution:j0(asalimitofnon-negativenumbers)andXXX(n)(n)j=limpij=limpij=lim1=1:n!1n!1n!1j2Sj2Sj2SAlso,notethattheindependenceontheinitialstateiisbuiltintothedefinitionofthelimiting(n)distribution:thesequencefpijgn2Nmusttendtothesamelimitjforalli2S.Moreover,itfollowsimmediatelytherecanbeatmostonelimitingdistribution.Theconnectionwithstationarydistributionsisspelledoutinthefollowingpropositions:Proposition13.12.SupposethataMarkovchainwithtransitionmatrixPadmitsalimitingdistribution=(i;i2S).Thenisastationarydistribution.Proof.Toshowthatisastationarydistribution,weneedtoverifythatitsatisfies=P,i.e.,thatXj=ipij:i2S(n+1)P(n)WeusetheChapman-Kolmogorovrelationpij=k2Spikpkjandstartfromtheobservation(n+1)thatj=limn!1pijtogetexactlywhatweneed:XXX(n+1)(n)(n)j=limpij=limpikpkj=(limpik)pkj=kpkj:n!1n!1n!1k2Sk2Sk2SExample13.13.Limitingdistributionsdon’tneedtoexist,evenwhentherearestationaryones.Herearetwoexamples:1.LetfXngn2N0beaRegime-switchingchainwith01P=10LastUpdated:December24,2010104IntrotoStochasticProcesses:LectureNotes CHAPTER13.STATIONARYANDLIMITINGDISTRIBUTIONSThen(1(1+(1)n);i=j(n)2p=ij1(1+(1)n+1);i6=j:2(n)Clearly,thesequencepisalternatingbetween0and1,soitcannotadmitalimit.Aijstationarydistributionexists:thesystem=Pbecomes0=00+11;1=10+01:2.Inthepreviousexamplethelimitingdistributiondidnotexistwhichimpliesthat0=1.Inorderfortobeadistributiononf0;1g,wemusthave==1.So,(1;1)isa01222stationarydistribution.3.Inthepreviousexamplethelimitingdistributiondidnotexistsbecausethelimitsofthe(n)sequencespdidnotexist.Anotherreasonforthenon-existenceoflimitingdistributionsij(n)canbedependenceontheinitialconditions:thelimitslimnpijmayexistforalli;j,buttheirvaluescandependontheintialstatei.ThesimplestexampleisaMarkovchainwithtwostatesi=1;2,wherep11=p22=1.Therearetworecurrent(andthereforeclosed)(n)classes,andthechainremainsinthestateitstarteinforever.Therefore,limnp12=0and(n)(n)limnp22=1,sonolimitingdistributionexistsdespitethefactthatalllimitslimnpijdo.Proposition13.14.LetfXngn2N0beafinite-state,irreducibleandaperiodicMarkovchain.Thenthelimitingdistributionexists.WeconcludethediscussionoflimitingdistributionswithaversionoftheLawofLargeNumbers(LLN)forMarkovchains.Beforewestateit,werecalltheclassicalLLNforindependentvariables:Theorem13.15.LetfXngn2N0beasequenceofindependentandidenticallydistributedrandomvariables,suchthatE[jX0j]<1.ThennX11limXk=E[X0];nnk=0almostsurely2.WhenfXngn2N0isaMarkovchain,twoproblemsoccur.First,therandomvariablesX0;X1;:::arenotindependent.Second,XktakesitsvaluesinthestatespaceSwhichdoesnotnecessarilyconsistofnumbers,sotheexpressionX0+X1orE[X0]doesnotmakesenseallthetime.Todealwiththesecondproblem,wepickanumericalfunctionf:S!R(giveeachstateavalue)andformsumsoftheformf(X0)+f(X1)+


+f(Xn1).Independenceismoresubtle,butitcanbereplacedwithstationarity(looselyspeaking),asinthefollowingproposition(weskiptheproof):2Almostsurelymeanswithprobabilityone,andstatesthatthisstatementistrueallthetimeforallpracticalpurposes.Itmayfail,butonlyinextremelyexceptionalcasessuchastheonewhereyoutossafaircoininfinitelymanytimesandgettailseverysingletime.Thatmeansnever,really.LastUpdated:December24,2010105IntrotoStochasticProcesses:LectureNotes CHAPTER13.STATIONARYANDLIMITINGDISTRIBUTIONSProposition13.16.LetfXngn2N0beanirreducibleMarkovchainwithafinitestatespaceS,let=(i;i2S)bethe(unique)stationarydistribution,andletf:S!Rbeanarbitraryfunction.ThenPn1Xk=0f(Xk)lim=f(i)i;nni2Salmostsurely,nomatterwhatinitialdistributionwechoose.Example13.17.LetfXngn2N0beanirreduciblefiniteMarkovchain,andletthefunctionf:S!Rbegivenby(1;j=i;f(j)=1(i=j)=0;j6=i:Then,bytheLawofLargeNumbers,wegave1nX1Xlim1fXk=ig=1(i=j)j=i;nnk=0j2Ssothaticanbeinterpretedasalong-runpercentageoftimethattheMarkovchainfXngn2N0spendsinthestatei.LastUpdated:December24,2010106IntrotoStochasticProcesses:LectureNotes