Research News, August 2000

Previous News

Next News

Return to Research News Index

These pages are edited by Philippe.Flajolet@inria.fr.

Issue last updated August 20, 2000.

The AofA Metting in Gdansk, July 3-7, 2000

The Sixth Seminar on Analysis of Algorithms was held in Krinica Morska, an hour away from Gdansk, in a nice see resort. Attendees had the whole hotel all by themselves. The organization was superb, due to the efforts of Chairman Szpankowski and the constant tactful monitoring of the local organizers, especially Ryszard Sobczak and Andrzej Kusiuk. Nearly 60 participants came from four continents, with a bulk of the participants from Austria, France, and North America. The Piwo [beer] and Zubrówka [Polish vodka with the herb on which the wild buffalo feeds] were flowing as participants needed some ``magic potion'' to absorb the contents of some 43 lectures and communications. A nice feature this year was the possibility of having more of the younger gang, many of which talked on their Ph.D. thesis topic and gave excellent presentations.

There were five main lectures exploring probabilistic and analytic aspects of analysis of algorithms as we perform it to-day. (An account of other lectures will be given in a later issue of this bulletin).

David Aldous (Berkeley) talked on ``Zeta(2) and the random assignment problem''. The model is the complete bipartite graph K_n,n with random weights on edges that obey an exponential law of parameter 1. Let A_n be the cost of a random assignment. It has long been conjectured that

$\begin{displaymath} E(A_n)\mathop{\to}_{n\to\infty} \zeta(2)=\sum_{k=1}^\infty\frac{1}{k^2}.\end{displaymath}$ (1)

There is indeed a finite version of the conjecture, namely,

$\begin{displaymath} E(A_n)=\sum_{k=1}^m\frac{1}{k^2},\end{displaymath}$ (2)

