Analytic Combinatorics/Tauberian Theorem

Introduction

'Tauberian' refers to a class of theorems with many applications. The full scope of Tauberian theorems is too large to cover here.

We prove here only a particular Tauberian theorem due originally to Hardy, Littlewood and Karamata, which is useful in analytic combinatorics.

Theorem

Theorem from Feller.

If

$f(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n\sim \frac{1}{(1-x{)}^{\rho }}L\left(\frac{1}{1-x}\right)(x\to 1^{-})$

where the sequence $\{a_n\}$ is monotone (always non-decreasing or always non-increasing), $0<\rho <\mathrm{\infty }$ and $\underset{x\to \mathrm{\infty }}{\lim }\frac{L(cx)}{L(x)}=1$ then

$a_n\sim \frac{n^{\rho -1}}{\mathrm{\Gamma }(\rho )}L(n)(n\to \mathrm{\infty })$

Proof

Proof from Feller.

• We express our theorem in terms of a measure $U$ with a density function $u(x)=a_n(n\le x<n+1)$ such that $U(n)=\underset{0}{\overset{n}{\int }}u(x)dx=\sum _{i=0}^{n-1}{a}_i$.
• The Laplace transform of $U$ is $\omega (\lambda )=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-\lambda x}u(x)dx=\sum _{n=0}^{\mathrm{\infty }}\underset{n}{\overset{n+1}{\int }}u(x)e^{-\lambda x}dx=\sum _{n=0}^{\mathrm{\infty }}{a}_n\underset{n}{\overset{n+1}{\int }}{e}^{-\lambda x}dx=\sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{1}{\lambda }(e^{-n\lambda }-e^{-(n+1)\lambda })=\frac{1-e^{-\lambda }}{\lambda }\sum _{n=0}^{\mathrm{\infty }}{a}_n{e}^{-n\lambda }$
• By the power series expansion of $e$, as $\lambda \to 0$, $\frac{1-e^{-\lambda }}{\lambda }=\frac{\lambda +o(\lambda )}{\lambda }\sim 1$.
• Therefore, $\omega (\lambda )\sim f(e^{-\lambda })\sim \frac{1}{(1-e^{-\lambda }{)}^{\rho }}L\left(\frac{1}{1-e^{-\lambda }}\right)\sim \frac{1}{{\lambda }^{\rho }}L\left(\frac{1}{\lambda }\right)$ as $\lambda \to 0$.
• $\frac{\omega (\frac{\lambda }{x})}{\omega (\frac{1}{x})}\sim \frac{1}{{\lambda }^{\rho }}\frac{L(\frac{x}{\lambda })}{L(x)}\sim \frac{1}{{\lambda }^{\rho }}$ as $x\to \mathrm{\infty }$.
• $\frac{1}{{\lambda }^{\rho }}$ is the Laplace transform of $\frac{y^{\rho -1}}{\mathrm{\Gamma }(\rho )}$. To express this in terms of the measure $\frac{U(xy)}{\omega (\frac{1}{x})}$, we integrate the latter to get $\frac{y^{\rho }}{\rho \mathrm{\Gamma }(\rho )}=\frac{y^{\rho }}{\mathrm{\Gamma }(\rho +1)}$.
• We use the continuity theorem to show that this implies $\frac{U(xy)}{\omega (\frac{1}{x})}\sim \frac{y^{\rho }}{\mathrm{\Gamma }(\rho +1)}$, or (setting $y=1$) $U(x)\sim \frac{\omega (\frac{1}{x})}{\mathrm{\Gamma }(\rho +1)}\sim \frac{x^{\rho }}{\mathrm{\Gamma }(\rho +1)}L(x)$.
• We prove that this implies $u(x)\sim \frac{\rho U(x)}{x}$.
• Therefore, $a_n=u(n)\sim \frac{\rho U(n)}{n}\sim \frac{n^{\rho -1}}{\mathrm{\Gamma }(\rho )}L(n)$.

Measure and probability distributions

A measure $U$ assigns a positive number to a set. It is a generalisation of concepts such as length, area or volume.

Graph of u(x) shown as a step-function in blue. There are two examples of the measure U: U(1.5) is the area under the curve in orange, U{[2.4, 2.6]} is the area under the curve in green.

In our case, our measure is the area under the curve of the step function that takes the values of our coefficients, $u(x)=a_n(n\le x<n+1)$. Therefore, $U(x)=\underset{0}{\overset{x}{\int }}u(y)dy$. If $n$ is an integer, $U(n)=\sum _{i=0}^{n-1}{a}_i$. We define $U\{I\}$ to be the area under the curve confined to the interval $I$. If the interval $I$ is contained in the interval $(n,n+1)$ for some $n$ and $l$ is the length of $I$, then $U\{I\}=u(n)l$.

