Generating Functions

Generating functions

A sequence $a = a_{i} | i = 0, 1, 2, \dots$ of real numbers may contain a lot of information. One concise way of storing this information is to wrap up the numbers together in a ``generating function”. For example, the (ordinary) generating function of the sequence $a$ is the function $G_{a}$ defined by $G_{a} (s) = \sum_{i = 0}^{\infty} a_{i} s^{i} for s \in R for which the sum converges.$ In many circumstances it is easier to work with the generating function $G_{a}$ than with the original sequence $a$ .

Theorem. [Abel's theorem] If $a_{i} \geq 0$ for all $i$ and $G_{a} (s)$ is finite for $| s | < 1$ , then $lim_{s ↑ 1} G_{a} (s) = \sum_{i = 1}^{\infty} a_{i}$ , whether the sum is finite or equals $+ \infty$ . This standard result is useful when the radius of convergence $R$ satisfies $R = 1$ , since then one has no a priori right to take the limit as $s ↑ 1$ .

Moment generating function

Definition. The **moment generating function** of the random variable $X$ is the function $M : R \mapsto [0, \infty)$ given by the Laplace transform of the corresponding p.d.f. $f_{X} (s)$ : $M_{X} (t) = E (e^{t X}) = \int_{- \infty}^{\infty} e^{t x} f_{X} (x) d x,$ or corresponding p.m.f. $p_{X} (k)$ : $M_{X} (t) = \sum_{k} e^{t k} P (X = k) = \sum_{k} \sum_{n = 0}^{\infty} \frac{(t k)^{n}}{n!} P (X = k) = \sum_{n = 0}^{\infty} \frac{t^{n}}{n!} (\sum_{k} k^{n} P (X = k)) = \sum_{n = 0}^{\infty} \frac{t^{n}}{n!} E (X^{n}) .$ $M_{X} (- t)$ is so called **bilateral** Laplace transform of $f_{X} (x)$ or $p_{X} (k)$ .

Under the assumption that $M_{X} (t)$ is infinitely differentiable at $t = 0$ , the following statements are true.

$M^{'} (0) = E (0) = μ$ .
$M^{(n)} (0) = E (X^{n})$ .
Using Taylor's theorem, $M_{X} (t) = \sum_{k = 0}^{\infty} \frac{t^{k}}{k!} E (X^{k})$ .

Theorem. If $X$ and $Y$ are independent, then $\begin{aligned} M_{X + Y} (t) & = \int_{- \infty}^{\infty} e^{t z} f_{x + y} (z) d z \\ = \int_{- \infty}^{\infty} e^{t z} \int_{- \infty}^{\infty} f_{X} (x) f_{Y} (z - x) d x d z \\ = \int_{- \infty}^{\infty} e^{t (x + y)} \int_{- \infty}^{\infty} f_{X} (x) f_{Y} (y) d x d y \\ = M_{X} (t) M_{Y} (t) . \end{aligned}$

Characteristic functions

Sometimes $E (e^{t X})$ may blow up. So we consider some transformations in the complex domain, which usually perform better.

Definition. The **characteristic function** of $X$ is the function $ϕ : R \mapsto C$ defined by $ϕ (t) = E (e^{i t X}) where i = \sqrt{- 1} .$ We often write $ϕ_{x}$ for the characteristic function of the random variable $X$ . Characteristic functions are related to Fourier transforms.

Theorem. The characteristic function $ϕ$ satisfies:

$ϕ (0) = 1$ , $| ϕ (t) | \leq 1$ for all $t$ .
$ϕ$ is uniformly continuous on $R$ w.r.t. $t$ .
If $X \sim N (0, 1)$ , then $ϕ_{X} (t) = e^{- t^{2} / 2}$ .

Proof ▸

We only prove the first statement. $\begin{aligned} | ϕ (t) | & = | \int_{- \infty}^{\infty} e^{i t x} f (x) d x | \\ \leq \int_{- \infty}^{\infty} | e^{i t x} | f (x) d x (triangle inequality) \\ = \int_{- \infty}^{\infty} f (x) d x (| e^{i t x} | = 1) \\ = 1 \end{aligned}$ ◼

Example. [Cauchy distribution] If $f (x) = \frac{1}{π (1 + x^{2})}$ , then the corresponding characteristic function is $ϕ (t) = \frac{1}{π} \int_{- \infty}^{\infty} \frac{e^{i t x}}{1 + x^{2}} d x = e^{- | t |} .$

Theorem. The following statements are true.

If $ϕ^{(k)} (0)$ exists, then ${\begin{cases} E | X^{k} | < \infty & if k is even \\ E | X^{k - 1} | < \infty & if k is odd \end{cases}$
If $E (| X^{k} |) < \infty$ , then $ϕ (t) = \sum_{j = 0}^{k} \frac{E (X^{j})}{j!} (i t)^{j} + o (t^{k})$ and so $ϕ^{(k)} (0) = i^{k} E (X^{k})$ .

Theorem. If $X$ and $Y$ are independent then $ϕ_{X + Y} (t) = ϕ_{X} (t) ϕ_{Y} (t) .$ Similarly, if $X_{1}, \dots, X_{n}$ are independent, then $ϕ_{X_{1} + \dots + X_{n}} (t) = \prod_{i = 1}^{n} ϕ_{X_{i}} (t) .$

Theorem. If $a, b \in R$ and $Y = a X + b$ , then $ϕ_{Y} (t) = e^{i t b} ϕ_{X} (a t)$ .

Proof ▸

$ϕ_{Y} (t) = E (e^{i t (a X + b)}) = E (e^{i t b} e^{i (a t) X}) = e^{i t b} E (e^{i (a t) X}) = e^{i t b} ϕ_{X} (a t) .$ ◼

Theorem. Random variables $X$ and $Y$ are independent if and only if $ϕ_{X, Y} (s, t) = ϕ_{X} (s) ϕ_{Y} (t) for all s and t .$

Definition. We say that the sequence $F_{1}, F_{2}, \dots$ of distribution functions converges to the distribution function $F$ , written $F_{n} \to F$ , if $F (x) = lim_{n \to \infty} F_{n} (x)$ at each point $x$ where $F$ is continuous.

Theorem. [Continnity theorem] Suppose that $F_{1}, F_{2}, \dots$ is a sequence of distribution functions with corresponding characteristic functions $ϕ_{1}, ϕ_{2}, \dots$ .

If $F_{n} \to F$ for some distribution function $F$ with characteristic function $ϕ$ , then $ϕ_{n} (t) \to ϕ (t)$ for all $t$ .
Conversely, if $ϕ (t) lim_{n \to \infty} ϕ_{n} (t)$ exists and is continuous at $t = 0$ , then $ϕ$ is the characteristic function of some distribution function $F$ , and $F_{n} \to F$ .

Central limit theorem

Definition. If $X, X_{1}, X_{2}, \dots$ is a sequence of random variables with respective distribution functions $F, F_{1}, F_{2}, \dots$ , we say that $X_{n}$ converges in distribution to $X$ , written $X_{n} \overset{D}{\to} X$ , if $F_{n} \to F$ as $n \to \infty$ .

Theorem. [Central limit theorem] Let $X_{1}, X_{2}, \dots$ be a sequence of independent identically distributed random variables with finite mean $μ$ and finite nonzero variance $σ^{2}$ , and let $S_{n} = X_{1} + X_{2} + \dots + X_{n}$ . Then $\frac{S_{n} - n μ}{\sqrt{n σ^{2}}} \overset{D}{\to} N (0, 1) as n \to \infty .$

Proof ▸

First, write $Y_{i} = \frac{X_{i} - μ}{σ}$ , and let $ϕ_{Y}$ be the characteristic function of the $Y_{i}$ . We have that $ϕ_{Y} (t) = 1 - \frac{1}{2} t^{2} + o (t^{2}) .$ Note that $Y_{i}$ are i.i.d. So the characteristic function of $\sum_{i = 1}^{n} Y_{i}$ is $ϕ_{n} = [ϕ_{Y} (t)]^{n} = {[1 - \frac{1}{2} t^{2} + o (t^{2})]}^{n} .$ Also, the characteristic function $ψ_{n}$ of $U_{n} = \frac{S_{n} - n μ}{\sqrt{n σ^{2}}} = \frac{1}{\sqrt{n}} \sum_{i = 1}^{n} Y_{i}$ satisfies $ψ_{n} (t) = {ϕ_{Y} (t / \sqrt{n})}^{n} = {1 - \frac{t^{2}}{2 n} + o (\frac{t^{2}}{n})}^{n} \to e^{- \frac{1}{2} t^{2}} as n \to \infty,$ where we used $lim_{n \to \infty} {(1 + \frac{a}{n})}^{n} = e^{a} .$ The last function is the characteristic function of the $N (0, 1)$ distribution, and an application of the continuity theorem completes the proof. ◼

Corollary. $Q_{n} = \frac{1}{n} S_{n} \to N (μ, \frac{σ^{2}}{n})$ , $S_{n} \to N (μ, n σ^{2})$ . The sampling error is proportional to $\frac{1}{\sqrt{n}}$ .

There is a generalization. If $X_{i}$ is not i.i.d., we can still use the central limit theorem.