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) ®
a_{n} or a_{n,k}''. Then
by Cauchy's formula, we get for structures A
a(z) = 



= 

a_{n} 

Þ 

= 

ó õ
a(z) 

. 
When considering marked structures with parameters
{ A,w}, (w is a mapping A ®
N),
we have
a(u,z)= 

u 


= 

a_{n,k}u^{k} 

.

In this case, a_{n,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/1a(z) 
 by number of cycles 
G =
Set(·Cycle( A)) 
g(u,z)= exp(ulog1/1a(z)) 
 by number of trees 
G =
Set(Cycle(· A)) 
g(u,z) = 1/1u a(z) 

Table 1:
Some examples of generating functions
By a classical theorem about characteristic functions
(X_{n}) converges weakly to Y if and only if f_{X}_{n}(q) converges to f_{Y}(q) for all q, with f_{Z} = E(e^{iq Z}).
We also have a(u,z)=å_{n,k}u^{k} z^{n}/n! = å_{n}
p_{n}(u)z^{n}/n!, which gives the probability generating function
of X_{n} as p_{n}(u)/p_{n}(1) = å_{n} Pr(X_{n} =k)u^{k}.
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 G_{f} with vertices {1,...,n} and edges
(i,f(i)), for 1³ i ³ n. Each component of
G_{f} 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 squareroot type.
For trees, we get
a(u,z) = t(u,z) h(u,z)(1z/r(u))^{1/2}. For sequences of trees,
we get an expression of the form 1/(1a(u,z)), and for random mappings
an expression of the form
s(u,z) = 
1 

1T(u,z)+h(u,z)(1z/r(u))^{1/2} 

. 
We recall that when we get an expression of the form 1/(1uC(z)),
the asymptotic distribution of the corresponding random variable
depends on the value C(r_{c}), where r_{c} is the only
singularity on the circle
of convergence of C(z). If C(r_{c})>1, the limit law is normal;
if C(r_{c})<1, the limit law is derivative of geometric, and if
C(r_{c})=1 the limit law is Rayleigh.
3 Examples
Leaves.
For Cayley trees, we have a(u,z) = z e^{a(u,z)} + z(u1),
for sequences of trees, s(u,z)=1/(1a(u,z)), and for functional
graphs
Nodes of arity r.
For trees,
a(u,z) = z 
æ ç ç è 


+
u 

ö ÷ ÷ ø 
= z
e^{a(u,z)}+z(u1) 

. 
For sequences of trees, we have s(u,z)=1/(1a(u,z)), and for
functional graphs,
g(u,z) = 
1 

1a(u,z)+z(u1) 
æ ç ç è 

 

ö ÷ ÷ ø 


. 
Nodes at distance d from a cycle.
We have the recurrence
a_{0}(u,z)=ua(z), a_{d+1}(u,z)=ze 

. 
For functional graphs, this gives g(u,z) =1/(1a_{d}(u,z)).
Nodes with r preimages in total.
For trees, we have a(u,z) = ze^{a(u,z)}+(u1)a_{r+1}z^{r+1},
where a_{r+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³ 0}a^{p}(z)/p). This gives
g(u,z) =


exp 
æ ç ç è 


(u^{p}1) 

ö ÷ ÷ ø 
= 
K(u,z) 

1a(u,z)+(u1)a_{r+1}z^{r+1} 

. 
Nodes d iterated.
(These nodes are at distance ³
d from a leaf.)
For trees, we have
a_{d}(u,z)=xue 

(u1)l_{d}(z) with 
l_{0}(z)=0, l_{d+1}(z)=ze 

. 
For functional graphs, we have, for nodes at distance ³ d of a
leaf of their subtree, s_{d}(u,z) = 1/(1a_{d}(u,z)). For nodes at
distance ³ d of a leaf, we have
g_{d}(u,z) = 

=

1 

1a_{d}(u,z)(u1)l_{d}(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
nonnegative 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)(1z/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,k}g_{n,k}u^{k} z^{n}
corresponding for variables X_{n} to a probability distribution
Pr(X_{n}=k)=g_{n,k}/g_{n}. We consider a local expansion in the
neighbourhood of u=1,z=r(u), of the form
g(u,z)= 
1 

1T(u,z)+h(u,z)(1z/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),

If r'(u) = 0 and T'_{u}(1,r)>0, then
X_{n}/(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/2x^{2}). Moreover
E(X_{n})»(p n/2l)^{1/2} and Var(X_{n}) »
(2p/2)n/l.
 If r'(1)¹ 0 and T'_{u}(1,r)=0, then X_{n}µ
n/(s^{2} n)^{1/2} ® N(0,1), where µ =
r'(1)/r(1) and
s^{2}=µ^{2}+µr''(1)/r(1). Moreover E(X_{n})» µ n
and Var(X_{n})» s^{2} n.
 If r'(1) ¹ 0 and T'_{u}(1,r)¹ 0, then
