Chapter 4: Generating Functions - Auckland

1 74 Chapter 4: Generating FunctionsThis Chapter looks at Probability Generating Functions (PGFs) fordiscreterandom variables. PGFs are useful tools for dealing with sums and limits ofrandom variables. For some stochastic processes, they alsohave a special rolein telling us whether a process willeverreach a particular the end of this Chapter , you should be able to: find the sum of Geometric, Binomial, and Exponential series; know the definition of the PGF, and use it to calculate the mean, variance,and probabilities; calculate the PGF for Geometric, Binomial, and Poisson distributions; calculate the PGF for a randomly stopped sum; calculate the PGF for first reaching times in the random walk; use the PGF to determine whether a process willeverreach a given sums1.

2 Geometric Series1 +r+r2+r3+..= Xx=0rx=11 r,when|r|< formula proves thatP x=0P(X=x) = 1 whenX Geometric(p):P(X=x) =p(1 p)x Xx=0P(X=x) = Xx=0p(1 p)x=p Xx=0(1 p)x=p1 (1 p)(because|1 p|<1)= Binomial TheoremFor anyp, q R, and integern,(p+q)n=nXx=0 nx pxqn that nx =n!(n x)!x!(nCrbutton on calculator.)The Binomial Theorem proves thatPnx=0P(X=x) = 1 whenX Binomial(n, p):P(X=x) = nx px(1 p)n xforx= 0,1, .. , n, sonXx=0P(X=x) =nXx=0 nx px(1 p)n x= p+ (1 p) n= 1n= Exponential Power SeriesFor any R, Xx=0 xx!=e .This proves thatP x=0P(X=x) = 1 whenX Poisson( ):P(X=x) = xx!e forx= 0,1,2, .., so Xx=0P(X=x) = Xx=0 xx!e =e Xx=0 xx!

3 =e e = :Another useful identity is:e = limn 1 + n nfor Generating FunctionsTheprobability Generating function (PGF)is a useful tool for dealingwithdiscreterandom variables taking values 0,1,2, .. Its particular strengthis that it gives us an easy way of characterizing the distribution ofX+YwhenXandYare independent. In general it is difficult to find the distribution ofa sum using the traditional probability function. The PGF transforms a suminto a product and enables it to be handled much more of random variables are particularly important in the study of stochasticprocesses, because many stochastic processes are formed from the sum of asequence of repeating steps: for example, the Gambler s Ruin from Section nameprobability Generating functionalso gives us another clue to the roleof the PGF.

4 The PGF can be used to generate all the probabilities of thedistribution. This is generally tedious and is not often an efficient way ofcalculating probabilities. However, the fact that itcanbe done demonstratesthatthe PGF tells us everything there is to know about the :LetXbe a discrete random variable taking values in the non-negativeintegers{0,1,2, ..}. Theprobability Generating function (PGF)ofXisGX(s) =E(sX), for alls Rfor which the sum the probability Generating functionGX(s) =E sX = Xx=0sxP(X=x).Properties of the (0) =P(X= 0):GX(0) = 00 P(X= 0) + 01 P(X= 1) + 02 P(X= 2) +.. GX(0) =P(X= 0). (1) = 1 :GX(1) = Xx=01xP(X=x) = Xx=0P(X=x) = 1:Binomial DistributionLetX Binomial(n, p), soP(X=x) = nx pxqn xforx= 0,1.

5 , (s) =nXx=0sx nx pxqn x=nXx=0 nx (ps)xqn x= (ps+q)nby the Binomial Theorem: true for (s) = (ps+q)nfor alls (s) 20 10010050100150200X ~ Bin(n=4, p= )CheckGX(0):GX(0) = (p 0 +q)n=qn=P(X= 0).CheckGX(1):GX(1) = (p 1 +q)n= (1)n= 2:Poisson DistributionLetX Poisson( ), soP(X=x) = xx!e forx= 0,1,2, ..GX(s) = Xx=0sx xx!e =e Xx=0( s)xx!=e e( s)for alls (s) =e (s 1)for alls (s) ~ Poisson(4)Example 3:Geometric DistributionLetX Geometric(p), soP(X=x) =p(1 p)x=pqxforx= 0,1,2, ..,whereq= 1 p. 505012345G(s)sto infinityX ~ Geom( )GX(s) = Xx=0sxpqx=p Xx=0(qs)x=p1 qsfor allssuch that|qs|< (s) =p1 qsfor|s|< the probability Generating function to calculate probabilitiesThe probability Generating function gets its name because the power series canbe expanded and differentiated to reveal the individual probabilities.

