Research News, August 1997

Previous News Next News

Return to Research News Index

August 1997 Issue

[1/08/97] Mergesort. The latest issue of Random Structures and Algorithms [11 (1), August 1997] contains a paper by M. Cramer on the analysis of Mergesort in its basic recursive top-down version. What we now know from this paper and its predecessors (e.g., Flajolet and Golin, Acta Informatica, 1994) is that the expected cost of Mergesort, like for many other divide and conquer algorithms, involves fluctuating functions of a fractal nature. Like many sorting algorithms, the comparison cost of Mergesort has a limit distribution that is Gaussian. Cramer establishes this fact by means of a "contraction method" that is somewhat reminiscent of Rösler's approach to Quicksort. Bottom-up Mergesort was analysed by Panny and Prodinger (Panny and Prodinger, Algorithmica, 1996).

[2/08/97] Gaussian Laws. The Random Structures and Algorithms Conference is taking place in Poznan. The programme is exciting! Here are the slides of Philippe Flajolet's lecture on "The Ubiquitous Gaussian Law in Analytic Combinatorics" [ps.gz:408kb] (coathored by H. K. Hwang and M. Soria, and also based on joint work with Sedgewick). For more detailed informations, see the preliminary version of a chapter on limit laws that's part of a future book entitled Analytic Combinatorics by Flajolet and Sedgewick.

[10/08/97] Depoissonization. We usually need to analyse certain combinatorial or probabilistic parameters under the assumption that the size N of the structure considered is fixed. On the other hand, it is often easier to deal with Poisson models where size is a random variable that obeys a Poisson law of parameter z, since this entails nice independence properties. Returning from the Poisson model to the "fixed size" model is called depoissonization. Roughly speaking, this is a Tauberian problem (that is, coming back from averages to original quantities) and several techniques are known. Ramanujan was already interested in such questions in the 1910's. Szpankowski and Jacquet have written a big paper of some healthy 67 pages that is due to appear as a Fundamental Study in Theoretical Computer Science (TCS). Here is a preprint version. Their study is based on the fact that if enough information is available for complex Poisson parameter z (a seemingly nonprobabilistic situation!), then the fixed size model can be reconstructed by contour integration and the saddle point method. This is called analytic depoissonization. Thus analytic depoissonization comes as a useful addition to other known techniques based on elementary series expansions, Tauberian theorems, Rice's integrals, or Mellin transforms and "Dirichlet depoissonization". Amongst the many problems discussed by Jacquet and Szpankowski, you'll find: digital search trees and their many variants, randomized leader election, communication protocols, probabilistic counting, etc. Leader election, by the way is also treated in a recent paper of the Electronic Journal of Combinatorics.



[27/08/97] Recursive algorithms, probability metrics, and contraction method Rüschendorf and Cramer have sent a batch of papers that deal with the analysis of limit distributions in recursive structures and algorithms. These papers originate from work done largely at Freiburg. Roughly, the idea is that once suitably normalized, the distribution of costs of a recursive algorithm is likely to be expressed by a fixed-point equation. This fixed point equation may then well be tractable if a contraction theorem applies (this requires an appropriate metric space of probability distributions). In a way, this is comparable to Roesler's derivation of the limit law of quicksort (known to be nonGaussian). It constitutes an attractive alternative, often more "transparent", to the martingale approach of Regnier (see Mahmoud's book Evolution of Random Search Trees) or the moment approach of Hennequin that together first led to the limit law of quicksort. I have already mentioned Cramer's treatment of Mergesort (the limit law there is Gaussian) and this was done along the lines of the metrics contraction approach.
The general principles of the method are for instance discussed in a paper by Rachev and Rueschendorf (Probability metrics and recursive algorithms, Adv. Appl. Prob., vol. 27, 770-799 (1995)). Several applications are given in papers that emanate from this group, like: the size of digital tries (it is Gaussian, as first proved by Jacquet-Regnier and discussed in Mahmoud's book), some versions of bucket-sort (see also works by Devroye and his Lecture Notes on Bucket Algorithms), the depth of nodes in binary search trees (otherwise treated by Lyapounov's extension of the central limit theorem), tree communication protocols that are now known to the theoretical community to constitute attractive alternatives to "linear" protocols (a class to which the Ethernet belongs), and that are closely related to tries, etc.
I wonder whether some of this could be connected to the general study of divide-and-conquer recurrences that was conducted by Karp a few years ago, where Karp was mostly interested in approximate bounds and "large deviations".