A measure can be converted to a probability distribution $F(x)=\frac{U(x)}{U(+\mathrm{\infty })}$ with density $f(x)=u(x)$, assigning a probability to how likely a random variable will take on a value less than or equal to $x$. We do this because probability distributions have two properties which we make use of in our proof.

We define $F\{A\}$ to be the probability that a random variable will take on a value in the set $A$.

Property 1: Expectation or mean

The expectation or mean of a probability distribution $F$ with density $f$ is calculated as $E(X)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}xf(x)dx$.

We also define $E(u)=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}u(x)f(x)dx$.

Theorem 1

Let $\{F_n\}$ be a sequence of probability distributions with expectations $E_n$, if $F_n\to F$ then $E_n(u)\to E(u)$ for $u\in C_0(-\mathrm{\infty },\mathrm{\infty })$.

Proof

Assume $F_n\to F$. Let $u$ be a continuous function such that $|u(x)|<M$ for all $x$. Let A be an interval such that $F\{A\}>1-ϵ$, and therefore, for the complement $A^{\prime }$, $F\{A^{\prime }\}<2ϵ$ for $n$ sufficiently large.

Because $u$ is continuous it is possible to partition $A$ into intervals $I_1,I_2,\cdots$ so small that $u$ oscillates by less than $ϵ$.

We can then estimate $u$ in $A$ by a step function $\sigma$ which assumes constant values within each $I_k$ and such that $|u(x)-\sigma (x)|<ϵ$ for all $x\in A$. We define $\sigma (x)=0$ for $x\in A^{\prime }$, so that $|u(x)-\sigma (x)|<M$ for $x\in A^{\prime }$.

Therefore, $|E(u)-E(\sigma )|\le ϵF\{A\}+MF\{A^{\prime }\}\le ϵ+Mϵ$.

For sufficiently large $n$, $|E_n(u)-E_n(\sigma )|\le ϵF_n\{A\}+M{F}_n\{A^{\prime }\}\le ϵ+Mϵ$

Because $E_n(\sigma )\to E(\sigma )$ then for sufficiently large $n$, $|E(\sigma )-E_n(\sigma )|<ϵ$.

Putting it all together,

$|E(u)-E_n(u)|\le |E(u)-E(\sigma )|+|E(\sigma )-E_n(\sigma )|+|E_n(\sigma )-E_n(u)|<3(M+1)ϵ$

which implies $E_n(u)\to E(u)$.

Property 2: Convergence

Lemma 1

Let $a_1,a_2,\cdots$ be an arbitrary sequence of points. Every sequence of numerical functions contains a subsequence that converges for all $a_i$.

Row 4, $u_n^4$, (in blue) is contained in the previous 3 rows, contains all the subsequent rows and converges at $a_4$. All $u_4^4,u_5^5,\cdots$ (in green) are contained in $u_n^4$ and therefore converge for $a_4$. This argument can be repeated for all $a_k$.

$u_1^1$	$u_2^1$	$u_3^1$	$u_4^1$	$u_5^1$	$\cdots$
$u_1^2$	$u_2^2$	$u_3^2$	$u_4^2$	$u_5^2$	$\cdots$
$u_1^3$	$u_2^3$	$u_3^3$	$u_4^3$	$u_5^3$	$\cdots$
$u_1^4$	$u_2^4$	$u_3^4$	$u_4^4$	$u_5^4$	$\cdots$
$u_1^5$	$u_2^5$	$u_3^5$	$u_4^5$	$u_5^5$	$\cdots$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$\ddots$

Proof

For a sequence of functions $\{u_n\}$ we can find a subsequence $u_1^1,u_2^1,\cdots$ that converges at $a_1$. Out of the subsequence $u_1^1,u_2^1,\cdots$ we find a subsequence $u_1^2,u_2^2,\cdots$ that converges at $a_2$. Continue in this way to find sequences $\{u_n^k\}$ that converge for the point $a_k$, but not necessarily any of the previous points.

Construct a diagonal sequence $u_1^1,u_2^2,u_3^3,\cdots$. This sequence converges for all $a_k$ because all but the first $k-1$ terms are contained in $\{u_n^k\}$. This is true for all $k$.

Theorem 2

Every sequence $\{F_n\}$ of probability distributions possesses a subsequence $F_{n_1},F_{n_2},\cdots$ that converges to a probability distribution $F$.

Proof

By lemma 1, we can find a subsequence $\{F_{n_k}\}$ that converges for all points $a_i$of a dense sequence. Denote the limit the sequence converges for each $a_i$ by $G(a_i)$. For $x$ that are not one of $a_i$, $G(x)$ is the greatest lower bound of all $G(a_i)$ for $a_i>x$.

