User:Dom walden/Bivariate Generating Functions

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction

[edit | edit source]

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

[edit | edit source]

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

Theorem

[edit | edit source]

If is a subset of the unit disc with at least one point of accumulation in the interior of the disc. If , and pointwise for each

then

and [1]

Proof

[edit | edit source]

Applying Vitali's theorem, we take the sequence to be and to be the unit disc. All are analytic and bounded on (due to ). The theorem assumes that converges to in which has an accumulation point in .

Vitali's theorem states uniformly converges to on any compact subset of , which we will take as the disc and use Cauchy's coefficient formula:

[2]

Vitali's theorem

[edit | edit source]

Theorem

Let be a sequence of functions, all analytic on an open connected set and for all and in .

If the sequence converges on a subset of with a point of accumulation in , then converges uniformly on every compact subset of .[3]

Proof

Let

We want to prove that each converges to a limit.

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

Let be a point where the sequence converges. Then

because, by Schwarz's lemma, and .

We choose such that the first term is arbitrarily small and large enough that the second term is arbitrarily small. Therefore, converges to a limit.

Next, we define

For . converges to a limit at as both and converge to a limit. We repeat the argument above, which proved that converges to a limit, to prove that also converges to a limit. We keep repeating this to prove that converges for all .

Since each term of converges to a limit, also converges to a limit for . If we repeat the argument with another disc centred at any limit point (e.g. ), we can extend to any region bounded by .[4]

Schwarz's lemma

[edit | edit source]

Lemma

If is analytic and regular(?) for , for and , then

[5]

Proof

is regular for and on the circle . By the maximum modulus theorem(?) this inequality holds also inside the circle. Because we multiply both sides of the inequality by which gives us our lemma.[6]

Example

[edit | edit source]

The number of singleton cycles in a permutation of length is given by .

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

as .

Therefore,

as .[7]

Continuous limit law

[edit | edit source]

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

[edit | edit source]

Theorem

Let be bivariate analytic at with non-negative coefficients. Let be meromorphic in with only a simple pole for positive . Assume:

  1. Meromorphic perturbation: there exists and such that in the domain :
    where and are analytic in and and is a simple zero of .
  2. Non-degeneracy: .
  3. Variability: .

Then, the standardised random variable converges to the Gaussian variable, with speed of convergence and mean and standard deviation asymptotically linear in .[8]

Proof

Construct annular region composed of two concentric circles and of radius () and , respectively. By the global Cauchy formula[9] and residue theorem, for in the annular region and in a small enough domain around 1,

By Cauchy's inequality,

where is a finite constant, due to the fact that is non-zero on and is analytic and therefore bounded...

Therefore,

meaning it meets the conditions of the Quasi-powers theorem.[10]

Singularity

[edit | edit source]

Saddle-point

[edit | edit source]

Theorem

Assume

uniformly for in a fixed neighbourhood of and each analytic in . Assume also

and

uniformly for . Then

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

Proof

Quasi-powers theorem

[edit | edit source]

Theorem

Let the be non-negative discrete random variables and be probability generating functions. Assume uniformly in a fixed complex neighbourhood of for

where are analytic at and . Assume satisfies the "variability condition"

Then the mean and variance of satisfy

and

where

.[12]

Proof

Convert to a Laplace transform

therefore

[13]

Continuity of integral transforms

[edit | edit source]

Theorem from Flajolet and Sedgewick[14].

Fourier

Also known as Lévy's continuity theorem.

If and have Fourier transforms and , respectively, and has a continuous distribution function, then

if and only if, pointwise for each real

Laplace

Assume and have Laplace transforms and , respectively, defined on . If pointwise for each real

then

Appendix

[edit | edit source]

Pointwise convergence

[edit | edit source]

A sequence of functions is said to converge pointwise to on a set if for each point and there exists a number such that

for

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

Uniform convergence

[edit | edit source]

A sequence of functions is said to converge uniformly to on a set if for any there exists a number such that

for and for all

Compared to pointwise convergence, depends only on . In other words, the same holds for all .

Fourier transform

[edit | edit source]

Laplace transform

[edit | edit source]

Notes

[edit | edit source]
  1. Flajolet and Sedgewick 2009, pp. 624.
  2. Flajolet and Sedgewick 2009, pp. 624.
  3. Flajolet and Sedgewick 2009, pp. 624. Titchmarsh 1939, pp. 168-169.
  4. Titchmarsh 1939, pp. 168-169.
  5. Titchmarsh 1939, pp. 168.
  6. Titchmarsh 1939, pp. 168.
  7. Flajolet and Sedgewick 2009, pp. 625-626.
  8. Flajolet and Sedgewick 2009, pp. 656.
  9. Lang 1999, pp. 145.
  10. Flajolet and Sedgewick 2009, pp. 656-657.
  11. Flajolet and Sedgewick 2009, pp. 690.
  12. Flajolet and Sedgewick 2009, pp. 645-646.
  13. Flajolet and Sedgewick 2009, pp. 646-647.
  14. Flajolet and Sedgewick 2009, pp. 639-640.

References

[edit | edit source]
  • 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.