ANALYSIS of ALGORITHMS [RN 06-03]

Research News, June 2003

Previous News

Next News

Return to Research News Index

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

Issue dated June 30, 2003.

Renzo, Donatella, Francesca & Cecilia
(click to enlarge)

AofA 2003. The meeting took place in San Miniato, and old village of Tuscany, exactly half way between Firenze (Florence) and Pisa. An old convent completely refurbished, talks in a former chapel with acoustics well-suited to those who had experience in preaching, meals systematically featuring antipasti, primo piatto, and secundo piatto, Chianti and other fluids generously served at tables, a sympathetic Agriturismo with a welcoming pool and refreshing beers just nextdoors... All this contributed to a friendly atmosphere making the AOFA 2004 one of the great vintages. Grazie mille to Renzo (Sprugnoli) and his team, Donatella (Merlini), Francesca (Uncini), and Cecilia (Verri) for creating such a supportive environment [from left to right on the photograph above]

There were 67 regular participants representing many nationalities -- Austria, France, Cyprus, Belgium, Canada, Iran, Taiwan, Germany, Chile, Catalunya, Australia and New Zealand (Brendan and Mark could be easily spotted as they were constantly walking upside down), Uruguay, Brazil, India, USA, Italy (of course!), South Africa, South Corea, as well as, counting countries of origin, Poland, Israel and Egypt. In a way, thanks to Helmut Prodinger who represented South Africa), all continents were present.

&&&&&&&& PHOTO ALBUM &&&&&&&&

Back to science. There were 34 talks in total, ranging in duration from 15 minutes (short research announcements) to 60 minutes (survey talks). In addition a well-attended half-afternoon of 11 poster presentations created a lot of opportunities for scientific exchanges. The complete program can be found at the URL of the meeting. I will just give here a few indications on the five survey lectures delivered at the start of each working day.

Ralph Neininger

Ralph Neininger, now at Frankfurt, started the meeting with A classification of random recursive problems. Recursive divide-and-conquer algorithms are taught in every undergraduate C.S. curriculum, but at this level, one usually only teaches solution methods for the simplest recurrences, the ones describing worst-case behaviour: see for instance the ``Master Theorems'' in the classic book by Cormen, Rivest, and Leiserson. The probabilistic analysis of D&C algorithms is much more challenging. Already mean value and variance analyses may pose challenging problems as was apparent from talks by several speakers (e.g., Nevin Kapur). Neininger gave a highly useful synthesis of these recurrences which are typically of the type

$\begin{displaymath} X_n =X_{K_n}^{*}+X_{n-K_n}^{**}+T_n. \end{displaymath}$ (1)

There is the random variable describing the (random) cost of processing an input of size . The recursive algorithm divides the problem into a subproblem of size (which is also random) and a complementary problem of size , or close. The quantity , nicknamed the ``toll'', combines the cost of the initial divison step and the cost of recombining partial solutions. For many ``good'' algorithms, a randomness preservation property holds and the equation above does describe exactly what goes on. (By the way, $X^{*}$ , $X^{**}$ denote independent copies of random variables of type .)
The recursive method basically consists in viewing the fundamental recursion (1) as a fixed point equation. In this perspective the right hand side is first considered as an operator acting on probability measures (usually after some normalization involving mean and possibly variance, as well as some asymptotic approximations when passing from discrete recurrences to continuous limits). Next, quite a bit of subtlety is needed in choosing a suitable metric on the space of probability measures, but, with cunningness, this metric can often be taken so that this operator becomes a contraction. The usual fixed point theorem on contractions in general metric spaces [=such beasts must have a fixed point] will do the rest! Done in an inspired way, the method will often prove the existence of a limit distribution and provide effective bounds on the speed of convergence to this limit. Sometimes, the limit distribution can be identified; at least a functional equation of sorts will characterize it. Ralph's lecture brings a lot of structure to this process and from his work, we get valuable guidelines concerning a number of critical choices: Which moments do we need a priori? Which metric should one adopt? Which speed of convergence may we expect? When are we likely to encounter the inevitable Gaussian law? This line of research treads in the steps of earlier works of Rösler and Rüschendorf, and at the same time, it thoroughly renews it. As Ralph explained, applications are now known in the area of quicksort and its variants (median-based algorithms), quickselect, multiple quickselect (looking simultaneously for several quantiles), patterns in trees, maxima in certain two-dimensional regions (e.g., triangles), skip lists, and of course many random tree models and asssociated parameters (e.g., Wiener index and patterns in binary search trees), split trees in the sense of Devroye, recursive trees, etc. Go right now to Ralph's pages to learn more.

