03 - Generating Functions

Probability Generating Functions

Let $X$ be a random variable taking non-negative integer values then

Probability Generating Function of $X$ is defined by $G:\mathcal{S}\to \mathbb{R}$ where

$$\mathcal{S}=\left\{s\in \mathbb{R}:\sum _{k=0}^{\infty }|s{|}^k{p}_X(k)<\infty \right\}$$

with $p_X$ is the probability mass function of $X$ and

$$G(s):=\mathbb{E}[s^X]=\sum _{k=0}^{\infty }{p}_X(k)s^k,s\in \mathcal{S}$$

Generating Function of a Sum of Independent Random Variables

Let $X$ and $Y$ be independent random variable with generating functions $G_X$ and $G_Y$ then

$$G_{X+Y}(s)=G_X(s)G_Y(s)$$

Proof

$$\begin{array}{rl}{G}_{X+Y}(s)& =\mathbb{E}[s^{X+Y}]\\ & =\mathbb{E}[s^X{s}^Y]\\ & =\mathbb{E}[s^X]\mathbb{E}[s^Y](\text{by independence})\\ & =G_X(s)G_Y(s)\end{array}$$

Generating Function of a Random Sum

Let $X_1,X_2,\cdots$ be i.i.d. random variables (taking non-negative integer values)
Let $N$ be a random variable taking non-negative integer values independent of $X_i$

Let

$$S=X_1+X_2+\cdots +X_n$$

Then

$$G_S(z)=G_N(G_X(z))$$

Proof

$$\begin{array}{rl}{G}_S(z)& =\mathbb{E}[z^S]\\ & =\mathbb{E}[z^{X_1+X_2+\cdots +X_N}]\\ & =\sum _{n=0}^{\infty }\mathbb{E}[z^{X_1+X_2+\cdots +X_n}\mid N=n]\mathbb{P}(N=n)\\ & =\sum _{n=0}^{\infty }\mathbb{E}[z^{X_1+X_2+\cdots +X_n}]\mathbb{P}(N=n)(\text{by independence})\\ & =\sum _{n=0}^{\infty }(\mathbb{E}[z^{X_1}]{)}^n\mathbb{P}(N=n)(\text{by independence})\\ & =\mathbb{E}[(G_X(z){)}^N]\\ & =G_N(G_X(z))\end{array}$$

Moment Generating Function

Let $X$ be a random variable then

Moment Generating Function is defined by

$$M_X(t):=\mathbb{E}[e^{tX}]$$

with $M_X:\mathbb{R}\to [0,\infty ]$

Proof of WLLN using Moment Generating Functions

Let $X_1,X_2,\cdots$ be a sequence of i.i.d. random variables with mean $\mu$, variance ${\sigma }^2$ and MGF $M$
Let $S_n=X_1+X_2+\cdots +X_n$

Consider expansion of $M$ as a power series around $0$ as $h\to 0$ then

$$\begin{array}{rl}M(h)& =M(0)+M(0)+h{M}^{\prime }(0)+o(h)\\ & =1+h\mu +o(h)\end{array}$$

Let ${\overline{M}}_n$ be the mgf of $\frac{S_n}{n}$

By independence of ${\mathbf{x}}_i$ then

$$\begin{array}{rl}{\overline{M}}_n(t)& =\mathbb{E}\left[e^{t\frac{S_n}{n}}\right]\\ & =\mathbb{E}[e^{t{X}_1/n}\cdots e^{t{X}_n/n}]\\ & ={\left(M\left(\frac{t}{n}\right)\right)}^n\\ & ={\left(1+\frac{t}{n}\mu +o\left(\frac{t}{n}\right)\right)}^n\text{ as }n\to \infty \\ & \to e^{t\mu }\text{ as }n\to \infty \end{array}$$

where $e^{t\mu }$ is the mgf of random variable which takes constant value $\mu$ with probability $1$

By Continuity Theorem for Moment Generating Functions then

$$\frac{S_n}{n}\stackrel{d}{\to }\mu \text{ as }n\to \infty$$

Proof of CLT using Moment Generating Functions

Let $X_1,X_2,\cdots$ be a sequence of i.i.d. random variables with mean $\mu$, variance ${\sigma }^2$
Let $Y_i=X_i-\mu$ with mgf $M_Y$

Consider expansion of $M_Y$ as a power series around $0$ as $h\to 0$ then

$$\begin{array}{rl}{M}_Y(h)& =M_Y(0)+h{M}_Y^{\prime }(0)+\frac{h^2}{2}{M}_Y^{\prime \prime }(0)+o(h^2)\\ & =1+h\mathbb{E}[Y]+\frac{h^2}{2}\text{var}(Y)+o(h^2)\\ & =1+\frac{h^2{\sigma }^2}{2}+o(h^2)\end{array}$$

Let ${\tilde{M}}_n$ be mgf of $\frac{S_n-\mu n}{\sigma \sqrt{n}}$ then

$$\begin{array}{rl}{\tilde{M}}_n(t)& =\mathbb{E}\left[\exp \left(\frac{t(S_n-\mu n)}{\sigma \sqrt{n}}\right)\right]\\ & =\mathbb{E}\left[\exp \left(\frac{t(X_1-\mu )}{\sigma \sqrt{n}}\right)\cdots \exp \left(\frac{t(X_n-\mu )}{\sigma \sqrt{n}}\right)\right]\\ & =M_Y{\left(\frac{t}{\sigma \sqrt{n}}\right)}^n\\ & ={\left(1+\frac{t^2}{2n}+o\left(\frac{t^2}{n}\right)\right)}^n\text{ as }n\to \infty \\ & \to \exp \left(\frac{t^2}{2}\right)\text{ as }n\to \infty \end{array}$$

where $\exp \left(\frac{t^2}{2}\right)$ is mgf of $N(0,1)$

By Continuity Theorem for Moment Generating Functions then

$$\frac{S_n-\mu n}{\sigma \sqrt{n}}\stackrel{d}{\to }N(0,1)$$

Chernoff Bound for Simple Random Walk

Let $X_i$ be i.i.d taking values $-1$ and $1$ with probability $\frac{1}{2}$ each
Let $S_n=X_1+\cdots +X_n$ so it is the position after $n$ steps then

$$\mathbb{P}(|S_n|>na)\le 2\exp \left(-\frac{n{a}^2}{2}\right)$$

Characteristic Function

Let $X$ be a random variable then

Characteristic Function of $X$ is given by

$${\varphi }_X(t):=\mathbb{E}[e^{itX}]\text{ for }t\in \mathbb{R}$$

So

$${\varphi }_X(t)=\mathbb{E}[\cos (tX)]+i\mathbb{E}[\sin (tX)]$$