Previous News
Next News
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".