Distribution of Image Points in Random Mappings

Michèle Soria

Université Paris VI

Algorithms Seminar

November 10, 1996

[summary by Pierre Nicodème]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
This talk presents a general theorem which can be used to identify the limiting distribution for a class of combinatorial schemata. For example, many parameters in random mappings can be covered in this way.

1   Methods

We consider the general working scheme ``Symbolic Structures A or { A,w} ® Generating Functions a(z) or a(u,z) ® an or an,k''. Then by Cauchy's formula, we get for structures A
a(z) =
 
å
a Î A
z
|a|
 
|a|!
=
 
å
n³ 0
an
zn
n!
Þ
an
n!
=
1
2ip
ó
õ a(z)
dz
zn+1
.
When considering marked structures with parameters { A,w}, (w is a mapping A ® N), we have
a(u,z)=
 
å
aÎ A
u
w(a)
 
z
|a|
 
|a|!
=
 
å
n,k
an,kuk
zn
n!
.
In this case, an,k can be obtained by double Cauchy inversion, or by Cauchy inversion and Continuity Theorem. Table 1 gives some examples of translation of marked combinatorial structures to generating functions. The mark is represented by character ``·'' and translated to parameter u.
Description Structure Generating Function
Degree at the root in Cayley trees A = Node ×Set(· A) a(u,z) = z exp(ua(z))
Random Mappings G = Set(Cycle( A)) g(z)=1/1-a(z)
--- by number of cycles G = Set(·Cycle( A)) g(u,z)= exp(ulog1/1-a(z))
--- by number of trees G = Set(Cycle(· A)) g(u,z) = 1/1-u a(z)

Table 1: Some examples of generating functions

By a classical theorem about characteristic functions (Xn) converges weakly to Y if and only if fXn(q) converges to fY(q) for all q, with fZ = E(eiq Z). We also have a(u,z)=ån,kuk zn/n! = ån pn(u)zn/n!, which gives the probability generating function of Xn as pn(u)/pn(1) = ån Pr(Xn =k)uk. We refer to [2] for the concept of (labelled) combinatorial structures and their translation to generating functions.

2   Trees and Random Mappings

A random mapping is an arbitrary mapping f: {1,...,n}®{1,...,n} such that every mapping has probability n-n. A mapping f can be identified to its functional graph Gf with vertices {1,...,n} and edges (i,f(i)), for 1³ i ³ n. Each component of Gf consists of a cycle and every cyclic point is the root of a tree.

The basic property for analysis is that solutions of functional equations usually have algebraic singularity of square-root type. For trees, we get a(u,z) = t(u,z) -h(u,z)(1-z/r(u))1/2. For sequences of trees, we get an expression of the form 1/(1-a(u,z)), and for random mappings an expression of the form
s(u,z) =
1
1-T(u,z)+h(u,z)(1-z/r(u))1/2
.
We recall that when we get an expression of the form 1/(1-uC(z)), the asymptotic distribution of the corresponding random variable depends on the value C(rc), where rc is the only singularity on the circle of convergence of C(z). If C(rc)>1, the limit law is normal; if C(rc)<1, the limit law is derivative of geometric, and if C(rc)=1 the limit law is Rayleigh.

3   Examples

Leaves.
For Cayley trees, we have a(u,z) = z ea(u,z) + z(u-1), for sequences of trees, s(u,z)=1/(1-a(u,z)), and for functional graphs
g(u,z) =
1
1-zea(u,z)
=
1
1-a(u,z)+z(u-1)
.

Nodes of arity r.
For trees,
a(u,z) = z æ
ç
ç
è
 
å
m¹ r
am(u,z)
m!
+ u
ar(u,z)
r!
ö
÷
÷
ø		 = z ea(u,z)+z(u-1)
ar(u,z)
r!
.
For sequences of trees, we have s(u,z)=1/(1-a(u,z)), and for functional graphs,
g(u,z) =
1
1-a(u,z)+z(u-1) æ
ç
ç
è
ar-1
(r-1)!
-
ar
r!
ö
÷
÷
ø
.

