03. Generating Functions

3.1 Review of Probability 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}$$

Link to original

Properties of the Probability Generating Function

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

$$G^{(k)}(0)=k!p_X(k)\text{ for }k=0,1,2,\cdots$$

$$G(1)=1\text{ and }{G}^{(k)}(1)=\mathbb{E}[X(X-1)\cdots (X-k+1)]\text{ for }k=1,2,\cdots$$

Note that a distribution is determined by its generating function

Link to original

Uniqueness Theorem for Probability Generating Functions

If $X$ and $Y$ have same generating function then

$$X\text{ and }Y\text{ have same distribution}$$

Link to original

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}$$

Link to original

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}$$

Link to original

---

3.2 Moment Generating Functions

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 ]$

Link to original

---

3.2.1 Examples and Basic Results about Moment Generating Functions

Properties of the Moment Generating Function

Let $X$ be a random variable

1. Let $Y=aX+b$ for some $a,b\in \mathbb{R}$

$$M_Y(t)=e^{bt}{M}_X(at)$$

2. Let $X_1,\cdots ,X_n$ be independent random variables with mgfs $M_{X_1},\cdots ,M_{X_N}$ then
   Mgf of sum is defined by

$$M_{X_1+\cdots +X_n}(t)=M_{X_1}(t)\cdots M_{X_n}(t)$$

Link to original

Taylor Expansion of the Moment Generating Function

Suppose $M_X(t)$ is finite for $|t|\le t_0$ for some $t_0>0$ then

$$M_X(t)=\sum _{k=0}^{\infty }\frac{t^K\mathbb{E}[X^k]}{k!}\text{ for }|t|\le t_0$$

$$M_X^{(k)}(0)=\mathbb{E}[X^k]$$

Proof - Informal

$$\begin{array}{rl}{M}_X(t)& =\mathbb{E}[e^{tX}]\\ & =\mathbb{E}\left[1+tX+\frac{(tX{)}^2}{2!}+\frac{(tX{)}^3}{3!}+\cdots \right]\\ & =1+t\mathbb{E}[X]+\frac{t^2\mathbb{E}[X^2]}{2!}+\frac{t^3\mathbb{E}[X^3]}{3!}+\cdots \end{array}$$

Link to original

Uniqueness Theorem for Moment Generating Functions

Let $X$ and $Y$ be random variables with the same moment generating function
which is finite on $[-t_0,t_0]$ for some $t_0>0$ then

$$X\text{ and }Y\text{ have the same distribution}$$

Link to original

Continuity Theorem for Moment Generating Functions

Let $Y$ and $X_1,X_2,\cdots$ be random variables with mgfs $M_Y$ and $M_{X_1},M_{X_2},\cdots$
which are finite on $[-t_0,t_0]$ for some $t_0>0$

If

$$M_{X_n}(t)\to M_Y(t)\text{ as }n\to \infty \text{ for all }t\in [-t_0,t_0]$$

Then

$$X_n\stackrel{d}{\to }Y\text{ as }n\to \infty$$

Link to original

---

3.2.2 Proof of WLLN and CLT using Moment Generating Functions

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$$

Link to original

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)$$

Link to original

---

3.3 Using Moment Generating Functions for Tail Bounds

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)$$

Link to original

---

3.4 Characteristic Functions

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)]$$

Link to original