which my friends from statistical physicics attribute to Parisi. This problem has been open for some 20 years: Karp proved in 1983 that E(A_n)<2; Aldous (1992) proved the existence of the limit and Goemans and Kodialam (1993) established that E(A_n) is a little over 1+e^-1. Mezard and Parisi have a nonrigorous argument based on ideas from statistical mechanics that , but, to this day, however, the conjecture stands. Aldous developed the ideas of an approach to proving the infinite n conjecture--this by viewing it as an infinite matching problem. This gives already the improved upper bound and there is good hope that the infinite n conjecture will succumb, given time (and effort?).
There are several interesting points in Aldous lecture. First, the general approach of the probabilistic methods consists in designing an infinite (continuous) model in which the finite scale models are immersed; see Aldous' continuum random tree. This is dual to analytic-combinatorial methods that aim at an exact modelling by generating function complemented by subsequent asymptotic analysis. (``First approximate, then analyse!" versus ``First analyse then approximate!'') Second, Aldous spent quite some time advocating ``pure thought'' proofs: this is the way he envisions the probabilistic approach. This made me wonder, however, as to the amount of technology that is needed. My impression is that everything is in the eye of the beholder, and perhaps what is ``pure thought'' for some is hard work for others? Conversely, perhaps, we, analysts, should devote more time structuring our proofs by taking the ``pure thought''motto as an inspiration?
A last fact regarding this motivating lecture. One may consider the analogous problem of the cost of a minimal spanning tree of K_n with edge weights that are uniform (0,1). Then Frieze showed that the expected cost tends to $\zeta(3)$ as $n\to\infty$ . I am not aware of a finite n version of Frieze's result.
Michael Drmota (Wien) gave a very nice survey lecture on analytic approaches to the distribution of height in binary search trees. (BST's) The problem was started by Robson (then in Canberra, now in Bordeaux) in 1979. Robson had established a sequence of lower bounds for the height of the form where the 's were very slowly increasing beyond 3. Robson had also observed that the right tails of the distribution of node levels gives an upper bound on height: the idea is that , where H_n is the height and D_n,k the number of nodes at level k in a randomly grown BST of size n. Now, a lot is known about the profile of trees, including the elementary fact that the E(D_n,k) are expressible in terms of Stirling cycle numbers, and large deviation estimates imply that an asymptotic upper bound on E(H_n) is ,where c=4.31107 is defined by and .Devroye (1986) succeeded in proving that is the correct asymptotic order of mean height. He did so by a suitable discretization of Kingman's trees of random variables.
Since 1986, a number of researchers have tried to quantify the distribution of height. This includes Devroye, Reed, Drmota, and Robson. There is in fact a fierce competition between probabilistic and analytic approaches, with Drmota's approach illustrating the latter. Perhaps there is a whole family of discrete limit distributions depending on the values of n. Drmota shows that the variance of tree height is O(1), a result obtained independently and simultaneously by Reed using probabilistic arguments. Such properties are also related to second order asymptotics of mean height. Drmota's approach is based on the following nonlinear differential recurrence for the GF of trees of height at most h:

$\begin{displaymath} y_{h+1}(z)=1+\int_0^{z} y_h(t)^2\, dt.\end{displaymath}$ (3)

The corresponding coefficient recurrences on [zⁿ]y_h(z) have a continuous limit that corresponds to a nonlinear convolution equation. By a careful study of this equation, Drmota is able to pull out estimations leading to the new result. For the same price, the analysis shows that, under the plausible (but yet unproven) assumption that the limit

$\begin{displaymath} \lim_{h\to+\infty} \frac{y_{h+1}(1)}{y_h(1)}\end{displaymath}$ (4)

exists, then, there is an asymptotic formula for the distribution of height:

$\begin{displaymath} \Pr(H_n\le h) \approx \Psi\left(\frac{n}{y_h(1)}\right),\end{displaymath}$ (5)

for some well-characterized function $\Psi$ . Still under the assumption (4), one can prove

$\begin{displaymath} \begin{array} {lll} E(H_n)& =& c\log n -\frac{3c}{2(c-1)}\log\log n + \Delta_1 +o(1)\\ Var(H_n)&=&\Delta_2+o(1),\end{array}\end{displaymath}$
for some well-characterized fluctuating functions .
With almost complete certainty, Drmota's analysis captures precisely the truth . This leaves however as an important open problem to establish (4): see the open problem section.
Philippe Flajolet (Rocquencourt) talked about ``Random Maps and Airy Phenomena'', based on joint work with Cyril Banderier, Michèle Soria, and Gilles Schaeffer. The paper is on my web page. Rather than plainly summarizing it, let me talk about the intensions. For many years, there had been good reason to suspect that Airy functions play a rôle in quantifying certain transition regions of random combinatorics. The Airy function can be defined either as a solution of the differential equation y''-zy=0 or by the integral representation

$\begin{displaymath} \hbox{\rm Ai}(z)=\frac{1}{2\pi}\int_{-\infty}^{+\infty} e^{i... ...!} \sin\left(\frac{2(n+1)\pi}{3}\right)\left(3^{1/3}z\right)^n.\end{displaymath}$ (6)

It is thus the prototype of integrals involving the exponential of a cubic.
Many limit distributions of analytic combinatorics are known to be attainable though perturbation of a singularity analysis or a saddle point analysis. The approximations are of an exponential quadratic form, e^-x², which usually leads to Gaussian laws. However, when there is some confleunce of singularities or some ``coalescence'' of saddle points, approximations of a more complicated form should be sought. Precisely, coalescence of two saddle points is known in applied mathematics to lead to expressions involving the Airy function.
The talk then focusses on the case of random maps. Recall that a map is a connected planar graph given together with a rigid embedding on the plane or the Riemann sphere. Consider now the core which is the largest 2-connected component of a map (this is in essence the largest submap obtained by breaking the original map at its articulation points). Then core size admits a limiting distribution that has several surprising features: the tails are highly dissymmetric, decaying like x^-5/2 on the left and like e^-x³ on the right. We proposed to call the distribution the ``map-Airy'' distribution: it arises precisely from a confluence of two saddle points (as seen via Lagrange inversion) or, equivalently, from a certain type of confluence of singularities (in the realm of the original generating functions) and it involves the Airy function--whence the name given to the distribution. Indeed, the map-Airy distribution is found to have density

$\begin{displaymath} {\cal A}(x)=2\exp\left(-\frac23 x^3\right)\left(x\hbox{\rm Ai}(x^2)-\hbox{\rm Ai}'(x^2) \right),\end{displaymath}$ (7)

and is, in disguise, a stable law of index $\frac32$ .
The talk by Soria replaces these results into the more general framework of composition of singularity schemes. The talk by Schaeffer makes explicit the generality of the approach. In fact a dozen or so types of maps exhibit the distribution (7) and this has implication in the fast random generation of maps with higher connectivity indices (till 4, as of now). Finally, readers of these pages have already heard about the Airy function, e.g., in the context of linear probing hashing. As a matter of fact, there is good hope to attack the evolution of the random graph G_n,m (n vertices and m edges) and of linear probing hashed tables by means of coalescing saddle points. See the AofA logo.
Svante Janson (Uppsala) talked about ``Four methods and one theorem--another look at hashing with linear probing''. A number n of items are inserted into a table of size m. The jth element is inserted at random place h_j (given by a hashing function and assumed to be random over ) if it is free; otherwise, the places are tried sequentially until an empty location is found. The quantity of interest is the total displacement D_mn. Three regimes are distinguished by the talk.

R₁
Very sparse tables: $n/\sqrt{m}\to a$ ; in this case D_mn converges to a Poisson law of rate a²/2. (Think of the birthdate problem!)
R₂
Sparse tables: $n\gg \sqrt{m}$ but $m-n\gg \sqrt{m}$ ;then the standardized version of D_mn is asymptotically normal. This is the region in which one wants to use hashing tables, especially when $n/m\sim \alpha$ for some $\alpha$ with $0<\alpha<1$ (in which case normality was already known).
R₃
Coalescence regime: $n\sim m-a\sqrt m$ ;then n^-3/2D_mn converges to a random variable W_a. This is when the table fills, blocks of contiguously occupied cells coalesce into large ``islands'', and the construction cost becomes nonlinear (n^3/2). The random variable W_a is related to Brownian excursion and W₀ is the Brownian excursion area (The latter fact is in Flajolet, Poblete, Viola, Algorithmica, 1998).

The first method builds upon a direct description of D_mn in terms of a simple functional of the occupancy profile of the table (that is, how many elements X_i adopt cell i as their fisrt choice). In the coalescence regime R₃, this quantity becomes a functional of the Brownian bridge in the asymptotic limit, namely,

$\begin{displaymath} W_a:=\int_0^1 \max_{s\le t} (b(t)-b(s)-a(t-s))\, dt.\end{displaymath}$ (8)

This method is related to works of Chassaing, Louchard, and Janson, but also, it'd seem, to Aldous' theory of the additive coalescent.
The second method is purely analytic. It makes use of the exact combinatorial correspondance between connected graphs and linear probing hashing (Knuth, Algorithmica, 1998). A careful analysis of generating functions in the coalescence region gives access to the moments that in turn determine the law W_a.
The third method deals with the intermediate range R₂. Then, there is a fairly large number of blocks in the table, each with enough variability, so that a normal law is expected. Here, this is established by a general lemma giving the distribution of sums of 2-dimensional random vectors conditioned by one of their coordinates. The approach is technically similar to earlier saddle point approaches but phrased in more probabilistic terms.
The fourth method deals with the very sparse regime and is much simpler than the other ones. Roughly, in the region R₁, collisions are rare and to first order asymptotics only blocks of size 2 tend to be created. For such rare events, Poisson approximations are found by well established methods (moments or Stein's method) of the theory of rare events.
Helmut Prodinger talked on ``Old and New results on Alternating Sums''. Alternating sums appear in several places in the analysis of algorithms and random discrete structures. Typically, a whole bunch of them arise from random digital trees (also known as tries). They are usually tough to deal with since they often exhibit ``exponential cancellation''. By this, is meant that the resulting sum is exponentially smaller than its largest terms. In such cases no local asymptotic analysis of individual terms can provide clues as to the asymptotic behaviour of the entire sum. Typical examples are already found in Knuth's volume 3. For instance

$\begin{displaymath} U_n=\sum_{k\ge2} {n\choose k} \frac{(-1)^k}{2^{k-1}-1}\end{displaymath}$ (9)

occurs in the analysis of radix-exchange sort, of tries, etc.
As exemplified by Equation (9), many alternating sums of interest to us involve binomial coefficients. The talk offered a perspective on both classical and newer instances. The starting point is known amongst computer scientists as ``Rice's formula'', following exercises in Knuth's books and the contributions of S.O. Rice who made use of it in several discrete models. In fact, the formula is developed already by Nörlund in his famous Vorlesungen über Differenzenrechnung (Kopenhagen, 1923). This formula reads

$\begin{displaymath} \sum_{k=1}^n {n\choose k} (-1)^{n-k}f_k= \frac{1}{2i\pi}\int_{{\cal C}} f(z)\, \frac{n!}{z(z-1)\cdots(z-n)}\,dz,\end{displaymath}$ (10)

for a suitable contour $\cal C$ . Given a number sequence (f_k), this requires a complex analytic ``lifting'' f(z) satisfying f(k)=f_k. Evaluation by residues of the integral then opens access to an asymptotic evaluation of the original discrete sum, in a way that is not without resemblance to Mellin transform techniques.
A new application of Rice's integrals is describes in the talk. It is relative to distributed maxima finding and sorting. There, n persons communicate over a shared access channel (if two or more talk at the same time, the communication is scrambled). The three algorithms studied in this context are: maxima finding; selection sort; quicksort. The point is that, in such an environment, finding the maximum or the pivot of quicksort now requires a variable number of communications over the channel. What is employed for resolving conflicts over the channel is in essence the leader-election algorithm of Prodinger (``How to select a loser'', Discrete Mathematics 1993), itself a simplified version of the tree protocol of Capetanakis-Tsybakov-Mikhailov. Since the protocols are closely related to digital trees, the analyses involve a mixture of recurrences. The paper pointed at below shows that, indeed, Rice integrals and allied techniques are instrumental and provide very precise information on the behaviour of the three algorithms. Technically, the integral representations involve the Riemann zeta function that lifts the Bernoulli numbers present in the analysis. (This is also related to what Knuth calls ``the hardest asymptotic nut that he ever had to crack''.)
Naturally, there is a general philosophy behind Rice's formula: In order to cope with a finite sum, extrapolate analytically the coefficients as well as the weights so as to obtain an equivalent complex integral representation by virtue of the residue theorem. Prodinger showed in his lecture how this could be extended to q-binomial alternating sums using functions akin to the q-Gamma function that itself lifts the q-factorials

$\begin{displaymath} (q,q)_n=(1-q)(1-q^2)\cdots(1-q^n).\end{displaymath}$
His treatment gives identities that can be seen as q-analogues of Stirling number identities (of the first kind, i.e., of the cycle type). There are relations with a model of random acyclic digraphs as studied by Andrews, Crippa, and Simon. I wonder whether there are combinatorial connections with records in sequences of geometric random variables, a subject otherwise dear to Helmut.

To be continued!