User:Dom walden/Bivariate Generating Functions

Introduction

Combinatorial class = C

Combinatorial parameter = \chi or \zeta

P(X = k) = #(y \in C | X(y) = k) / #C

So X, \chi, \zeta is both a variable and function...

Or, P(E) = \mu(E) = \sum_{e \in E} p(e)

f(x) (pdf)

F(x) = P(X \leq x) = \int_{-\infty}^x f(u)du (cdf)

For continuous variable:

Fourier/characteristic: \lambda_X(s) = \int_{\R} e^{sx} f(x) dx

Laplace: \phi_X(t) = \int_{\R} e^{itx} f(x) dx

(I don't necessarily believe the above...)

X* = \zeta - E(\zeta) / \sqrt{V(\zeta)}

If Y = X - \mu / \sigma then

\phi_Y(t) = e^{-\mu it} \phi_X(t/\sigma)

\lambda_Y(s) = e^{-\mu s} \lambda_X(s/\sigma)

Characteristic function of standard normal:

1/\sqrt{2\pi} \int_R e^{itz} e^{-z^2/2} dz

Discrete limit law

This applies when the mean and standard deviation of the random variable remain finite.

Theorem

If $\Omega$ is a subset of the unit disc with at least one point of accumulation in the interior of the disc. If $p_{n}(u)=\sum _{k\geq 0}p_{n,k}u^{k}$, $q(u)=\sum _{k\geq 0}q_{k}u^{k}$ and pointwise for each $u\in \Omega$

$\lim _{n\to +\infty }p_{n}(u)=q(u)$

then

$\lim _{n\to +\infty }p_{n,k}=q_{k}$ and $\lim _{n\to +\infty }\sum _{j\leq k}p_{n,j}=\sum _{j\leq k}q_{j}$

Proof

Applying Vitali's theorem, we take the sequence to be $\{p_{n}(u)\}$ and $S$ to be the unit disc. All $p_{n}(u)$ are analytic and bounded on $S$ (due to $p_{n}(1)=1$). The theorem assumes that $\{p_{n}(u)\}$ converges to $q(u)$ in $\Omega \subset S$ which has an accumulation point in $S$.

Vitali's theorem states $\{p_{n}(u)\}$ uniformly converges to $q(u)$ on any compact subset of $S$, which we will take as the disc $|u|\leq 1/2$ and use Cauchy's coefficient formula:

$q_{k}={\frac {1}{2i\pi }}\int _{|u|=1/2}q(u){\frac {du}{u^{k+1}}}=\lim _{n\to \infty }{\frac {1}{2i\pi }}\int _{|u|=1/2}p_{n}(u){\frac {du}{u^{k+1}}}=\lim _{n\to \infty }p_{n,k}$

Vitali's theorem

Theorem

Let $\{f_{n}(z)\}$ be a sequence of functions, all analytic on an open connected set $S$ and $|f_{n}(z)|\leq M$ for all $n$ and $z$ in $S$.

If the sequence $\{f_{n}(z)\}$ converges on a subset of $S$ with a point of accumulation in $S$, then $\{f_{n}(z)\}$ converges uniformly on every compact subset of $S$.

Proof

Let

$f_{n}(z)=a_{0,n}+a_{1,n}z+\cdots$

We want to prove that each $a_{v,n}$ converges to a limit.

We start with a disc centred at the origin of radius $R$ and point of accumulation as the origin. Then

$|f_{n}(z)-f_{n}(0)|\leq |f_{n}(z)|+|f_{n}(0)|\leq 2M$

Let $z_{0}\neq 0$ be a point where the sequence converges. Then

$|f_{n}(0)-f_{n+m}(0)|\leq |f_{n}(0)-f_{n}(z_{0})|+|f_{n}(z_{0})-f_{n+m}(z_{0})|+|f_{n+m}(z_{0})-f_{n+m}(0)|\leq {\frac {4M|z_{0}|}{R}}+|f_{n}(z_{0})-f_{n+m}(z_{0})|$

because, by Schwarz's lemma, $|f_{n}(0)-f_{n}(z_{0})|\leq 2M|z_{0}|/R$ and $|f_{n+m}(z_{0})-f_{n+m}(0)|\leq 2M|z_{0}|/R$.

We choose $z_{0}$ such that the first term is arbitrarily small and $n$ large enough that the second term is arbitrarily small. Therefore, $f_{n}(0)=a_{0,n}$ converges to a limit.

Next, we define

$g_{n}(z)={\frac {f_{n}(z)-a_{0,n}}{z}}=a_{1,n}+a_{2,n}z+\cdots \leq {\frac {2M}{R}}$

For $|z|<R$. $g_{n}(z)$ converges to a limit at $z_{0}$ as both $f_{n}(z)$ and $a_{0,n}$ converge to a limit. We repeat the argument above, which proved that $f_{n}(0)=a_{0,n}$ converges to a limit, to prove that $g_{n}(0)=a_{1,n}$ also converges to a limit. We keep repeating this to prove that $a_{v,n}$ converges for all $v$.

Since each term of $f_{n}(z)$ converges to a limit, $f_{n}(z)$ also converges to a limit for $z<R$. If we repeat the argument with another disc centred at any limit point (e.g. $z_{0}$), we can extend to any region bounded by $S$.

Schwarz's lemma

Lemma

If $f(z)$ is analytic and regular(?) for $|z|\leq R$, $|f(z)|\leq M$ for $|z|=R$ and $f(0)=0$, then

$f(re^{i\theta }\leq {\frac {Mr}{R}}\quad (0\leq r\leq R)$

Proof

$f(z)/z$ is regular for $|z|\leq R$ and $|f(z)/z|\leq M/R$ on the circle $|z|=R$. By the maximum modulus theorem(?) this inequality holds also inside the circle. Because $|f(z)/z|=|f(z)|/r$ we multiply both sides of the inequality by $r$ which gives us our lemma.

Example

The number $k$ of singleton cycles in a permutation of length $n$ is given by $P(z,u)={\frac {e^{z(u-1)}}{1-z}}$.

For each $u$ we have a singularity at $z=1$ of order 1. If we treat $u$ as a constant and apply our estimate for meromorphic functions

$p_{n}(u)=[z^{n}]P(z,u)\sim {\frac {(-1)e^{(u-1)}}{-1}}=e^{u-1}$ as $n\to \infty$.

Therefore,

$p_{n,k}\sim [u^{k}]e^{u-1}={\frac {1}{k!e}}$ as $n\to \infty$.

Continuous limit law

This applies when the mean and standard deviation of the random variable tend to infinity.

There are three cases/theorems:

• Meromorphic
• Singularity
• Saddle

Meromorphic schema

Theorem

Let $F(z,u)$ be bivariate analytic at $(z,u)=(0,0)$ with non-negative coefficients. Let $F(z,1)$ be meromorphic in $z\leq r$ with only a simple pole $\rho$ for positive $\rho <r$. Assume:

1. Meromorphic perturbation: there exists $\epsilon >0$ and $r>\rho$ such that in the domain $D=\{|z|\leq r\}\times \{|u-1|<\epsilon \}$:

   $F(z,u)={\frac {B(z,u)}{C(z,u)}}$

   where $B(z,u)$ and $C(z,u)$ are analytic in $D$ and $B(\rho ,1)\neq 0$ and $\rho$ is a simple zero of $C(z,1)$.

2. Non-degeneracy: $\partial _{z}C(\rho ,1)\partial _{u}C(\rho ,1)\neq 0$.
3. Variability: $v\left({\frac {\rho (1)}{\rho (u)}}\right)\neq 0$.

Then, the standardised random variable $X_{n}$ converges to the Gaussian variable, with speed of convergence $O(n^{-1/2})$ and mean and standard deviation asymptotically linear in $n$.

Proof

Construct annular region composed of two concentric circles $C_{s}$ and $C_{r}$ of radius $s$ ($\rho <s<r$) and $r$, respectively. By the global Cauchy formula and residue theorem, for $z$ in the annular region and $u$ in a small enough domain around 1,

$f_{n}(u)={\frac {1}{2\pi i}}\int _{C_{s}}{\frac {B(z,u)}{C(z,u)}}{\frac {dz}{z^{n+1}}}+{\frac {1}{2\pi i}}\int _{C_{r}}F(z,u){\frac {dz}{z^{n+1}}}=Res\left({\frac {B(z,u)}{C(z,u)z^{n+1}}};z=\rho (u)\right)+{\frac {1}{2\pi i}}\int _{C_{r}}F(z,u){\frac {dz}{z^{n+1}}}$

By Cauchy's inequality,

$\int _{C_{r}}F(z,u){\frac {dz}{z^{n+1}}}\leq {\frac {\max _{|z|=r,|u-1|\leq \epsilon }|F(z,u)|}{r^{n}}}={\frac {\sup _{|z|=r,|u-1|\leq \epsilon }|B(z,u)|}{\inf _{|z|=r,|u-1|\leq \epsilon }|C(z,u)|r^{n}}}={\frac {K}{r^{n}}}=O(r^{-n})$

where $K$ is a finite constant, due to the fact that $C(z,u)$ is non-zero on $|z|=r$ and $B(z,u)$ is analytic and therefore bounded...

$Res\left({\frac {B(z,u)}{C(z,u)z^{n+1}}};z=\rho (u)\right)={\frac {B(\rho (u),u)}{C_{z}^{'}(\rho (u),u)\rho (u)^{n+1}}}$

Therefore,

$f_{n}(u)={\frac {B(\rho (u),u)}{C_{z}^{'}(\rho (u),u)\rho (u)^{n+1}}}+O(r^{-n})$

meaning it meets the conditions of the Quasi-powers theorem.

Saddle-point

Theorem

Assume

$p_{n}(u)=e^{h_{n}(u)}(1+o(1))$

uniformly for $u$ in a fixed neighbourhood $\Omega$ of $1$ and each $h_{n}(u)$ analytic in $\Omega$. Assume also

$h_{n}'(1)+h_{n}''(1)\to \infty$

and

${\frac {h_{n}'''(u)}{(h_{n}'(1)+h_{n}''(1))^{3/2}}}\to 0$

uniformly for $u\in \Omega$. Then

$X_{n}^{*}={\frac {X_{n}-h_{n}'(1)}{(h_{n}'(1)+h_{n}''(1))^{1/2}}}$

converges in distribution to a Gaussian with mean 0 and variance 1.

Proof

Quasi-powers theorem

Theorem

Let the $X_{n}$ be non-negative discrete random variables and $p_{n}(u)$ be probability generating functions. Assume uniformly in a fixed complex neighbourhood of $u=1$ for $\beta _{n},\kappa _{n}\to +\infty$

$p_{n}(u)=A(u).B(u)^{\beta _{n}}\left(1+O\left({\frac {1}{\kappa _{n}}}\right)\right)$

where $A(u),B(u)$ are analytic at $u=1$ and $A(u)=B(u)=1$. Assume $B(u)$ satisfies the "variability condition"

$v(B(u))\equiv B''(1)+B'(1)-B'(1)^{2}\neq 0$

Then the mean and variance of $X_{n}$ satisfy

$\mu _{n}\equiv E(X_{n})=\beta _{n}m(B(u))+m(A(u))+O(\kappa _{n}^{-1})$

$\sigma _{n}^{2}\equiv V(X_{n})=\beta _{n}v(B(u))+v(A(u))+O(\kappa _{n}^{-1})$

and

$P\left({\frac {X_{n}-E(X_{n})}{\sqrt {V(X_{n})}}}\leq x\right)=\Phi (x)+O\left({\frac {1}{\kappa _{n}}}+{\frac {1}{\sqrt {\beta _{n}}}}\right)$

where

$\Phi (x)={\frac {1}{\sqrt {2\pi }}}\int _{-\infty }^{x}e^{-w^{2}/2}dw$.

Proof

Convert to a Laplace transform

$\lambda _{n}(s)=e^{\beta _{n}\log B(s)+\log A(s)}(1+O(\kappa _{n}^{-1}))$

therefore

$\log \lambda _{n}(s)=\beta _{n}\log B(s)+\log A(s)+O(\kappa _{n}^{-1})$

${\frac {d}{ds}}\log \lambda _{n}(s)=\beta _{n}{\frac {d}{ds}}\log B(s)+{\frac {d}{ds}}\log A(s)+O(\kappa _{n}^{-1})=\beta _{n}m(B(s))+m(A(s))+O(\kappa _{n}^{-1})$

${\frac {d^{2}}{ds^{2}}}\log \lambda _{n}(s)=\beta _{n}{\frac {d^{2}}{ds^{2}}}\log B(s)+{\frac {d^{2}}{ds^{2}}}\log A(s)+O(\kappa _{n}^{-1})=\beta _{n}v(B(s))+v(A(s))+O(\kappa _{n}^{-1})$

Continuity of integral transforms

Theorem from Flajolet and Sedgewick.

Fourier

Also known as Lévy's continuity theorem.

If $p_{n}(u)$ and $q(u)$ have Fourier transforms $\phi _{n}(t)$ and $\phi (t)$, respectively, and $q(u)$ has a continuous distribution function, then

$\lim _{n\to +\infty }p_{n}(u)=q(u)$

if and only if, pointwise for each real $t$

$\lim _{n\to +\infty }\phi _{n}(t)=\phi (t)$

Laplace

Assume $p_{n}(u)$ and $q(u)$ have Laplace transforms $\lambda _{n}(s)$ and $\lambda (s)$, respectively, defined on $s\in [-s_{0},s_{0}]$. If pointwise for each real $s\in [-s_{0},s_{0}]$

$\lim _{n\to +\infty }\lambda _{n}(u)=\lambda (u)$

then

$\lim _{n\to +\infty }p_{n}(u)=q(u)$

Appendix

Pointwise convergence

A sequence of functions $\{f_{n}(z)\}$ is said to converge pointwise to $f(z)$ on a set $S$ if for each point $z\in S$ and $\epsilon >0$ there exists a number $N$ such that

$|f_{n}(z)-f(z)|<\epsilon$ for $n>N$

Compared to uniform convergence, $N$ is dependent on both $z$ and $\epsilon$. In other words, as the $z$ changes the $N$ may have to change as well.

Uniform convergence

A sequence of functions $\{f_{n}(z)\}$ is said to converge uniformly to $f(z)$ on a set $S$ if for any $\epsilon >0$ there exists a number $N$ such that

$|f_{n}(z)-f(z)|<\epsilon$ for $n>N$ and for all $z\in S$

Compared to pointwise convergence, $N$ depends only on $\epsilon$. In other words, the same $N$ holds for all $z$.

References

• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
• Titchmarsh, E. C. (1939). The Theory of Functions (2nd ed.). Oxford University Press.