Nodes at distance d from a cycle.
We have the recurrence
a0(u,z)=ua(z),     ad+1(u,z)=ze
ad(u,z)
 
.
For functional graphs, this gives g(u,z) =1/(1-ad(u,z)).

Nodes with r pre-images in total.
For trees, we have a(u,z) = zea(u,z)+(u-1)ar+1zr+1, where ar+1 = (r+1)r is the number of trees of size r+1. For functional graphs, we have G=Set(Cycle( A)), which translates to g(z) = exp(åp³ 0ap(z)/p). This gives
g(u,z) =
1
1-zea(u,z)
exp æ
ç
ç
è
zr
r
 
å
p
(up-1)
rr-p
(r-p)!
ö
÷
÷
ø		 =
K(u,z)
1-a(u,z)+(u-1)ar+1zr+1
.

Nodes d iterated.
(These nodes are at distance ³ d from a leaf.) For trees, we have
ad(u,z)=xue
ad(u,z)
 
-(u-1)ld(z)     with    l0(z)=0,   ld+1(z)=ze
ld(z)
 
.
For functional graphs, we have, for nodes at distance ³ d of a leaf of their sub-tree, sd(u,z) = 1/(1-ad(u,z)). For nodes at distance ³ d of a leaf, we have
gd(u,z) =
1
1-uze
ad(u,z)
 
=
1
1-ad(u,z)-(u-1)ld(z)
.

4   A classification for limit laws of random mappings parameters

We begin with a proposition which applies to functional equations of trees.

