Topic 7: Random Processes

1 Topic7: RandomProcesses De nition,discreteandcontinuousprocesses Specifyingrandomprocesses{Joint cdf's or pdf's{Mean,auto-covariance,auto-correlat ion{Cross-covariance,cross-correlation StationaryprocessesandergodicityES150{ Harvard SEAS1 Randomprocesses Arandomprocess, alsocalledastochasticprocess, is a familyof randomvariables,indexedby a parametertfromanindexingsetT. For eachexperiment outcome!2 ,we assigna functionXthatdependsontX(t; !)t2T; !2 {tis typicallytime,butcanalsobe a spatialdimension{tcanbe discreteor continuous{Therangeoftcanbe nite,butmoreoftenis in nite,which meanstheprocesscontainsanin nitenumber of randomvariables. Examples:{Thewirelesssignalreceivedby a cellphoneover time{Thedailystock price{Thenumber of packetsarrivingat a routerin 1-secondintervals{Theimageintensity over 1cm2regionsES150{ Harvard SEAS2 We areinterestedin specifyingthejoint behaviorof therandomvariableswithina family, or thebehaviorof a studying{Thedependenciesamongtherandomva riablesof theprocess( ){Long-termaverages{Extremeor boundaryevents ( ){Estimation/detectionof a signalcorruptedby noiseES150{ Harvard SEAS3 Two ways of viewinga randomprocessConsidera processX(t; !)}}}}}}}}}}}}}}}}}

2 At a xedt,X(t; !) is a randomvariableandis calledatimesample. For a xed!,X(t; !) is adeterministicfunctionoftandis calledarealization(ora samplepathor samplefunction))!inducestherandomnessinX (t; !). In thesubsequent notation,!isimplicitlyimpliedandtherefor eis usuallysuppressed. Whentcomesfroma countableset,theprocessisdiscrete-time. Wethenusuallyusento denotethetimeindexinsteadandwritetheproc essasX(n; !), or justXn,n2Z.{For each n,Xnis a ,which canbe continuous,discrete,or mixed.{Examples:Xn=Zn;n 1; Z U[0;1].Others:sendingbitsover a noisychannel,samplingof thermalnoise. Whentcomesfromanuncountablyin niteset,theprocessiscontinuous-time. We thenoftendenotetherandomprocessasX(t). Ateacht,X(t) is a randomvariable.{Examples:X(t) = cos(2 f t+ ); U[ ; ].ES150{ Harvard SEAS4 Specifyinga randomprocess A randomprocesscanbecompletelyspeci edby thecollectionof jointcdfamongtherandomvariablesfX(t1); X(t2); : : : ; X(tn)gforany setof sampletimesft1; t2; : : : ; tngandany (tk),{If theprocessis continuous-valued,thenit canalsobe speci edbythecollectionof joint pdffX1;:::;Xn(x1; : : : ; xn){If theprocessis discrete-valued,thena collectionof joint pmfcanbe usedpX1;:::;Xn(x1; : : : ; xn) =P[X1=x1; : : : ; Xn=xn] Thismethod requiresspecifyinga vastcollectionof joint cdf's or pdf's,butworkswell forsomeimportant andusefulmodelsof { Harvard SEAS5 Mean,auto-covariance,andauto-correlation functionsThemoments of timesamplesof a randomprocesscanbe usedtopartlyspecifytheprocess.}}}}}}}

