# Generating Functions Now, having talking about generating functions, we should define what mean exactly. In mathematics, a [**generating function**](https://en.wikipedia.org/wiki/Generating_function) is a way of encoding an infinite sequence of numbers, $a_n$, by treating them as the coefficients of a power series. This formal power series is the generating function. Polya put this most acurately: > "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." #### Ordinary Generating Function The _ordinary generating function_ of a sequence $a_n$ is: $G(a_n ; x) = \sum_{n=0}^{\infty} a_n x^n$ Where if $a_n$ is the probability mass function of a discrete random variable, then this is called a _probability generating function_. #### Probability Generating Function The [**probability generating function**](https://en.wikipedia.org/wiki/Probability-generating_function) of a discrete random variable is a [power series](https://en.wikipedia.org/wiki/Power_series) representation (the generating function) of the probability mass function of the random variable. If $X$ is a discrete random variable (non negative), then the probability generating function of $X$ is defined as: $G(z) = E \big[ z^X \big] = \sum_{x=0}^{\infty} p(x) z^x$ Where $p$ is the probability mass function of $X$. ##### Example Consider for a moment a binomial random variable, with a PMF: $f(x, n, p) = \binom{n}{x} p^x (1-p)^{n-x} $ Where $x$ is the number of successes in $n$ trials, with probability of success $p$ in each trial. It's probability generating function is: $G(z) = E(z^X) = \sum_{x=0}^{n} f(x, n, p) z^x$ $G(z) = \sum_{x=0}^{n} f(x, n, p) z^x = f(0, n, p) z^0 + f(1, n, p) z^1 + f(2, n, p)z^2 + \dots + f(n, n, p) z^n $ Where, since $f(x, n, p)$, for a given number of successes, $x$, is equivalent to $\binom{n}{x} p^x(1-p)^{n-x}$: $G(z) = \sum_{x=0}^{n} \binom{n}{x} p^x(1-p)^{n-x} z^x = \sum_{x=0}^{n} \binom{n}{x} (pz)^x(1-p)^{n-x} $ And, via the [binomial theorem](https://en.wikipedia.org/wiki/Binomial_theorem) we can write this as: $G(z) = \sum_{x=0}^{n} \binom{n}{x} (pz)^x(1-p)^{n-x} = \Big( (1-p) + pz \Big)^n$ $G(z) = \Big( (1-p) + pz \Big)^n$ #### Relationship between Probability Generating Function and Moment Generating Function Since the probability generating function is defined as: $G(z) = E \big[ z^X \big] = \sum_{x=0}^{\infty} p(x) z^x$ And the moment generating function: $M_X(t) = E \big[ e^{tX} \big]$ We can then define: $log(z) = t$ So that $e^t = z $. Then: $G(z) = E[z^X] = E[e^t]^X = E[e^{tX}] = M_X(t) = M_X(logz)$ Hence, the relationsip is simply: $G(z) = M_X (log(z))$ Summarized as: > The probability generating function is usually used for (nonnegative) integer valued random variables, but is really only a repackaging of the moment generating function. So the two contains the same information. --- Date: 20210825 Links to: [Mathematics MOC](Mathematics%20MOC.md) [Moment-Generating-Function](Moment-Generating-Function.md) Tags: References: * Moments and Characteristic Functions notebook in math appendix of intuitively ML