X_{n}  µ n/(s^{2} n)^{1/2}®
N(0,1)* R(s^{2}l), 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
X_{n}µ_{n}/(s^{2} n)^{1/2}® N(0,1),
(except if r'(u) = 0 and T(1,r)<1, in which case X_{n}
® d G, derivative of a geometric law).
The density and characteristic functions in these different cases are
as follows.

R (Rayleigh) f_{ R}_{(l)}(x)=l
xe^{l x}^{2}^{/2}, and
f_{ R}(q)=
1+iq(p/2)^{1/2}e^{q}^{2}^{/2}(1ierf(q/(2)^{1/2})).
 N (Normal)
f_{ N}(x)=1/(2p)^{1/2}e^{x}^{2}^{/2} and f_{ N}(q)=e^{q}^{2}^{/2}.
 N* R (Normal conv. Rayleigh)
f_{ N}_{*}_{ R}(x)=(e^{x}^{2}^{/4}e^{x}^{2}^{/2})/(2p)^{1/2}+xe^{x}^{2}^{/4}/2(2)^{1/2}erf(x/2)
and f_{ N}_{*}_{ R}(q)=
f_{ N}(q)× f_{ R}(q).
Proof.(Sketch)
Let g(u,z) = å_{n³ 0}p_{n}(u)z^{n}/n! with p_{n}(1)=g_{n}.
The proof rests on the convergence of the corresponding
characteristic functions to (1) f_{ R}(q), (2)
e^{q}^{2}^{/2},
(3) e^{q}^{2}^{/2}× f_{ R}(q). For instance, in
case (1), the characteristic function
p_{n}(e^{iq/(n)}^{1/2})/g_{n} 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 X_{n} the law of X_{n}µ n/(s^{2} n)^{1/2}.
Leaves.
We have
a(z)=t(u,z)h(u,z)(1z/r(u))^{1/2}.
This gives {t=r e^{t}+(u1)r, 1=r e^{t}},
which gives {t(1,r)º t(1)=1, r(1)=r}, and
also by differentiation wrt u {t'=(r
e^{t})' + r+(u1)r', 0=(r
e^{t})'},
these two last equations give {t'(1)=r, r'(1)=r^{2}¹ 0}.
This gives for sequences of trees
t(1,r)=1, r'(1)¹ 0, t'_{u}(1,r)¹ 0, and
therefore X_{n} ® N* R.
This also gives for functional graphs, with T(u,z)=t(u,z)(u1)z,
T(1,r)=1,r'(1)¹ 0, T'_{u}(1,r)=t'(1)r=0, and
therefore X_{n} ® N.
Nodes with indegree r.
As before, a(z)=t(u,z)h(u,z)(1z/r(u))^{1/2}.
We have
{t = r e^{t}+r(u1)t^{r}/r!, 1=r
e^{t}+r(u1)t^{r1}/(r1)!}. This gives
t(1)=1 and r(1) = r. By differentiation wrt u, we obtain
t'(1) = r(1/r!1/(r1)!) and
r'(1) = r^{2}/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 X_{n} ®
N* R. If r=1, the limit law is normal.
For functional graphs, we have
T(u,z)=t(u,z)z(u1)(a^{r1}/(r1)!a^{r}/r!).
We get T(1,r)=1,r'(1) ¹ 0, and T'_{u}(1,r)=0, which
implies that X_{n} ® N.
Nodes at distance d from a cycle.
We have
a_{d}(u,z) =t_{d}(u,z)c_{d}(u,z)(1ez)^{1/2}, with t_{0}(z)=ug(z),
t_{d}(u,z)=ze^{t}_{d1}^{(u,z)}, c_{0}(z)=uk(z),
c_{d}(u,z)=t_{d}(u,z)c_{d1}(u,z).
This gives r'=0, t_{d}(1,r)=1,
t'_{d}(1,r)=1.
Applying this results to g(u,z)=1/(1a_{d}(u,z)), we get
T(1,r)=1, T'_{u}(1,r)¹ 0,r=Cst, which implies that
X_{n}® R.
Nodes with indegree r.
(Same method.) We have
for sequences of Cayley trees x_{n}®
N* R, and for functional graphs
X_{n}® N.
Nodes at distance ³ d from a leaf.
(Same method.) From
a leaf of their own subtree (sequences of Cayley trees),
X_{n}® N* R. In the general case,
X_{n}® N.
Nodes at distance d from a leaf.
(Same method.) If the
path contains no cyclic edge,
X_{n}® R* N
(except if d=1, in which case X_{n}® N). If
cyclic edges
are allowed, for d£2, we have X_{n}® 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. 246269.
 [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. 431524. 
North Holland, 1990.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.