On the Width of Labeled Trees

Jean-François Marckert

Université de Nancy 1

Algorithms Seminar

April 12, 1999

[summary by Christine Fricker]

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
We consider An the set of all rooted labeled trees with n nodes. We denote by Zi the number of nodes at distance i from the root and by Wn=max0£ i £ n Zi the width of the tree. The aim of the talk is to present results on convergence of moments of Wn (correctly renormalized) to those of the maximum of the normalized Brownian excursion and to give a tight bound for the rate of convergence. For the proof, the connections between especially breadth first search random walk on trees, random walk with Poissonian increment, parking function and empiric process of mathematical statistics are described.

The results presented in this talk were obtained jointly with P. Chassaing.



1   Introduction

A rooted labeled tree with n nodes is a connected graph with n vertices and n-1 edges where a vertex, the root, is specified. Tight bounds of the width Wn of rooted labeled trees with n nodes are given, answering an open question of Odlyzko and Wilf [3] that E(Wn) is between C1(n)1/2 and C2(nlogn)1/2. More precisely, we first present the result of Takacs [6] that Wn/(n)1/2 converges in distribution to the maximum m of the Brownian excursion, with the well-known theta distribution given by
Pr (m£ x)=
 
å
kÎ Z
(1-4k2x2)e
-2k2x2
 
.
However weak convergence does not answer completely the question of Odlyzko and Wilf. To fill this gap, we prove that
Theorem 1   For all p³ 1, |E(Wnp/np/2)-E(mp)|£ Cp n-1/4(logn)1/2 where m is the maximum of the normalized Brownian excursion.
The moments of m are well-known and given by
E(mp)=p(p-1)G(p/2)z(p)2-p/2.
For this we prove that there exists a sequence of normalized Brownian excursions of maximum mn such that, for all p³ 1,
E( | Wn/(n)1/2-mn |
p
 
 
)£ C'p n-p/4(logn)1/2
using that if q is defined by 1/p+1/q=1 and if X and Y are two real random variables in Lp, then by Holder's inequality,
| E(Xp)-E(Yp) | £ p \| X-Y \|
 
 
p
\| X+Y \|
p/q
 
p
.

2   Relation Between Rooted Labeled Trees and Parking Functions

In hashing with linear probing or parking, we consider n cars ci (1£ i£ n) arriving in this order at random in n+1 places {0,1,...,n}, where car ci is parking on its place hi if hi is still empty, otherwise car ci is trying places hi+1 mod n+1,... . We consider parking functions, i.e. sequences (hi)1£ i£ n such that place n is empty. A parking function is alternatively characterized by the sequence (Ak={i,hi=k}) 0£ k£ n of sets of cars that arrive on place k, with xk=card Ak. If yk is the number of cars that tried once to park on place k,
yk=yk-1-1+xk,     y0=x0.
The fact that place n is the empty place is given by
yk³ 1   (0£ k£ n-1),     yn=0
or equivalently
k
å
i=0
xi-k³ 1   (0£ k£ n-1),    
n
å
i=0
xi-n=0.     (1)

A labeled tree with vertices {0,1,...,n} rooted at 0 is also characterized by the sequence of disjoint sets (Ak)0£ k£ n whose union is {1,...,n} and the xk=card Ak satisfying (1). Indeed, Ak (k³ 1) (respectively A0) is defined as the set of new neighbors of the smallest element in Ak-1 (respectively 0) and (1) is the condition for the tree to be connected and to have root 0. The number of Ak (k³ 1) with cardinality xk (k³ 1) is proportional to the product of Poisson probabilities e-1/xk!. In other words the corresponding unlabeled tree is a Galton-Watson tree with Poisson(1) progeny, constrained to have n+1 nodes. Thus, the sequence y=(yk)0£ k£ n is the discrete excursion with length n of a random walk with increments xk-1. It is well-known that (yë ntû/(n)1/2)0£ t£ 1 converges in distribution to (e(t))0£ t£ 1 where e is a normalized Brownian excursion and maxk yk/(n)1/2 converges in distribution to m=max0£ t£ 1 e(t), which is theta-distributed.

The random walk (yk) (introduced in [1] and [5]) gives the profile of the tree (Zk) as a sub-sequence of (yk)
Zk+1=yl(k)
where l(k)=åi=1k Zi and the width Wn as
Wn=
 
max
k
Zk=
 
max
k
yl(k).
We prove in the following proposition that Wn=maxk yl(k) has the same behavior as maxk yk.

Proposition 1   For each p³ 1,
||Wn-
 
max
k
yk ||p=O(n1/4(log n)3/4).

This result is based on the slow variation of the sequence y=(yk)0£ k£ n. Indeed, Wc(n) defined as the set of sequences y=(yk)0£ k£ n such that, for all k and m such that k+m£ n,
|ym+k-ym|£ c(klog n)1/2
satisfies the following lemma.

Lemma 1   For all a>0, there exists c>0 such that, for all n,
1-Pr (Wc(n))=o(n
-a
 
).