Proposition 1   Let F(u,z,a(u,z)) be a power series in three variables with non-negative coefficients and F(0,0,0) = 0. Suppose that the system of equations {t=F(1,r,t), 1=F'a(1,r,t)} has positive solutions r and t such that F'z(1,r,t)¹ 0 and F''aa(1,r,t)¹ 0. Then, F(u,z,a)=0 has for solution
a(u,z) = t(u,z)-h(u,z)(1-z/r(u))1/2,
with t,h,r analytic,
t(1,r(1))=t(1)º t,   r(1)=r    and   h(1,r(1))=(
2r F'z(1,r,t)
F''aa(1,r,t)
)1/2.
We arrive to a general theorem which seems to be the proper theorem to discuss random mappings. We consider a generating function g(u,z)=ån,kgn,kuk zn corresponding for variables Xn to a probability distribution Pr(Xn=k)=gn,k/gn. We consider a local expansion in the neighbourhood of u=1,z=r(u), of the form
g(u,z)=
1
1-T(u,z)+h(u,z)(1-z/r(u))1/2
.
T, h and r are analytic and T(1,r)=1.
Theorem 1   With these hypotheses (T, h, r analytic and T(1,r)=1),
  1. If r'(u) = 0 and T'u(1,r)>0, then Xn/(n)1/2® R(l), where l=1/2(h(r,1)/T'u(r,1))2 and R(l) is the Rayleigh distribution of density l x exp(-l/2x2). Moreover E(Xn)»(p n/2l)1/2 and Var(Xn) » (2-p/2)n/l.
  2. If r'(1)¹ 0 and T'u(1,r)=0, then Xn-µ n/(s2 n)1/2 ® N(0,1), where µ = -r'(1)/r(1) and s2=µ2+µ-r''(1)/r(1). Moreover E(Xn)» µ n and Var(Xn)» s2 n.
  3. If r'(1) ¹ 0 and T'u(1,r)¹ 0, then Xn - µ n/(s2 n)1/2® N(0,1)* R(s2l), where µ and s are defined as in (2), l is defined as in (1) and the star operator represents the convolution operation.
Remark 1   If T(1,r) ¹ 1, then Xn-µn/(s2 n)1/2® N(0,1), (except if r'(u) = 0 and T(1,r)<1, in which case Xn ® d G, derivative of a geometric law).
The density and characteristic functions in these different cases are as follows.
  1. R (Rayleigh) f R(l)(x)=l xe-l x2/2, and f R(q)= 1+iq(p/2)1/2e-q2/2(1-ierf(q/(2)1/2)).
  2. N (Normal) f N(x)=1/(2p)1/2e-x2/2 and f N(q)=e-q2/2.
  3. N* R (Normal conv. Rayleigh) f N* R(x)=(e-x2/4-e-x2/2)/(2p)1/2+xe-x2/4/2(2)1/2erf(x/2) and f N* R(q)= f N(q)× f R(q).
Proof.(Sketch) Let g(u,z) = ån³ 0pn(u)zn/n! with pn(1)=gn. The proof rests on the convergence of the corresponding characteristic functions to (1) f R(q), (2) e-q2/2, (3) e-q2/2× f R(q). For instance, in case (1), the characteristic function pn(eiq/(n)1/2)/gn converges to f R(q). The proofs in the different cases make use of Cauchy inversions along suitable contours of the complex plane [1].


5   Applications

We note Xn the law of Xn-µ n/(s2 n)1/2.

Leaves.
We have a(z)=t(u,z)-h(u,z)(1-z/r(u))1/2. This gives {t=r et+(u-1)r, 1=r et}, which gives {t(1,r)º t(1)=1, r(1)=r}, and also by differentiation wrt u {t'=(r et)' + r+(u-1)r', 0=(r et)'}, these two last equations give {t'(1)=r, r'(1)=-r2¹ 0}. This gives for sequences of trees t(1,r)=1, r'(1)¹ 0, t'u(1,r)¹ 0, and therefore Xn ® N* R. This also gives for functional graphs, with T(u,z)=t(u,z)-(u-1)z, T(1,r)=1,r'(1)¹ 0, T'u(1,r)=t'(1)-r=0, and therefore Xn ® N.

Nodes with in-degree r.
As before, a(z)=t(u,z)-h(u,z)(1-z/r(u))1/2. We have {t = r et+r(u-1)tr/r!, 1=r et+r(u-1)tr-1/(r-1)!}. This gives t(1)=1 and r(1) = r. By differentiation wrt u, we obtain t'(1) = r(1/r!-1/(r-1)!) and r'(1) = -r2/r!¹ 0. For sequences of trees, we get t(1,r)=1, r'(1)¹ 0 and, if r³ 2, t'u(1,r)¹ 0, which implies Xn ® N* R. If r=1, the limit law is normal. For functional graphs, we have T(u,z)=t(u,z)-z(u-1)(ar-1/(r-1)!-ar/r!). We get T(1,r)=1,r'(1) ¹ 0, and T'u(1,r)=0, which implies that Xn ® N.

Nodes at distance d from a cycle.
We have ad(u,z) =td(u,z)-cd(u,z)(1-ez)1/2, with t0(z)=ug(z), td(u,z)=zetd-1(u,z), c0(z)=uk(z), cd(u,z)=td(u,z)cd-1(u,z). This gives r'=0, td(1,r)=1, t'd(1,r)=1. Applying this results to g(u,z)=1/(1-ad(u,z)), we get T(1,r)=1, T'u(1,r)¹ 0,r=Cst, which implies that Xn® R.

Nodes with in-degree r.
(Same method.) We have for sequences of Cayley trees xn® N* R, and for functional graphs Xn® N.

Nodes at distance ³ d from a leaf.
(Same method.) From a leaf of their own subtree (sequences of Cayley trees), Xn® N* R. In the general case, Xn® N.

Nodes at distance d from a leaf.
(Same method.) If the path contains no cyclic edge, Xn® R* N (except if d=1, in which case Xn® N). If cyclic edges are allowed, for d£2, we have Xn® N. (Conjecture: this last result is true for all d.)

References

[1]
Drmota (Michael) and Soria (Michèle). -- Images and preimages in random mappings. SIAM Journal on Discrete Mathematics, vol. 10, n°2, May 1997, pp. 246--269.

[2]
Vitter (Jeffrey Scott) and Flajolet (Philippe). -- Analysis of algorithms and data structures. In van Leeuwen (J.) (editor), Handbook of Theoretical Computer Science, Chapter 9, pp. 431--524. -- North Holland, 1990.
This document was translated from LATEX by HEVEA.