3 Meanfunction:mX(t) =E[X(t)] =Z1 1x fX(t)(x)dxmX(t) is a functionof speci estheaveragebehavior(orthetrendin thebehavior)ofX(t) over time. Auto-correlationfunction:RX(t1; t2) is de nedas thecorrelationbetweenthetwo timesamplesXt1=X(t1) andXt2=X(t2)RX(t1; t2) =E[Xt1Xt2]Properties:{In general,RX(t1; t2) dependsonbotht1andt2.{For realprocesses,RX(t1; t2) issymmetricRX(t1; t2) =RX(t2; t1)ES150{ Harvard SEAS6{For anyt,t1andt2RX(t; t)=E[X2t] 0jRX(t1; t2)j qE[X2t1]E[X2t2]ProcesseswithE[X2t]<1fora lltis calledsecond-order. Auto-covariancefunction:Cx(t1; t2) is de nedas thecovariancebetweenthetwo timesamplesX(t1) andX(t2)CX(t1; t2)=E[fXt1 mX(t1)gfXt2 mX(t2)g]=RX(t1; t2) mX(t1)mX(t2){ThevarianceofX(t) canbe obtainedasvar(Xt) =E[fX(t) mX(t)g2] =CX(t; t)var(Xt) is a functionof timeandis always non-negative.{Thecorrelationcoe cientfunction: X(t1; t2) =CX(t1; t2)pCX(t1; t1)pCX(t2; t2) X(t1; t2) is a functionof timest1andt2.}}}}}}

4 It is { Harvard SEAS7 Examples:Findthemeanandautocorrelationfu nctionsof thefollowingprocesses:a)X(t) = cos(2 f t+ ); U[ ; ]b)Xn=Z1+: : :+Zn;n= 1;2; : : { Harvard SEAS8 Multiplerandomprocesses:Cross-covariance andcross-correlationfunctionsFor multiplerandomprocesses: Theirjoint behavioris completelyspeci edby thejoint distributionsforallcombinationsof usedto partiallyspecifythejoint randomprocessesX(t) andY(t). Cross-correlationfunction:RX;Y(t1; t2) =E[Xt1Yt2]{IfRX;Y(t1; t2) = 0 forallt1andt2, processesX(t) andY(t) areorthogonal.{Unlike theauto-correlationfunction,thecross-cor relationfunctionis ;Y(t1; t2)6=RX;Y(t2; t1)ES150{ Harvard SEAS9 Cross-covariancefunction:CX;Y(t1; t2)=E[fXt1 mX(t1)gfYt2 mY(t2)g]=RX;Y(t1; t2) mX(t1)mY(t2){IfCX;Y(t1; t2) = 0 forallt1andt2, processesX(t) andY(t) areuncorrelated. Two processesX(t) andY(t) areindependentif any two vectorsoftimesamples,onefromeach process,areindependent.}}}}}}

5 {IfX(t) andY(t) areindependent thentheyareuncorrelated:CX;Y(t1; t2) = 08t1; t2(thereverseis notalways true). Example:SignalplusnoiseY(t) =X(t) +N(t)whereX(t) andN(t) areindependent { Harvard SEAS10 StationaryrandomprocessesIn many randomprocesses, , eventhoughtheprocessis Strict-sensestationarity:{A processisnth orderstationaryif thejoint distributionof any setofntimesamplesis independent of theplacement of thetimeorigin.[X(t1); : : : ; X(tn)] [X(t1+ ); : : : ; X(tn+ )]8 For a discreteprocess:[X1; : : : ; Xn] [X1+m; : : : ; Xn+m]8m{A processthatisnth orderstationaryforeveryintegern >0 is saidto bestrictlystationary, or juststationaryforshort.{ stationary. Strictstationarity is a { Harvard SEAS11{First-orderstationaryprocesses:fX (t)(x) =fX(x) forallt. ThusmX(t)=m8tvar(Xt)= 28t{Second-orderstationaryprocesses:fX(t 1);X(t2)(x1; x2) =fX(t1+ );X(t2+ )(x1; x2)8 Thesecond-orderjoint pdf (pmf) dependsonlyonthetimedi erencet2 t1.}}}}}}}}