This can be proved using (see Petrov [4]) that, if (Yk) is a random walk with increments Xk satisfying E(Xk)=0 and for some a>0, E(exp(a|Xk|)<¥, then there exists T,C1,C2>0 such that
Pr(|Yk|³ x)£
ì
ï
ï
í
ï
ï
î
2e
-
x2
4C1
 
if 0£ x £ C1T,
2e
-C2x
 
if x ³ C1T.
Then it remains to prove that E((maxk yk/(n)1/2)p)® E(mp) and to estimate the rate of convergence. This is the object of the next section.

3   Parking Functions and Empiric Processes

Consider the sequence (Ui)1£ i£ n of n i.i.d. random variables uniformly distributed on [0,1]. Let Fn(t) be the empiric distribution for (Ui)1£ i£ n i.e.
Fn(t)=
card{iÎ {1,...,n},Ui£ t}
n
,     (0£ t£ 1).
Process (Fn(t)) converges to (F(t))=(t), the distribution function of the uniform distribution. Especially, the empiric process (an(t))=((n)1/2( Fn(t)-F(t)))0£ t£ 1 converges in distribution to the Brownian bridge (b(t))0£ t£ 1.

There is a precise connection between parking functions and empiric processes. Indeed, consider the sequence (Ui)1£ i£ n of i.i.d. random variables uniformly distributed on [0,1] and realize parking in the following way: If UiÎ[k-1/n+1,k/n+1[, then car ci tries to park first on place hi=k. The last empty place V is given in terms of the empiric process.
Proposition 2   There is a unique T(n) in {0,1,...,n} such that
an(
T(n)
n+1
)=
 
min
1£ j£ n
an(
j
n+1
).
Moreover, T(n)=V.

It is easy to deduce that
½
½
½
½
 
max
k
yk
(n)1/2
-(
 
sup
0£ t£ 1
an(t)-
 
inf
0£ t£ 1
an(t)) ½
½
½
½		 £
1+2en
(n)1/2
where en=(n)1/2 sup0£ t£ 1|an(ë(n+1)tû/n+1)-an(t)| satisfies the following proposition.
Proposition 3   There exists A, C and K such that for all x and n,
Pr(en³ Clog n +x)£ An1-KCe-Kx.     (2)
Then an(t) is replaced by a Brownian bridge bn(t) using the following result of Komlos, Major and Tusnady [2].
Theorem 2   There exists a sequence of Brownian bridges (bn)n³ 1 and A, M, µ>0 such that for all n and x
an(t)=bn(t)+
cn(t)
(n)1/2
where Cn=sup0£ t£ 1|cn(t)| verifies for all x
Pr(Cn³ Alog n +x)£ Me
-µ x
 
.     (3)
Then
½
½
½
½
 
max
k
yk
(n)1/2
-(
 
sup
0£ t£ 1
bn(t)-
 
inf
0£ t£ 1
bn(t)) ½
½
½
½		 £
1+2(en+Cn)
(n)1/2
where Cn is introduced in Theorem 2. Using the fact that, if T is the almost surely unique point such that b(T)=min0£ t£ 1b(t), then e=(e(t))0£ t£ 1, defined by e(t)=b((T+t) mod 1)-b(T), is a normalized Brownian excursion independent of T, one has
½
½
½
½
 
max
k
yk
(n)1/2
-
 
sup
0£ t£ 1
en(t) ½
½
½
½		 £
1+2(en+Cn)
(n)1/2
.     (4)
Relations (2) and (3) give that || en+Cn ||p is bounded by Kplog n and thus (4) gives the following result.
Theorem 3   For each p³ 1,
½½
½½
½½
½½		 mn-
 
max
k
yk
(n)1/2
½½
½½
½½
½½
 



p
=O(
log n
(n)1/2
).
It is then easy to deduce Theorem 1.

References

[1]
Aldous (David). -- Brownian excursions, critical random graphs and the multiplicative coalescent. The Annals of Probability, vol. 25, n°2, 1997, pp. 812--854.

[2]
Komlós (J.), Major (P.), and Tusnády (G.). -- An approximation of partial sums of independent RV's, and the sample DF. II. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 34, n°1, 1976, pp. 33--58.

[3]
Odlyzko (Andrew M.) and Wilf (Herbert S.). -- Bandwidths and profiles of trees. Journal of Combinatorial Theory. Series B, vol. 42, n°3, 1987, pp. 348--370.

[4]
Petrov (V. V.). -- Sums of independent random variables. -- Springer-Verlag, New York-Heidelberg, 1975, x+346p. Translated from the Russian by A. A. Brown, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82.

[5]
Spencer (Joel). -- Enumerating graphs and Brownian motion. Communications on Pure and Applied Mathematics, vol. 50, n°3, 1997, pp. 291--294.

[6]
Takács (Lajos). -- Limit distributions for queues and random rooted trees. Journal of Applied Mathematics and Stochastic Analysis, vol. 6, n°3, 1993, pp. 189--216.
This document was translated from LATEX by HEVEA.