Luc Devroye

Luc Devroye's On various fast hashing schemes opened the second day. One might think that, forty years after Knuth's pioneering work on hashing, the subject had been exhausted. Luc's talk demonstrates convincingly that this is very far from being the case. For instance, Luc started by recalling an especially striking result of Azar, Broder, Karlin, and Upfal (in STOC 1994 and SIAM Comp. 1999). Say you use hashing with separate chaining. Consider the usual case where you throw balls into buckets, i.e., data items are accommodated in a table of linked lists, and the ``filling ratio'' $\alpha:=n/m$ is a constant bounded away from 0 and infinity. Any list has a length that obeys in the asymptotic limit the Poisson law of parameter $\alpha$ , namely, the law of a random variable such that

$\begin{displaymath} \Pr(X=k)=e^{-\alpha}\frac{\alpha^k}{k!}. \end{displaymath}$

In particular, the search cost is on average, the probability of having long lists is small, etc. However, some lists are due to be long, and a classical result from occupancy theory tells us that the longest list is about $\displaystyle \frac{\log n}{\log\log n}$ in probability. Thus, some elements have relatively long access paths in the table. Azar et al. proved in 1994 that you can do much better if you are given two hash functions instead of just one. Given data item , you compute the two possible addresses and and simply prefer to join the shorter of the two queues at and . (It's easy to augment the data structure so that this choice can be done at no cost.) Then, the surprise is that the longest list is in probability about $\log\log n$ . There is an exponential jump between the ``single'' [=usual] and the ``double'' [=joining the shorter queue] hashing strategy. The arguments used in the original proof are of a qualitative probabilistic nature. I wonder whether there one could have an analytic grasp on this phenomenon, say, stating with exact generating functions and posed this as an open problem in the Open Problems Session chaired by Helmut prodinger. Maybe, this is too hard a problem; but maybe there's some fascinating analytic structure in the case of a general ?
Luc then went on to discuss in-place hashing algorithms. There, no pointer is needed. An element to be placed in the table tries first location . Then, the (famous) linear probing method consists in trying consecutive places $a+1,a+2,\ldots$ , until one empty space is found. This evokes parking when a man and his dozing wife drive along a one way street. She wakes up and asks him to park as soon as possible, in which case the husband dutifully parks at the first available space. [This by now politically criticized formulation is due to Knuth, The Art of Computer Programming, vol. 3 and is an instance of Renyi's parking problem.] For the basic algorithm as described above--this is a sort of First-Come-First-Serve policy-- almost everything is known (see also recent developments in the talk of Svante Janson quantifying later stages of the algorithm) and results by Knuth, Pittel, Flajolet-Poblete-Viola and others are described in some of our earlier pages. Luc considers again the longest probe sequence and he does so for three policies: FCFS (the original First-Come-First-Serve), LCFS (Last-Come-First-Serve, where you kick out people parked earlier at your desired parking space), and Robin Hood (where people parked closer to their intended location are displaced). These versions are due to Poblete and Munro for LCFS and to Pedro Celis (1986) for Robin Hood. Luc shows what to expect in these three situations, namely

$\begin{displaymath} \left\{\begin{array}{lll} M_n^{FCFS}&\approx &\displaystyle ... ...{R.H.}&\approx& \displaystyle \log_2\log n. \end{array}\right. \end{displaymath}$ (2)

There, the symbol $\approx$ expresses informally various convergence-in-probability results due to Devroye, Morin, and Viola. Robin Hood strategies lead to what is again an exponential improvement. A lesson of more general value? Keep an eye on Luc's pages for much beautiful material on this and related questions...

Brigitte Vallée (with Bob Sedgewick)

It is not everyday that we see thoroughly analysed an algorithm which is more than two millennia old. Brigitte Vallée's talk on Euclidean Algorithms are Gaussian does exactly that. The Euclid's algorithm is the ``grand-daddy'' of all algorithms [Knuth, Vol. 2] and, together with Egyptian multiplication, one of the oldest algorithms ever conceived. Of course, it computes the gcd of two numbers, and each time a computer system adds or muliplies two rational numbers in exact representation, it is bound to be used. Brigitte considers in fact several Euclidean algorithms, allowing for variants (e.g., based on centred divisions), and her method deals with a whole class of parameters including the number of iterations, the total length of a binary encoding (of the quotients), the number of occurrences of digit 17, and so on. What's happening there? First, as recognized since Euler's time at least, Euclid's algorithm is nothing but the continued fraction algorithm restricted to the rationals. Next, as perceived in the early days of ergodic theory (Khinchine, esp.), the continued fraction algorithm is closely tied to the dynamics of the fractional-part-of-the-inverse function $T(x)=\left\{\frac1x\right\}\equiv \frac1x-\lfloor\frac1x\rfloor$ over the reals. Finally, in the late 1960's Ruelle introduced transfer operators as a way to extract quantitative information about transformations of the interval. In its simplest form, this operator reads as

$\begin{displaymath} \mathcal{G}_s[f](x)=\sum_{h\in T^{-1}} h'(x)^s f(h(x)), \end{displaymath}$ (3)

where ranges over the inverse branches of the (non-injective) transformation . Functional analysis now enters the game.
People like Dieter Mayer in Clausthal and Doug Hensley in Austin had already uncovered fascinating properties of the special operator associated to the continued fraction transformation. In particular Hensley had obtained, by a difficult proof, that the number of iterations of the standard Euclidean algorithm is asymptotically Gaussian. Brigitte's tour de force in this joint work with Viviane Baladi (now at CNRS in Paris) consists in going into a direction that differs substantially from Hensley's, thereby making possible wide generalizations via much more transparent arguments. The starting point is that the transfer operator originally developed for transformations over the reals has great expressive power, and in particular, it makes it possible to synthetize Dirichlet generating functions. Brigitte has already made great uses of this device in recent years for average-case analyses; see, e.g., her spectacular analysis of the binary GCD algorithm in 1998. Then, coefficients (representing mean values) are recovered by a single inversion, and this is achieved by Perron's formula combined with a suitable ``Tauberian'' theorem (due to Delange). Now, distributions are wanted and this is much harder. Superficially, the situation resembles the one commonly encountered in analytic combinatorics: introduce a new variable that takes into account the parameter of interest; conduct a perturbation analysis of the univariate problem; hope to find a Quasi-Powers approximation for moment generating functions of the finite distributions; conclude by analytic analogy with sums of independent random variables. (The last process has been very nicely developed by Hsien Kuei Hwang in Taiwan starting from the mid 1990s.)
Brigitte proceeds to develop a suitable operator which is a ``deformation'' of (3) by means a supplementary variable and which exists for all parameters of reasonably slow growth. The goal is a Quasi-Powers approximation of sorts. In order to apply Perron inversion there are a number of difficulties, though. From the functional analytic point of view, one needs a pole free region in the form of a vertical strip, a sort of Riemann hypothesis for the eigenvalues of certain transfer operators. This is achieved by adapting (and even extending!) arguments due to Dolgopyat and recently published in Annals of Mathematics. Other technical difficulties arise due to somewhat misbehaved Perron integrals for which an ``unsmoothing'' process needs to be designed. (Roughly, you have to go for a second-order Perron, then undo the effect of Cesàro averages.) Finally, the Quasi-Powers approximations are obtained for real arguments only, so that effective versions of Laplace inversion à la Alladi, Stef, and Tenenbaum [see here the Stef-Tenenbaum paper] are needed (rather than the more customary Berry-Esseen). The final miraculous outcome is what the title says: for the standard Euclidean algorithm and its major versions, all parameters induced by a slow-growing unit cost (incurred at each stage of the algorithm) exhibit asymptotic normality when taken over the set of all fractions with denominator $\le N$ . Wow! Keep an eye on Brigitte's well-crafted research pages, where the paper should surface soon.

Brendan McKay (with his computer)

Brendan McKay's lecture on The multidimensional saddle-point method served as an eye opener on a miraculous and still mysterious method of asymptotic enumeration. First a few words of context. Asymptotic enumeration is a priori a univariate problem that usually relies on the process of extracting asymptotically coefficients from a given generating function. Odlyzko and I formalized singularity analyis in the late 1980s as a way to perform this task for a wide class of functions with singularities at a finite distance in the complex plane. When functions are entire or grow too fast at their finite singularities, the saddle point method takes over. It's all good and well, but it tends to be restricted to combinatorial structures which are like lego pieces assembled according to simple rules (the constructible classes). In the analysis of related algorithms, these developments go well with average-case problems (sometimes also higher moments by pumping), as these remain essentially univariate problems.
Bivariate methods started essentially with Ed Bender and his collaborators (Rod Canfield, Bruce Richmond, and others) in the 1970s. Bender showed us that limit laws could be systematically derived from bivariate generating functions by a method that amounts to perturbing univariate analyses of functions at singularities (see also Flajolet-Soria for later developments). A focal point is the extraction of Quasi-Powers approximations arising from a smooth displacement of either a singularity or a singular exponent--I have already mentioned Hwang's unifying theory. These methods are suitable for finding limit distributions in the central regime but often stop short of providing uniform asymptotic estimates in wide regions, that is, they don't provide uniform large deviation results. In the late 1990's, Robin Pemantle proposed to use the geometry of singular varieties in order to remedy this situations. When doing so, we're diving into the world of holomorphic functions of several complex variables. Pemantle's research is still in progress but several works by him and collaborators (Mark Wilson, Manuel Lladser) already suggest that it is due to become a fundamental tool in years to come. (At San Miniato, there were related posters by Manuel Lladser and Marianne Durand). The jump from bivariate to trivariate, and so on, seems to be comparatively simpler. All in all, we have a handle on asymptotic combinatorics, when problems are expressed as a 1-dimensional or low-dimensional asymptotic coefficient extraction from generating functions.
Brendan introduced what could be termed high-dimensional analytic methods. Precisely, in this perspective, the problem of enumerating objects of size is first expressed as an -dimensional Cauchy integral. Unbelievable, eh! Say you want to enumerate 3-regular graphs. The generating function in variable $\prod_{i<j}(1+z_iz_j)$ , once expanded, provides an encoding of all graphs, with degrees of nodes all accounted for. Thus, the number of 3-regular graphs of size is simply

$\begin{displaymath} \begin{array}{lll} R_n^{(3)}&=&\displaystyle [z_1^3z_2^3\cdo... ...\frac{dz_1dz_2\cdots dz_n}{z_1^4z_2^4\cdots z_n^4}, \end{array}\end{displaymath}$ (4)

where integration takes place over a product of circles around 0. Guided by the usual low-dimensional saddle point method, we decide to integrate along $\vert z_j\vert=1$ and, if we're believers in the kindness of nature, we may hope for concentration to take place when remains close to 1. To this purpose, go polar ( $z_j=e^{i\theta_j}$ ), use the fact that you're always the exponential of your logarithm, and you'll get an -dimensional integral with an integrand of the form

$\begin{displaymath} exp\left(Q(\vec \theta))+R(\vec\theta)+S(\vec\theta)+\cdots\right). \end{displaymath}$

There is a quadratic form, a quartic form, and so on. With a suitable rescaling of the $\theta$ 's, some powers of will come out and, with luck, you may be able to prove that only a few terms matter and get separation of variables. The method will provide the asymptotic number of d-regular graphs in ``good'' interesting regions. In fact, Brendan started with the enumeration of antipodal balanced sets on the -cube, in his words a "toy example", continued with regular graphs and tournaments, and concluded with Steiner systems and Latin squares. There identifying suitable regions and understanding concentration properties is the key. Beautiful stuff!
In summary, univariate asymptotics (counting estimates, mean values, other moments) require either singularity analysis (based on Hankel contour) or the saddle point, that is, nineteenth century technology tuned to modern needs. Bivariate, trivariate, etc, asymptotics when restricted to central regimes rely on perturbation of these methods, concluding with the continuity theorems for either Fourier or Laplace transforms and bounds either à la Berry-Essen or à la Alladi-Tenebaum-Stef (see the discussion of Brigitte's talk). ``True'' multivariate asymptotics covering wide regions need the theory of functions of several complex variables, a twentieth century development. Brendan teaches us strangely enough, how to approach univariate problems (counting) by means of -dimensional integrals with very large, provided the problem has enough symmetries and special concentration conditions are met. Several natural questions then suggest themselves. What can the method capture in combinatorics? [Work by Ira Gessel in the mid 1980's could be relevant.] Can one provide turnkey results making it possible to apply the methods systematically to wide classes of symmetric problems? Can one develop a perturbative analysis and, in addition, get limit distributions? (E.g., we know from Bender, Canfield, and Gardy that fixed-dimensional saddle point can be perturbed, leading to Gaussian laws.) Brendan's method, invented in the 1990's, should become a fundamental method of asymptotic combinatorics in the 21st century. Watch for developments on Brendan's pages.

Philippe Flajolet (with Wojtek Szpanowski [on the left])

Philippe Flajolet on Analytic Urns I gave a talk based on joint work with Joaquim Gabarro and Helmut Pekari from Barcelona. We deal with urn models often know as Pólya urns: there are balls of several colours; at any given time you point (randomly) to a ball in the urn and based on its observed colour, you add and subtract a certain number of balls according to a fixed rule. The ancestry of these models goes at least to Laplace (in his wonderful Théorie analytique des probabilités of 1812, a book that has been recently reprinted), who himself quotes Bernoulli probably motivated by games of chance. Here, I consider the case of two colours, say Black and White, and the rules are simply described by a $2\times2$ matrix $\left(\begin{array}{cc} \alpha&\beta\\ \gamma&\delta\end{array}\right)$ . This means things like: if you draw a black ball, then use the first column and add $\alpha$ black balls and $\beta$ white balls to the urn. Such models can be generalized ad libitum and they have great modelling capabilities in epidemics, statistics, probability theory, and so on. Closer to us, Mahmoud and Smythe have in recent years demonstrated their usefulness in analysing various tree models like recursive trees, locally balanced search trees, bucket trees, to name a few. In the talk, I restrict attention to models for which the 2x2 matrix has constant row sum: $\alpha+\beta=\gamma+\delta=s$ . In other words, the ``weight'' of the urn increases deterministically by at each stage.
The big news is that you're not bound to probabilistic approximations, but you can play complex analysis with these beasts. There's a partial differential equation (PDE) for the bivariate generating function (BGF) describing the composition of the urn at various epochs. Thanks to some nice special structure, this linear first order PDE is of a type that allows some separation of variables, leading to a solution that only involves quadratures: the BGF H can be obtained from elementary function by means of algebraic operations, integration, and inversion. Given this, we may legitimately expect to find dominant singularities without too much pain, while being able to analyse the effect of shaking the auxiliary variable near 1. For the subclass of urns ``with subtraction'' (i.e., $\alpha,\delta<0$ ), the theory is complete and one gets in this way that the composition of the urn at some large time is Gaussian (this is originally due to Bagchi and Pal, 1985), that the speed of convergence to the Gaussian limit is $O(n^{-1/2})$ (due to Gouet, 1993), but we also get the precise structure of moments of all orders and a determination of the large deviation rate function.
There's some nice math in all this; at least some math I thoroughly enjoyed learning about and [modestly] practicing. The BGF is expressed in terms of a fundamental function $\psi$ which is in essence the inverse of an Abelian integral over the Fermat curve (where $h=s-\alpha-\beta$ ). For instance, for the model $\mathcal{T}_{2,3}$ associated with the fringe analysis of 2-3 trees, where the matrix is $\left(\begin{array}{cc}-2&3\\ 4&-3\end{array}\right)$ , this integral is

$\begin{displaymath} I(u):=\int_0^u \frac{t}{(1-t^6)^{5/6}}, \end{displaymath}$ (5)

and the function $\psi$ is parameterized by it and another similar-looking integral. Now comes something especially nice: the general theory sketched above can be pushed much farther in the case of this $\mathcal{T}_{2,3}$ urn studied earlier by Mahmoud as well as Panholzer-Prodinger [look at THIS]: there are solutions expressible in terms of elliptic functions. In fact, the methods are general enough to enable us to detect all urn models of the type considered that admit of elliptic function solutions: there are six of them exactly and these correspond to the tiling groups of the Euclidean plane. Riemann surfaces and the genus of the Fermat curve play a rôle in this discussion. The methods can also be adapted to some urn models with positive diagonal entries, where one can detect the occurrence of stable laws, a feature that also seems to be new and nicely complements nonconstructive martingale arguments due to Raùl Gouet (Chile) in the course of the 1990's.
All in all, after some more work (there is work in progress with Vincent Puyhaubert on these questions), we plan to come up with a complete analytic model for all $2\times2$ urn models with constant row sum, including negative, positive, or zero diagonal entries and all sorts of mixed cases. There are natural questions. Can one extend the theory to ``balanced'' (i.e., constant row-sum) models of dimension $\geq3$ ? Vincent and Marianne (Durand) have some hopes and they have already found some analytically 3x3 solvable models. Can we deal with unbalanced models? There, I'll be much more pessimistic. At least it's nice, I think, to find a theory which unifies what were before rather disparate models (e.g., coupon-collector, Ehrenfest, some Kotz-Mahmoud-Robert, Friedman, etc). Details are accessible from my research pages.

Ceiling in Galleria dei Uffizi, Firenze

(Last updated, July 6, 2003)

To be continued...