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. 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!

2 (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!=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.

3 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, .. , (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!

4 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. 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!

5 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!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.

6 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= . 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+.

7 +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. 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).

8 In this Chapter we will now use probability Generating Functions to investigatethewhole distribution :LetX1, X2, ..be a sequence of independent and identically dis-tributed random variables with common PGFGX. LetNbe a random variable,independent of theXi s, with PGFGN, and letTN=X1+..+XN=PNi= the PGF ofTNis:GTN(s) =GN GX(s) .Proof:GTN(s) =E(sTN) =E sX1+..+XN =ENnE sX1+..+XN N o(conditional expectation)=ENnE sX1.. sXN|N o=ENnE sX1.. sXN o(Xi s are indept ofN)=ENnE sX1 ..E sXN o(Xi s are indept of each other)=ENn(GX(s))No=GN GX(s) (by definition ofGN). 85 Example:LetX1, X2, ..andNbe as above. Find the mean (TN) =G TN(1) =ddsGN(GX(s)) s=1=G N(GX(s)) G X(s) s=1=G N(1) G X(1)Note:GX(1) = 1for any (N) E(X1), same answer as in Chapter :Heron goes fishingMy aunt was asked by her neighbours to feed the prizegoldfish in their garden pond while they were on my aunt dutifully went and fed them every day,she never saw a single fish for the whole three weeks.

9 Itturned out that all the fish had been eaten by a heronwhen she wasn t looking!LetNbe the number of times the heron visits the pondduring the neighbours absence. Suppose thatN Geometric(1 ),soP(N=n) = (1 ) n,forn= 0,1,2, .. When the heron visits the pondit has probabilitypof catching a prize goldfish, independently of what happenson any other visit. (This assumes that there are infinitely many goldfish to becaught!) Find the distribution ofT= total number of goldfish :LetXi= 1if heron catches a fish on visiti, +X2+..+XN(randomly stopped sum), soGT(s) =GN(GX(s)).86 NowGX(s) =E(sX) =s0 P(X= 0) +s1 P(X= 1) = 1 p+ ,GN(r) = Xn=0rnP(N=n) = Xn=0rn(1 ) n= (1 ) Xn=0( r)n=1 1 r.(r <1/ ).SoGT(s) =1 1 GX(s)(puttingr=GX(s)),giving:GT(s) =1 1 (1 p+ps)=1 1 + p ps[could this be Geometric?GT(s) =1 1 sfor some ?]=1 (1 + p) ps= 1 1 + p (1 + p) ps1 + p 87= 1 + p p1 + p 1 p1 + p s=1 p1 + p 1 p1 + p is the PGF of the Geometric 1 p1 + p distribution, so by unique-ness of PGFs, we have:T Geometric 1 1 + p.

10 Why did we need to use the PGF?We could have solved the heron problem without using the PGF,but it is muchmore difficult. PGFs are very useful for dealing with sums of random variables,which are difficult to tackle using the standard probability are the first few steps of solving the heron problem without the the problem: LetN Geometric(1 ), soP(N=n) = (1 ) n; LetX1, X2, ..be independent of each other and ofN, withXi Binomial(1, p)(rememberXi= 1 with probabilityp, and 0 otherwise); LetT=X1+..+XNbe the randomly stopped sum; Find the distribution using the PGF, we would tackle this by looking for an expression forP(T=t) for anyt. Once we have obtained that expression, we might be ableto see thatThas a distribution we recognise ( Geometric), or otherwise wewould just state thatTis defined by the probability function we have findP(T=t), we have topartition over different values ofN:P(T=t) = Xn=0P(T=t|N=n)P(N=n).( )Here, we areluckythat we can write down the distribution ofT|N=n: ifN=nis fixed, thenT=X1+.