Analytic Combinatorics/Tauberian Theorem

Introduction

edit

'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

edit

Theorem from Feller.[1]

If

 

where the sequence   is monotone (always non-decreasing or always non-increasing),   and   then

 

Proof

edit

Proof from Feller.[2]

  • We express our theorem in terms of a measure   with a density function   such that  .
  • The Laplace transform of   is  [3]
  • By the power series expansion of  , as  ,  .
  • Therefore,   as  .
  •   as  .[4]
  •   is the Laplace transform of  . To express this in terms of the measure  , we integrate the latter to get  .
  • We use the continuity theorem to show that this implies  , or (setting  )  .
  • We prove that this implies  .
  • Therefore,  .

Measure and probability distributions

edit

A measure   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,  . Therefore,  . If   is an integer,  . We define   to be the area under the curve confined to the interval  . If the interval   is contained in the interval   for some   and   is the length of  , then  .

A measure can be converted to a probability distribution   with density  , assigning a probability to how likely a random variable will take on a value less than or equal to  . We do this because probability distributions have two properties which we make use of in our proof.

We define   to be the probability that a random variable will take on a value in the set  .

Property 1: Expectation or mean

edit

The expectation or mean of a probability distribution   with density   is calculated as  .

We also define  .

Theorem 1
Let   be a sequence of probability distributions with expectations  , if   then   for  .[5]
Proof
Assume  . Let   be a continuous function such that   for all  . Let A be an interval such that  , and therefore, for the complement  ,   for   sufficiently large.
Because   is continuous it is possible to partition   into intervals   so small that   oscillates by less than  .
We can then estimate   in   by a step function   which assumes constant values within each   and such that   for all  . We define   for  , so that   for  .
Therefore,  .
For sufficiently large  ,  
Because   then for sufficiently large  ,  .
Putting it all together,
 
which implies  .[6]

Property 2: Convergence

edit
Lemma 1
Let   be an arbitrary sequence of points. Every sequence of numerical functions contains a subsequence that converges for all  .[7]
Row 4,  , (in blue) is contained in the previous 3 rows, contains all the subsequent rows and converges at  . All   (in green) are contained in   and therefore converge for  . This argument can be repeated for all  .
           
           
           
           
           
           
Proof
For a sequence of functions   we can find a subsequence   that converges at  . Out of the subsequence   we find a subsequence   that converges at  . Continue in this way to find sequences   that converge for the point  , but not necessarily any of the previous points.
Construct a diagonal sequence  . This sequence converges for all   because all but the first   terms are contained in  . This is true for all  .[8]
Theorem 2
Every sequence   of probability distributions possesses a subsequence   that converges to a probability distribution  .[9]
Proof
By lemma 1, we can find a subsequence   that converges for all points  of a dense sequence. Denote the limit the sequence converges for each   by  . For   that are not one of  ,   is the greatest lower bound of all   for  .
  is increasing between 0 and 1. If we define   to be equal to   at all points of continuity and   if   is a point of discontinuity. For a point of continuity  , we can find two points such that  ,   and  .
  are monotone, therefore  . The limit of   differs from   by no more than  , so   as   for all points of continuity.[10]
Theorem 3
If   then the limit of every subsequence equals  .[11]
Proof
By the definition of limits,   for  . Therefore, for any subsequence  ,   when  .[12]

Laplace transform

edit

The Laplace Transform can be seen as the continuous analogue of the power series, where   becomes  .   is replaced by   because it is easier to integrate.

We define the Laplace transform of a probability distribution   as  .

If   has the density   then we can also define the Laplace tranform of   as  .[13]

If our density   is zero for  , we can also see that the Laplace transform is equivalent to the expectation  .[14]

Theorem 4
Distinct probability distributions have distinct Laplace transforms.[15]

Continuity theorem

edit
Theorem 5
Let   be a sequence of probability distributions with Laplace transforms  , then   implies  .[16]
Proof
Because the Laplace transforms   are equivalent to expectations, we can use theorem 1 with   to prove that   implies  .
By theorem 2, if   is a subsequence that converges to  , then the Laplace transforms of   converge to the Laplace transform   of  .
By assumption in the theorem, the Laplace transforms   converge to  , then by theorem 3 all its subsequences also converge to   so that  .
Because Laplace transforms are unique,  . But this will be true for every subsequence so by theorem 3  .[17]

This proof can be extended more generally to measure by defining our probability distribution in terms of the measure  ,  .[18]

Asymptotics of the density function

edit
Theorem 6
If   has a monotone density   and   then   as  .[19]
Proof
For  ,
 .
As   the right side tends to  . By theorem 2, there exists a sequence   such that
 
Therefore
 
which implies  . This limit is independent of the chosen sequence   therefore is true for any sequence. For  
  as  .[20]

Dense

edit

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

Notes

edit
  1. Feller 1971, pp. 447.
  2. Feller 1971, pp. 445-447.
  3. Evertse 2024, pp. 152.
  4. Mimica 2015, pp. 19.
  5. Feller 1971, pp. 249.
  6. Feller 1971, pp. 249-250.
  7. Feller 1971, pp. 267.
  8. Feller 1971, pp. 267.
  9. Feller 1971, pp. 267.
  10. Feller 1971, pp. 267-268.
  11. Feller 1971, pp. 267.
  12. Feller 1971, pp. 267-268.
  13. Feller 1971, pp. 431-432.
  14. Feller 1971, pp. 430.
  15. Feller 1971, pp. 430.
  16. Feller 1971, pp. 431.
  17. Feller 1971, pp. 431.
  18. Feller 1971, pp. 433.
  19. Feller 1971, pp. 446.
  20. Feller 1971, pp. 446.

References

edit
  • Evertse, Jan-Hendrik (2024). Analytic Number Theory (Mastermath) Part I: Prime Number Theory. Chapter 5: Tauberian theorems (PDF).
  • Feller, William (1971). An Introduction to Probability Theory and Its Applications. Volume II (2nd ed.). John Wiley & Sons.
  • Mimica, Ante (2015). Laplace Transform (PDF).