6 ThisimpliesRX(t1; t2)=RX(t2 t1)CX(t1; t2)=CX(t2 t1)ES150{ Harvard SEAS12 Wide-sensestationaryrandomprocesses X(t) iswide-sensestationary(WSS)if thefollowingtwo propertiesbothhold:mX(t)=m8tRX(t1; t2)=RX(t2 t1)8t1; t2{WSSis a much morerelaxedconditionthanstrict-sensestat ionarity.{ WSSprocessis notalways strictlystationary.{Example:Sequenceof independent 'sXn= 1 withprobability12fornevenXn= 1=3 and3 withprobabilities910and110fornodd Propertiesof a WSSprocess:{RX(0)is theaveragepowerof theprocessRX(0)=E[X(t)2] 0RX(0)thus is always { Harvard SEAS13{RX( ) is anevenfunctionRX( ) =RX( ){RX( ) is maximumat = 0jRX( )j RX(0){IfRX(0)=RX(T) thenRX( ) is periodicwithperiodTifRX(0)=RX(T)thenRX( ) =RX( +T)8 {RX( ) measurestherateof changeof theprocessP[jX(t+ ) X(t)j> ] 2 (RX(0) RX( )) 2 If a Gaussianprocessis WSS,thenit is alsostrictlystationary.{A WWSG aussianprocessis completelyspeci edby theconstantmeanmandcovarianceCX( ).}}}}}}}}}}}

7 WSSprocessesplay a crucialrolein lineartime-invariant { Harvard SEAS14 Cyclostationaryrandomprocesses Many processesinvolves therepetitionof a procedurewithperiod T. A randomprocessiscyclostationaryif thejoint distributionof any setof samplesis invariant over a timeshiftofmT(mis aninteger)[X(t1); : : : ; X(tn)] [X(t1+mT); : : : ; X(tn+mT)]8m; n; t1; : : : ; tn A processiswide-sensecyclostationaryif forallintegermmX( +mT)=mX( )RX(t1+mT; t2+mT)=RX(t1; t2){IfX(t) is WSS,thenit is alsowide-sensecyclostationary. We canobtaina stationaryprocessXs(t) froma cyclostationaryprocessX(t) asXs(t) =X(t+ ); U[0; T]{IfX(t) is wide-sensecyclostationarythenXs(t) is { Harvard SEAS15 Timeaveragesandergodicity Sometimeswe needto estimatetheparametersof a randomprocessthroughmeasurement. A quantity obtainablefrommeasurements is theensembleaverage. Forexample,anestimateof themeanis^mX(t) =1 NNXi=1X(t; !i)where!iis theith outcomeof theunderlyingrandomexperiment.}}}}

8 {In general,sincemX(t) is a functionof time,we needto performNrepetitionsof theexperiment at each timetto estimatemX(t). If theprocessis stationary, however,thenmX(t) =mforallt. Thenwe may askifmcanbe estimatedbasedontherealization(over time)of a singleoutcome!alone. We de nethetimeaverageover aninterval 2 Tof a singlerealizationashX(t)iT=12 TZT TX(t; !)dtES150{ Harvard SEAS16 Question: Whendoes thetimeaverageconvergeto theensembleaverage? Example1: IfXn=X(n; !) is a stationary, [Xn] =m, thenby thestrongLLN1 NNXi= !masN!1=)Convergence. Example2:X(t) =Aforallt, whereAis a (t) is stationaryandmX=E[A] = 0 forallt, buthX(t)iT=12 TZT TA dt=A=)Noconvergence. Ergodicity letus characterizethisconvergencefora { Harvard SEAS17 Ergodicity of a WSSprocess Considera WSSrandomprocessX(t) (t) ismean-ergodicifhX(t)iT !masT!1 Notes:{Becauseof stationarity, theexpectedvalueofhX(t)iTisE[hX(t)iT] =E"12 TZT TX(t)dt#=12 TZT TE[X(t)]dt=m{Mean-ergodicde nitionthereforeimpliesthathX(t)iTapproac hesitsmeanasT!}}}}}

9 1. Mean-ergodictheorem:TheWSSprocessX(t) is mean-ergodicin themean-squaresense,thatislimT!1Eh(hX(t) iT m)2i= 0if andonlyif itscovariancesatis eslimT!112 TZT T 1 juj2T CX(u)du= 0ES150{ Harvard SEAS18}