6 Thus,given only the PGFGX(s) =E(sX), we can recover all probabilitiesP(X=x).For shorthand, writepx=P(X=x). ThenGX(s) =E(sX) = Xx=0pxsx=p0+p1s+p2s2+p3s3+p4s4+..Thusp0= P(X= 0) =GX(0).First derivative:G X(s) =p1+ 2p2s+ 3p3s2+ 4p4s3+..Thusp1=P(X= 1) =G X(0).Second derivative:G X(s) = 2p2+ (3 2)p3s+ (4 3)p4s2+..Thusp2=P(X= 2) =12G X(0).Third derivative:G X(s) = (3 2 1)p3+ (4 3 2)p4s+..Thusp3=P(X= 3) =13!G X(0).In general:pn=P(X=n) = 1n! G(n)X(0) = 1n! dndsn(GX(s)) s= :LetXbe a discrete random variable with PGFGX(s) =s5(2 + 3s2).Find the distribution (s) =25s+35s3:GX(0) =P(X= 0) = X(s) =25+95s2:G X(0) =P(X= 1) = X(s) =185s:12G X(0) =P(X= 2) = X(s) =185:13!

7 G X(0) =P(X= 3) = (r)X(s) = 0 r 4 :1r!G(r)X(s) =P(X=r) = 0 r 1with probability2/5,3with probability3 of the PGFThe formulapn=P(X=n) = 1n! G(n)X(0) shows that the whole sequence ofprobabilitiesp0, p1, p2, ..is determined by the values of the PGF and its deriv-atives ats= 0. It follows that the PGF specifies auniqueset of :If two power series agree on any interval containing 0, however small, thenall terms of the two series are : letA(s) andB(s) be PGFs withA(s) =P n=0ansn,B(s) =P n= there exists someR >0 such thatA(s) =B(s) for all R < s < R , thenan=bnfor use:If we can show that two random variables have the same PGF insome interval containing 0, then we have shown thatthe two random variableshave the same way of expressing this is to say thatthe PGF ofXtells us everythingthere is to know about the distribution and moments from the PGFAs well as calculating probabilities, we can also use the PGFto calculate themoments of the distribution ofX.

8 The moments of a distribution arethe mean,variance, :LetXbe a discrete random variable with PGFGX(s). (X) =G X(1). (X 1)(X 2)..(X k+ 1)o=G(k)X(1) =dkGX(s)dsk s=1.(This is thekth factorial momentofX.)Proof:(Sketch: see Section for more details) (s) = Xx=0sxpx,soG X(s) = Xx=0xsx 1px G X(1) = Xx=0xpx=E(X)sG(s) ~ Poisson(4) (k)X(s) =dkGX(s)dsk= Xx=kx(x 1)(x 2)..(x k+ 1)sx kpxsoG(k)X(1) = Xx=kx(x 1)(x 2)..(x k+ 1)px=EnX(X 1)(X 2)..(X k+ 1)o. 82 Example:LetX Poisson( ). The PGF ofXisGX(s) =e (s 1). FindE(X)and Var(X).Solution:sG(s) ~ Poisson(4)G X(s) = e (s 1) E(X) =G X(1) = .For the variance, considerEnX(X 1)o=G X(1) = 2e (s 1)|s=1= (X) =E(X2) (EX)2=EnX(X 1)o+EX (EX)2= 2+ 2=.

9 Generating function for a sum of independent of the PGF s greatest strengths is that it turns a sum intoa product:E s(X1+X2) =E sX1sX2 .This makes the PGF useful for finding the probabilities and moments ofa sumof independent random :Suppose thatX1, .. , Xnareindependentrandom variables, andletY=X1+..+Xn. ThenGY(s) =nYi=1 GXi(s).83 Proof:GY(s) =E(s(X1+..+Xn))=E(sX1sX2.. sXn)=E(sX1)E(sX2)..E(sXn)(becauseX1, .. , Xnare independent)=nYi=1 GXi(s).as required. Example:Suppose thatXandYare independent withX Poisson( ) andY Poisson( ). Find the distribution ofX+ :GX+Y(s) =GX(s) GY(s)=e (s 1)e (s 1)=e( + )(s 1).But this is the PGF of the Poisson( + )distribution.

10 So, by the uniqueness ofPGFs,X+Y Poisson( + ). stopped sumRemember the randomly stopped sum model fromSection A random numberNof events occur,and each eventihas associated with it a cost orrewardXi. The question is to find the distributionof the total cost or reward:TN=X1+X2+..+ called arandomly stopped sumbecause it has a random number of :Cash machine arrive during the day. Customeriwithdraws amountXi. The total amount withdrawn during the day isTN=X1+..+ Chapter 3, we used the Laws of Total Expectation and Variance to showthatE(TN) = E(N) and Var(TN) = 2E(N) + 2 Var(N), where =E(Xi)and 2= Var(Xi).In this Chapter we will now use probability Generating Functions to investigatethewhole distribution :LetX1, X2.