Two Not-That-Dull Functional Equations Arising in the Analysis of Algorithms

Wojciech Szpankowski

Purdue University

Algorithms Seminar

June 15, 1998

[summary by Philippe Jacquet]

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).

1   Introduction

The talk addresses two functional equations arising in the analysis of algorithms, namely, in the performance evaluation of the generalized digital search trees and the asymmetric leader election algorithm. These functional equations deal with Poisson transforms of the general recurrence
xn+b=an+ c pn xn + u
n
å
k=0
æ
è
n
k
ö
ø
pk (1-p)n-k (xk+xn-k),
where u and c are constants, an is a given sequence, and b³ 1 is a parameter. Together with suitable initial condition, this recurrence describes both algorithms. It was extensively investigated either for b=1 or c=0. The speaker presents asymptotic expansions of xn up to O(1) term. Interestingly enough, for both algorithms there appears a constant that must be evaluated numerically from the original recurrence. Analytic techniques of (precise) analysis of algorithms are used to establish these conclusions. In particular, the author uses analytic poissonization/depoissonization, Mellin transform and singularity analysis.

The results presented in this talk were obtained jointly with S. Janson, G. Louchard and J. Tang.

2   The Generalized Digital Search Tree Algorithm

The basic Digital Search Tree (DST) is a tree-like data structure. Each node in the tree contains one data. We assume that all data are encoded over a common finite alphabet of size, say V. Each one of the edges pending from a node is in correspondence with one symbol of the alphabet. Consequently the branching degree of each node cannot exceed V.

The insertion of a new data X in the DST proceeds as follows:
  1. Scan the first characters of data X in order to create a path in the DST with the symbol-edge correspondence;
  2. use the character after the last scanned character of X to create a new edge in the DST pending from the last node visited, and create a new node to store X.
The basic DST can be used to implement Lempel-Ziv compression algorithms. The successive data inserted in the DST are phrases scanned on the text to be compressed. Therefore the original text is divided into phrases, and since each phrase points to another phrase via a symbol-edge in the DST structure, the compressed code replaces each phrase by a pair (pointer, symbol).

In the following we consider data generated from a Bernoulli binary source over a probability vector (p,q).

The average depth of insertion EDn in the binary DST satisfies the following recursion valid for n>0:
(n+1)EDn+1=n+1
n
å
k=0
æ
è
n
k
ö
ø
pk (1-p)n-k (kEDk+(n-k)EDn-k).
The probability generating function Dn(u) of the depth of insertion satisfies:
(n+1)Dn+1(u)=1+u
n
å
k=0
æ
è
n
k
ö
ø
pk (1-p)n-k (kDk(u)+(n-k)Dn-k(u)).
The general case for data generated from Bernoulli source over V-ary alphabet (with probability vector (p1,...,pV)):
(n+1)Dn+1(u)=1+u
 
å
k1,...,kV
æ
è
n
k1··· kV
ö
ø
p
k1
 
1
··· p
kV
 
V
(k1D
 
k1
(u)+...+kV D
 
kV
(u)).
The generalized DST assume a capacity b for each node of the DST, i.e., each can store up to b data. The insertion algorithm is the same excepted that if the last visited node contains less than b data, then data X is stored in this node and no new node is created.

The functional recursion of p.g.f. Dn(u) is now the following:
(n+b)Dn+b(u)=b+u
 
å
k
æ
è
n
k
ö
ø
pk(1-p)n-k(kDk(u)+(n-k)Dn-k(u)).
The generating function of D(z)=ån EDn zn/ n!e-z satisfies the functional equation:
b
å
i=0
æ
è
b
i
ö
ø
i
zi
D(z)=z+D(pz)+D(qz).

