Generating Functions2021 May 20 See all posts
A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag.
- George Pólya, Mathematics and plausible reasoning (1954)
Probability generating function
We define a PGF as . for this article will be a discrete random variable.
This is an interesting defintion since by LOTUS with
The crazy idea here is we can use calculus on , since its an differentiable function!
Letting every term dies except the term which is
The general case of what we discovered is the nth derivative at zero being
That means we can recover each from the PGF , amazing!
Plugging in gives us by LOTUS
This is useful because finding expected values can be easier then finding probabilies since we have linearity.
Let and let be the number rolled by the 'th die
Since are independent we use the fact that if and indep
We know by LOTUS, plugging that in gives us
We know leading us to the amazing conclusion
The probability of six die summing to 18 is the coefficient of the term
Simplifying this to make finding the coefficients easier is now a matter of algebra not probability!
Take a polynomial, say the from the PGF of summing 3 fair dice
Think about getting the term, you can pick , and . but you could also pick different terms, like , and .
Counting the ways of picking the terms that have product is the same as counting dice rolls. except here we have the full power of algebra at our disposal.
Proof of expectation
(Assume X,Y are discrete, the continuous case is done by interchanging integrals)
Proof is by factoring out and then factoring out the sum
If you've done any probability you've likely come across a problem like this
What is the probability that the total after rolling 4 fair dice is 21?
When I heard this problem in stat110 strategic practice I tried to solve it in general, after spending several hours I gave up. It turns out the solution was just to manually list cases!
This bugged me, as a programmer I hate doing things manually. but not seeing a better way I continued on.
Interestingly, a similar thing happened to Frederick Mosteller in his sophomore year