Generating Functions and Trees and PI

From: Osher Doctorow (mdoctorow_at_comcast.net)
Date: 11/15/04 

Date: Mon, 15 Nov 2004 02:27:10 +0000 (UTC)

 From Osher Doctorow mdoctorow@comcast.net

COPYRIGHT NOTICE
Generating Functions and Trees and PI
Copyright By Owner Osher Doctorow Ph.D.
First Published 2004.

As I mentioned in a recent thread related to generating functions,
Cyril Banderier, Philippe Flajolet, Mireille Bousquet-Melou, Alain
Denise, Daniele Gardy, and Dominque Gouyou-Beauchamps in "Generating
functions for generating trees," arXiv:math.CO/0411250 v1 11 Nov
2004 (authors respectively from INRIA, INRIA, U. Bordeaux,U.Paris,
U. de Versailles, U. Paris) have written a fascinating paper which,
although the authors have no knowledge of Probable Influence (PI),
has many ties to PI theoretically and empirically.

I remind readers of the generating function for Fibonacci numbers,
namely:

1) g(x) = sum Fn x^n (sum for n = 1 to infinity) = x/(1 - x - x^2) =
x + x^2 + 2x^3 + 3x^4 + 5x^5...

where the coefficients of the last expression are 1, 2, 2, 3, 5, ...,
that is to say the Fibonacci numbers. Banderier et al in fact
explore the Fibonacci numbers and bisection of the Fibonacci
sequence in their paper, these two numbers/sequences being examples
of rational systems as opposed to algebraic systems (factorial form
systems) and opposed to transcendental (exponential form systems).

Rational systems have rational generating functions, algebraic
systems have algebraic generating functions, transcendental systems
have transcendental (typically exponential) generating functions
and the coefficients either grow too fast and so have radius of
convergence 0 or are too irregular to belong to the other classes
and include the topic of holonomy.

If only finitely many labels occur in the tree, then the generating
function is rational, while Laurent polynomials for example give
algebraic systems of generating functions and typically have
infinite sum form with or without poles/singularities such as square
roots (with finitely many singularities that are algebraic numbers),
and transcendental systems have either explicitly transcendental
elements like logarithms or exponentials or involve infinitely many
singularities.

Holonomic or D-finite series satisfy linear differential equations
with polynomial coefficients in a complex variable or a linear
recurrence relation with polynomial coefficients. Sum fn u^n is
holonomic iff sum fn u^n/n! is holonomic. Holonomic systems can be
algebraic or transcendental.

Turning to PI generalized probability generating functions (pgfs),
consider:

2) 1 + Dx(FX(x)) + Dxy(F(x,y)) + ...

Is this more closely related to rational, algebraic, or transcenden-
tal expressions or generating functions (generalized)? It depends
on whether the various cdfs like FX, F(x,y), etc. are which type of
the three types polynomial, algebraic, or trigonometric.

Notice that Dx(FX(x)) = fX(x) (the marginal pdf of X for continuous
random variable X), Dxy(F(x,y)) = f(x,y) (the bivariate pdf of X
and Y both continuous), etc. Thus, the PI generalized pgf generates
pdfs from cdfs, and its "0th degree" expression consists of cdfs,
and the latter includes the median implicitly since P(X < = x_m) =
1/2 for x_m the median. The only thing not generated in this way
is the non-median non-order-statistic moments, at least as far as
I know now, which is not surprising from my previous discussions of
the median and mean and variance, etc.

Osher Doctorow