$G$ is increasing between 0 and 1. If we define $F$ to be equal to $G$ at all points of continuity and $F(x)=G(x+)$ if $x$ is a point of discontinuity. For a point of continuity $x$, we can find two points such that $a_i<x<a_j$, $G(a_j)-G(a_i)<ϵ$ and $G(a_i)\le F(x)\le G(a_j)$.

$F_n$ are monotone, therefore $F_{n_k}(a_i)\le F_{n_k}(x)\le F_{n_k}(a_j)$. The limit of $\{F_{n_k}\}$ differs from $F(x)$ by no more than $ϵ$, so $F_{n_k}\to F(x)$ as $k\to \mathrm{\infty }$ for all points of continuity.

Theorem 3

If $F_n\to F$ then the limit of every subsequence equals $F$.

Proof

By the definition of limits, $|F_n-F|<ϵ$ for $n>N$. Therefore, for any subsequence $\{F_{n_k}\}$, $|F_{n_k}-F|<ϵ$ when $n_k\ge n>N$.

Laplace transform

The Laplace Transform can be seen as the continuous analogue of the power series, where $\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ becomes $\underset{0}{\overset{\mathrm{\infty }}{\int }}a(x)e^{-\lambda x}dx$. $x^n$ is replaced by $e^{-\lambda x}$ because it is easier to integrate.

We define the Laplace transform of a probability distribution $F$ as $\varphi (\lambda )=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-\lambda x}F\{dx\}$.

If $F$ has the density $f$ then we can also define the Laplace tranform of $F$ as $\varphi (\lambda )=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-\lambda x}f(x)dx$.

If our density $f$ is zero for $x<0$, we can also see that the Laplace transform is equivalent to the expectation $E(e^{-\lambda X})=\underset{0}{\overset{\mathrm{\infty }}{\int }}{e}^{-\lambda x}f(x)dx$.

Theorem 4

Distinct probability distributions have distinct Laplace transforms.

Continuity theorem

Theorem 5

Let $\{F_n\}$ be a sequence of probability distributions with Laplace transforms ${\varphi }_n$, then ${\varphi }_n\to \varphi$ implies $F_n\to F$.

Proof

Because the Laplace transforms ${\varphi }_n,\varphi$ are equivalent to expectations, we can use theorem 1 with $u(x)=e^{-\lambda x}$ to prove that $F_n\to F$ implies ${\varphi }_n\to \varphi$.

By theorem 2, if $\{F_{n_k}\}$ is a subsequence that converges to $F^{\prime }$, then the Laplace transforms of $F_{n_k}$ converge to the Laplace transform ${\varphi }^{\prime }$ of $F^{\prime }$.

By assumption in the theorem, the Laplace transforms ${\varphi }_n$ converge to $\varphi$, then by theorem 3 all its subsequences also converge to $\varphi$ so that $\varphi ={\varphi }^{\prime }$.

Because Laplace transforms are unique, $F^{\prime }=F$. But this will be true for every subsequence so by theorem 3 $F_n\to F$.

This proof can be extended more generally to measure by defining our probability distribution in terms of the measure $U_n$, $F_n=\frac{1}{{\varphi }_n(\lambda )}{e}^{-\lambda x}{U}_n\{dx\}$.

Asymptotics of the density function

Theorem 6

If $U$ has a monotone density $u$ and $\rho >0$ then $u(x)\sim \frac{\rho U(x)}{x}$ as $x\to \mathrm{\infty }$.

Proof

For $0<a<b$,

$\underset{a}{\overset{b}{\int }}\frac{u(ty)t}{U(t)}dy=\frac{U(tb)-U(ta)}{U(t)}$.

As $t\to \mathrm{\infty }$ the right side tends to $b^{\rho }-a^{\rho }$. By theorem 2, there exists a sequence $\{t_k\}\to \mathrm{\infty }$ such that

$\frac{u(ty)t}{U(t)}\to \psi (y)$

Therefore

$\underset{a}{\overset{b}{\int }}\psi (x)dx=b^{\rho }-a^{\rho }$

which implies $\psi (y)=\rho y^{\rho -1}$. This limit is independent of the chosen sequence $\{t_k\}$ therefore is true for any sequence. For $y=1$

$u(x)\sim \frac{\psi (x)U(x)}{x}=\frac{\rho U(x)}{x}$ as $x\to \mathrm{\infty }$.

Dense

A subset $A$ of a set $X$ is called dense if the closure of $A$ is equivalent to $X$, i.e. $\bar{A}=X$. This means that if $x\in X$ then $x$ is either in the subset $A$ or is on the boundary of that subset. If it is on the boundary then we can select elements of $A$ which are arbitrarily close to $x$.

References

• Template:Cite book
• Template:Cite book
• Template:Cite book