The aim is to find an accurate asymptotic expansion of EDn. Via depoissonization argument it is equivalent to find an asymptotic expansion of D(n)=EDn+O(log n). To this end one makes use of the Mellin transform d(s)G(s)=ò0¥D(x)xs-1dx satisfies:
b
å
i=0
æ
è
b
i
ö
ø
(-1)id(s-i)=(p-s+q-s)d(s).
In other words (1-p-s-q-s)d(s) is a linear combination of d(s-i), i varying from 1 to b:
d(s)=
1
1-p-s-q-s
b
å
i=0
æ
è
b
i
ö
ø
(-1)i+1d(s-i).
It comes that d(s) is defined for -b-1<Â(s)<-1. The inverse Mellin transform expresses D(z) via an integration formula:
D(z)=
1
2ip
ó
õ
c+i¥


c-i¥
d(s)G(s) z-sds
for cÎ]-b-1,-1[. The asymptotic expansion of D(z) when z®¥ comes from the poles of d(s) and G(s) via application of the residue theorem. The poles of d(s) are the roots of 1-p-s-q-s, and the same roots repeat when translated on the right by integer values because of the identities between d(s) and d(s-i). The main singularity is at s=-1 which doubles the pole of G(s) and will contribute in a zlog z term in D(z)'s expansion.

Application of the residue theorem finally gives:
D(z)=
1
h
zlog z+ æ
ç
ç
è
h2-h
h2
+g-
f'(-1)
h
ö
÷
÷
ø		 z+zP1(log z)+O(log z),
with h=-plog p-qlog q and h2=plog2p+qlog2 q. Quantity P1(z) is periodic with small amplitude when log p/log q is rational (when the roots of 1-p-s-q-s are regularly spaced on the vertical axis Â(s)=-1), and o(z) otherwise. Quantity f'(-1) denotes the derivative of åi=1b(
b
i
)(-1)i+1d(s-i) at s=-1.

The question remains on how to compute a numerical evaluation of constant f'(-1). To this end one computes a numerically tractable expression of d(s) via the Mellin transform:
d(s)=
1
G(s)
ó
õ
¥


0
zs-1
 
å
n
EDn
zn
n!
e-zdz=
 
å
n
EDn
n!
G(s+n)
G(s)
.
Therefore
d(s)=
 
å
n
EDn
n!
s(s+1)···(s+n-1).
Using this formula and truncating it up to certain rank N gives a numerical evaluation of f'(-1). Unfortunately the error term can be proven to be of order O(log N/ N). There are probably better estimates which converge geometrically.

3   Leader Election

We don't give details on the problem of leader election. Via successive Bernoulli splits over a group of n people, one randomly selects a leader. We denote Xn the average number of steps needed to achieve this election over a population of n people. When the Bernoulli splits are all done over the same probability vector (p,q), one obtains the recursion for n³ 2:
Xn=1+qnXn+
 
å
k
æ
è
n
k
ö
ø
pkqn-kXk
which translates into a functional equation for the generating function L(z)=ånXne-zzn/n!:
L(z)=1-(1+z)e-z+L(pz)+L(qz)e-pz.
Using again the Mellin approach, L*(s) the Mellin transform of L(z) satisfies the identity:
L*(s)=
f*(s)-(1+s)G(s)
1-p-s
,
where f*(s) is the Mellin transform of f(z)=L(qz)e-pz. Since L(0)=0, L*(s) is defined for -1<Â(s)<0, and thanks to the exponential decrease of f(z), f*(s) is defined for all Â(s)>-1. There is a sequence of poles on the axis Â(s)=0 regularly spaced: sk=2ip k/log p, for k integer. The poles are simple for k¹ 0, the pole is double at s=0 due to the contribution of the pole of G(s). The double pole contributes in a -log z/log p term in the residue theorem applied to reverse Mellin transform. The other poles contribute to a periodic function which depends on f(s) at s=sk.

In summary for any M>0:
L(z)=-
log z
log p
+
1
2
+
1-g-f*(0)
log p
+P2(log z)+O æ
ç
ç
è
1
zM
ö
÷
÷
ø		 .
P2(x) is a periodic function of period log p and small amplitude. Using again depoissonization theorems one gets Xn=L(n)+O(1/n).

As with the generalized DST, the numerical evaluation of constant f*(0) remains. In this case we are luckier than with DST since f*(0)=ånXn qn/n which converges exponentially.

This document was translated from LATEX by HEVEA.