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 $g(t) = E[t^X]$. for this article $X$ will be a **discrete** random variable.

This is an interesting defintion since by LOTUS with $p_k = P(X = k)$

The crazy idea here is we can use calculus on $g(t)$, since its an differentiable function!

Letting $t=0$ every term dies except the $k=1$ term which is $p_1 \cdot 1 \cdot 0^0 = p_1$

The general case of what we discovered is the nth derivative at zero being $p_n n!$

That means we can recover each $p_k = P(X = k)$ from the PGF $g(t) = E[t^X]$, amazing!

Plugging in $t=1$ gives us $E[X]$ by LOTUS

This is useful because finding expected values can be easier then finding probabilies since we have linearity.

## Dice problem

Let $X = X_1 + \dots + X_6$ and let $X_i$ be the number rolled by the $i$'th die

Since $X_i$ are independent we use the fact that $E[XY] = E[X]E[Y]$ if $X$ and $Y$ indep

We know $E[X_i] = \frac{1}{6}(t^1 + t^2 + \dots + t^6)$ by LOTUS, plugging that in gives us

We know $g^{(18)}(0) = P(X = 18)$ leading us to the amazing conclusion

The probability of six die summing to 18 is the coefficient of the $t^{18}$ term

Simplifying this to make finding the coefficients easier is now a matter of algebra not probability!

## Intuition

Take a polynomial, say the from the PGF of summing 3 fair dice $(t^1 + t^2 + \dots + t^6)^3$ Think about getting the $t^{10}$ term, you can pick $t^6$, $t^3$ and $t^1$. but you could also pick different terms, like $t^5$, $t^4$ and $t^1$.

Counting the ways of picking the terms that have product $t^{10}$ 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 $xP(X=x)$ and then factoring out the sum

## Background story

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^{1}