Search

Navigation

User login

Upcoming events

No upcoming events available

There are 497 members of the Warwick Mathematics Society, of which 0 are new today!
We're 99% of the way toward our target of 500 members.
You can join up on the UWSU website.

Who's new

Generating functions

Planktonboy

Posted: Submitted by Planktonboy on 21 February 2008 - 2:49am.

Joined: 2007-10-04
Posts: 188

Err, I fell asleep for most of the content of today's (yesterday's in fact) Prob B lecture. And the stuff on wikipedia didn't quite seem relavent in a probability setting. Can someone please briefly explain what they are and what they do.

edit: and then I find the probability-generating function page... Posting at 2 in the morning is as bad as posting drunk

Xedi

Posted: 21 February 2008 - 3:17am

Joined: 2007-10-03
Posts: 373

Honestly probability generating functions are totally useless, there's a reason why noone bothers with them today...

Buggs

Posted: 21 February 2008 - 12:28pm

Joined: 2006-10-05
Posts: 674

The problem is that with prob B, thy're sort of central to the entire module.

Prob B $\iff$ Generating Funtions

cosmin

Posted: 21 February 2008 - 1:44pm

Joined: 2006-11-02
Posts: 1004

They are actually very handy, they make a lot of things way easier. They're pretty much like regular generating functions: suppose you have a random variable $X:\; \mathbb{N}_0 \to [0,1]$ , its generating function is just

$G_X(z) := \sum_{n = 0}^\infty \boldsymbol{P}(X = n) z^n,$

i.e. the regular generating function for the sequence $(\boldsymbol{P}(X = n))_{n\geqslant 0}$ . Note that for $z = 1$ the sum is equal to 1, so it converges for $z\in [-1,1]$ . Note also that you can write $G_X(x) = \boldsymbol{E} [z^X]$ , which is useful for some proofs. To start with an easy property is that $\boldsymbol{P}(X = n) = G_X^{(n)}(0)/n!$ . Pushing this a bit further, differentiating the whole generating function is quite useful because we get

$G_X'(z) := \sum\limits_{n = 0}^\infty n \boldsymbol{P}(X = n) z^{n-1}$

so (surprise!) $G_X'(1) = \boldsymbol E [X]$ . Differentiating twice gives you

$G_X'(z) := \sum\limits_{n = 0}^\infty n(n-1) \boldsymbol{P}(X = n) z^{n-2} = \sum_{n = 0}^\infty n^2 \boldsymbol{P}(X = n) z^n - \sum_{n = 0}^\infty n \boldsymbol{P}(X = n) z^n$

and thus $G_X''(1) + G_X'(1) = \boldsymbol E [X^2]$ , the second moment of $X$ , which makes it easy to calculate the variance. One last (awesome) result is that if you have a random variable $Y$ which models a sum of $N$ identically distributed random variables $X_i$ (where $N$ is also a (positive) random variable, i.e. $Y = \sum\limits_{i = 1}^N X_i$ ) then the generating function of $Y$ is just $G_Y(z) = G_N(G_{X_1}(z))$ , which is extremely powerful (note the special case if you're just summing $N = n$ random variables all the time $G_Y(z) = (G_{X_1}(z))^n$ ).

A few examples of generating functions of common distributions:
Bernoulli: $\displaystyle \omega \sim B(p)$ gives $\displaystyle G_\omega(z) = (1-p) + pz$ .

Binomial: $\displaystyle X \sim \mathcal B(p,n)$ gives $\displaystyle G_X(z) = \sum_{k=0}^n \binom{n}{k}p^k(1-p)^{n-k}z^k = (1-p + pz)^n$ (note the last theorem I was talking about coming into play).

Poisson: $\displaystyle Y \sim \mathcal P(\lambda)$ gives $\displaystyle G_Y(z) = \sum_{k=0}^\infty\frac{\lambda^k e^{-\lambda}}{k!} z = e^{(\lambda - 1)z}$

Geometric: $\displaystyle Z \sim \mathcal G(p)$ gives $\displaystyle G_Z(z) = \sum_{k = 1}^\infty p (1-p)^{k-1} z^k = \frac{zp}{1-z(1-p)}$

P.S. There's also a second type of generating function, the so-called "moment generating function" which is defined (for a random variable $X$ ) by

$M_X(z) := \boldsymbol E[e^{zX}],$

but it's somewhat less useful (not to be confused with the exponential generating function $\sum_{n\geqslant 0} \frac{1}{n!}\boldsymbol{P}(X = n) z^n$ ). It's useful if you can more easily calculate this one than the normal one though (e.g. for the negative binomial).

Edit: Crap, I just noticed your edit. Ah well... :p

Buggs

Posted: 21 February 2008 - 1:56pm

Joined: 2006-10-05
Posts: 674

This explains how you actually managed the class test!

Newtonswig

Posted: 21 February 2008 - 1:56pm

Joined: 2006-10-01
Posts: 427

Still, well defended old thing- it's often tempting in maths to throw out the baby with the bath water as it were. The seemingly pointless and the utterly baffling are often rejected as esoteric and useless too readily.

Miss one "motivation" lecture and you're stuck doing bland computation of something you really couldn't care less about.

cosmin

Posted: 22 February 2008 - 4:31am

Joined: 2006-11-02
Posts: 1004

Very true. I myself wondered what the point of using generating functions for probabilities was when I first saw them, being used to the normal reccurence relation type GF. Seeing them in action convinced me pretty quickly though and I was particularly impressed by that last theorem: it very often turns what could have been horrendous calculations into simple and elegant formulas.

Planktonboy

Posted: 5 March 2008 - 9:56am

Joined: 2007-10-04
Posts: 188

Now that I've been awake in the last few lectures, I'm gonna disagree that moment generating functions are less useful. They appear to work better with CRVs since powers of e integrate more easily. You could do it with ordinary GFs but this cuts out the leg-work

cosmin

Posted: 5 March 2008 - 1:54pm

Joined: 2006-11-02
Posts: 1004

Well, I didn't say they were useless, just less useful in most cases. For most random variables they're still much harder to compute.

Planktonboy

Posted: 5 March 2008 - 1:57pm

Joined: 2007-10-04
Posts: 188

Well the fact that we've used the MGF for every cts RV so far, and the normal one for every disc RV; Makes me think that their usefulness isn't related at all.