Abstracts

GF of walks (lattice paths) over and GF of walks over are related by nice combinatorial formulae (related to identities known in probality theory under the name of Spitzer formula), reflecting a variation of the cyclic lemma. They rely on the theory of the (pointing) operator and on some peculiar factorization (e.g. an excursion can be factorized into arches). This gives access to some parameters, such as the number of times that the minimum is reached, for which I derive the asymptotics. In general, there exist 3 distincts cases (depending on the "drift" of the walk) leading to 3 distincts limit laws. A deep use is made of the kernel method, our asymptotic analysis (saddle point method and analysis of singularities) relies indeed on the analytic properties of the roots of the kernel.

(Work related to my PhD thesis and a paper in preparation with Ph. Flajolet).

In a first part, basic notions of the discrete martingale theory are given: decompositions, inequalities, stopping theorems and main convergence theorems. Several examples allow to see how martingales can be found, how a martingale can be transformed and how a martingale concentrates the randomness. The case of exponential martingales is studied: first, it gives an easy example of a non convergent, nonnegative martingale. They are also a basic tool in the study of branching random walks (which are related to the height of a binary search tree). Moreover, exponential martingales provide the tails of the distributions of sums of random variables. On the same topics, namely the concentration of a random variable around its mean, the Hoeffding-Azuma inequality is mentioned and it is applied in the bin-packing problem.

In a second part, the previous tools are used for binary search trees. The convergence theorems give information on some cost variables. The random measure valued

Finally, extensions to the -ary search trees are given.

The average-case analysis of sorting algorithms and many random data structures often necessitates the resolution of some recurrences, linear or nonlinear. In this talk I will introduce a simple elementary approach (without complex analysis) to the ``asymptotic transfers'' for quantities defined by a recurrence equation of quite general type. The approach reveals not only the intrinsic insight of such recurrences but also reflects more analytic properties of the associated PGF and differential equations. Almost no knowledge on differential equations is needed for this approach. The class of recurrences we study cover examples like the generalized quicksort of Hennequin that has recently been analyzed by purely analytic approach, the analysis of quicksort using Tukey's ``ninther'' (the median of three medians-of-three) and its extensions. Our approach can be used to derive all moments (centralized or not) and limit laws of the main cost measures in a systematic way.

The interest of studying ``ninther'' is multi-fold: first the underlying cost measures introduce naturally several new recurrences of quicksort-type that are so messy that a more algebraic and abstract treatment is needed; second, we can vary the underlying scheme to produce more instances of ``phase changes'' of the limit laws.

This is joint work with Hsien-Kuei Hwang and Tsung-Hsi Tsai.

We revisit tries from several perspectives. Topics include universal laws of large numbers for trie parameters, partial match, and level compaction.

It is shown that the expected value of the height of digital search trees is given by

This is a joint work with Philippe Flajolet and Nevin Kapur.

We review the notion of an additive-type functional on m-ary search trees. Three examples of such functionals are space requirement, total path length, and log-product of branch sizes; the last of these three serves as a crude measure of the "shape" of the tree. The goal is to study the distribution of an additive-type functional applied to a tree built in a natural way from a uniformly random permutation of .

We provide a general framework for the exact and asymptotic analysis of such distributions. Singularity analysis (the extraction of asymptotic information about a sequence from the behavior of its generating function near singularities) can be extremely useful in the consideration of asymptotic distributions, but the tools currently available do not handle the log-product functional. We expand the singularity analysis tool kit by proving that if singularity analysis can be applied to each of two sequences, then it can also be applied to the Hadamard product of the sequences. This tool allows for the handling not only of the log-product functional, but also of a wide variety of asymptotic problems in combinatorics and probability.

Many combinatorial problems lead to algebraic generating functions, that is, functions that are solutions of polynomial equations. Asymptotic enumeration results then depend on being able to determine precisely the location and nature of singularities. The major theorem of ``Drmota-Lalley-Woods'' addresses such questions in the case of an important but special class of algebraic functions (the positive ones arising from ``strongly dependent'' polynomial systems).

The difficulty of the problem, at its fullest level of generality stems from the fact that algebraic functions are inherently multivalued. There appears consequently a ``connection problem'': Given initial conditions dictated by combinatorics, where are and which are the ``relevant'' singularities? We prove this problem to be decidable in relatively low computational complexity. A consequence is the effective computability of coefficient asymptotics for general algebraic functions.

The results are potentially applicable to any combinatorial class that admits of an algebraic generating function. Examples (to be evoked, time permitting) include all combinatorial classes described by context-free languages (via the Chomsky-Schützenbeger Theorem), several random walks and polyomino problems (via the ``kernel method''), several geometric configuration problems (e.g., the noncrossing configurations studied by Flajolet-Noy), trees and terms (following Meir and Moon's framework), planar maps (via Tutte's quadratic method), and so on.

[Some of this research is described in ``Analytic combinatorics: functional equations, rational, and algebraic functions'' by P. Flajolet, R. Sedgewick (Res. Rep. INRIA RR4103, January 2001, 98 pages). Some results represent ongoing research with Bruno Salvy and Cyril Chabaud.]

A systematic approach for limit laws based on calculating the asymptotics of higher moments is presented. When applied to recursively defined random variables, the approach reduces the calculations of all moments to essentially the derivation of "asymptotic transfers," which bridge the asymptotics of the costs of subproblems to that of the total cost in the underlying recurrence of the moments. Many applications of this approach to the analysis of algorithms will be indicated, including maxima in right triangle, quickselect, maximum-finding algorithms on a broadcast communication model, -ary search trees, generalized quicksort, recursive trees, tries, patricia tries, bucket digital search trees, greedy heuristics for matchings on Cayley trees, etc. Further improvements of the approach, yielding a rate to CLT, will also be given.

This is a joint work with Philippe Chassaing.

Throughout this presentation, the standard Brownian motion (BM) will be denotedby . Other classical BM are the reflected BM: , the BrownianBridge (BB) on : , the reflected BB on : , the Brownian Excursion:. The local time of at , will be denoted by and we define (area of t he reflected BB), conditioned on having a local time at the origin equal to . For some reasons that will be clear later on, we propose to call this distribution the "Generalized Ai ry Distribution".

We are interested in the moments of , i.e.

(1)

In [4], [3] and [1], we were interested in and we found that this was deeply related to some properties of . We also obtained a lin ear recurrence formula for the moments of . Motivated by a paper of Janson, [2], weintend here to analyze the corresponding properties of . Starting from (1), this analysis will be directly based on BB and Airy functions properties. The presentation is organized as follows. Part gives the basic results we need in the sequel and relates the moments of to an asymptotic form of the Airy function. Part provides an efficient recurren ce formula for the moments. Part is devoted to some asymptotic properties of the density . Part concludes the presentation.

Bibliography

1

P. Flajolet and G. Louchard.
Analytic variations on the Airy distribution.
To appear in Algorithmica.

2

S. Janson.
Asymptotic distributions for the cost of linear probing hashing.
http://www.math.uu.se/svante/papers/.

3

G. Louchard.
The brownian excursion area: a numerical analysis.
Computers and Mathematics with Applications, 10(6):413-417, 1984.

4

G. Louchard.
Kac's formula, Levy's local time and brownian excursion.
Journal of Applied Probability, 21:479-499, 1984.

I discuss the rate of convergence of the distribution of the (normalized) number of comparisons in Quicksort to its limit distribution. Several different distance measures are considered (, , Kolmogorov-Smirnov, and pointwise difference of Laplace transforms). The results are typically , although a minor gap remains for the Kolmogorov-Smirnov distance. This rate is believed to be the true rate of convergence, but rigorous lower bounds are only of the order of .

This is joint work with Jim Fill and is a continuation of his talks in the two preceding seminars in this series.

We find the asymptotic average composition of a class of nonclassic Polya urn models (not necessarily of fixed row sum) by embedding the discrete urn process into a renewal process with rewards. A subclass of the models considered has banded matrix urn schemes and serves as a natural modeling tool for the size of a class of random bucket trees. The class of urns considered extends known results for multicolor urns with constant row sums. The same asymptotic average results are shown to hold in the larger class. This provides an average-case analysis for the size of certain random bucketed multidimensional quad trees and -d trees, which are all new results. Some bucket trees have urn schemes with constant row sum, a special case that helps detect phase changes in the limiting distribution of the (normed) size of the tree. For these special cases one can appeal to a more developed urn theory to find a joint limiting distribution of the normed size up to a threshold value of the capacity of a bucket. Once that cut-off point is surpassed, normality ceases to hold. This case appears in paged binary trees (threshold 116), m-ary search trees (threshold 26), and bucket recursive trees (threshold 26). The asymptotic normality results and the phase change after the threshold in these trees are already known and we only provide alternative proofs via a unified urn models approach.

This a joint work with Alois Panholzer.

A non-crossing tree (NC-tree) is a tree drawn on the plane having as vertices a set of points on the boundary of a circle, and whose edges are straight line segments that do not cross. In this talk, we show that NC-trees with size are "almost" conditioned Galton-Watson trees. As corollaries, we give the limit depth processes and the limit profile of NC-trees (an so the limit law of the height, of the width, and the total path length).

In this work we present generic algorithms for the unranking and ordered generation of labelled combinatorial structures. Unranking means generating the -th combinatorial structure of a given size , given the rank and a specification of the combinatorial class. In the ordered generation, the goal is to generate all combinatorial structures for a given size and specification of the combinatorial class. We also provide a cost algebra for the complexity of these algorithms much in the line of the seminal work of Flajolet et al. on the random generation of labelled combinatorial structures. We show that the unranking algorithms have the same complexity as the corresponding algorithms for random generation and that the ordered generation algorithms will usually be of the same complexity as specifically designed algorithms (where the class to be generated is not a parameter of the algorithm).

This is joint work with Xavier Molinero.

The concept of Riordan matrices provides a remarkable characterization of many lower triangular arrays that often arise in combinatorics and in the analysis of algorithms. The theory has been introduced in the literature in 1991 by Shapiro et al. [6] and then examined closely from a theoretical and practical point of view in [2,3,4,7]. This study has pointed out that Riordan arrays are a powerful tool in the study of many counting problems.

In this talk we first present the main properties of these matrices referring in particular to some classical example such as Pascal, Catalan, Motzkin and modified Stirling (first and second kind) triangles; we then show some connections between Riordan arrays and both lattice paths and generating trees, a concept, the last one, which is more and more studied in the literature (see, e.g., [1,5]); finally we describe some examples concerning the applications of the Riordan array concept to the study of some parameters in the job scheduling of a slow device, to the enumeration and the analysis of some data structure such as hybrid trees and to some tiling problems.

Bibliography

1

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps.
Generating functions of generating trees.
Discrete Mathematics, to appear.

2

D. Merlini.
I Riordan Array nell'Analisi degli Algoritmi.
Tesi di Dottorato, Università degli Studi di Firenze, 1996.

3

D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri.
On some alternative characterizations of Riordan arrays.
Canadian Journal of Mathematics, 49(2):301-320, 1997.

4

D. Merlini, R. Sprugnoli, and M. C. Verri.
Waiting patterns for a printer.
In Proceedings of FUN with algorithm'01, The Island of Elba, 2001.

5

D. Merlini and M. C. Verri.
Generating trees and proper Riordan Arrays.
Discrete Mathematics, 218:167-183, 2000.

6

L. W. Shapiro, S. Getu, W.-J. Woan, and L. Woodson.
The Riordan group.
Discrete Applied Mathematics, 34:229-239, 1991.

7

R. Sprugnoli.
Riordan arrays and combinatorial sums.
Discrete Mathematics, 132:267-290, 1994.

The secondary structure of a RNA molecule is of great importance and possesses influence, e.g. on the interaction of tRNA molecules with proteins or on the stabilization of mRNA molecules. The classification of secondary structures by means of their order proved useful with respect to numerous applications. In 1978 Waterman, who gave the first precise formal framework for the topic, suggested to determine the number of secondary structures of size and given order . Since then, no satisfactory result has been found. Based on an observation due to Viennot et al. we will derive generating functions for the secondary structures of order from generating functions for binary tree structures with Horton-Strahler number . These generating functions enable us to compute a precise asymptotic equivalent for . Furthermore, we will determine the related number of structures when the number of unpaired bases shows up as an additional parameter. Our approach proves to be general enough to compute the average order of a secondary structure together with all the -th moments and to enumerate substructures such as hairpins or bulges in dependence on the order of the secondary structures considered.

Well-known contraction arguments for the derivation of limit laws for parameters of random recursive structures and algorithms based on the minimal -metric (Wasserstein-metric) are extended to recurrences of random vectors of parameters.

This leads besides multivarite limit laws to an easy access to the asymptotic correlation of two parameters. An application is given on the joint behavior of the number of key comparisons and key exchanges of the Quicksort algorithm.

A multivariate point of view may also cover univariate recursions with certain "forbidden" dependences in the recurrence. An example is the Wiener index of a random binary search tree.

Although often asymptotic normality cannot be proven by the minimal -metric (requiring a change of the metric) some exceptional examples are given, e.g., the number of coin flips in "leader election".

This talk is mainly based on my preprint On a multivariate contraction method for random recursive structures with applications to Quicksort.

We consider arithmetical expression trees. The result of the expression is called the valuation of the tree. Defining as the random variable equal to the valuation of a tree of size (number of internal nodes), we study the limit distribution of , for going towards , in particular cases. We will only consider binary trees, and hence binary operators.

We first constrain the leaves (external nodes) to be labelled by integers belonging to a finite set , with positive P[] and P[], and the internal nodes to be labelled by and with probabilities and . For Catalan trees we obtain discrete limits. For binary search trees, the limit depends on .

We then consider trees with a distribution of operands having a variance, and operators and put on internal nodes with probabilities and . For Catalan trees we obtain Gaussian limits (excepted for degenerated cases), while for binary search trees, the limit once again depends on .

We focus on the Waterloo variant of the index calculus method for the discrete logarithm problem in finite fields. We provide a rigorous proof for the heuristic arguments for the running time of the Waterloo algorithm. This implies in studying the behavior of pairs of coprime smooth polynomials over finite fields. The proof involves a double saddle point method that is in nature similar to the one of Odlyzko for the rigorous analysis of the basic index calculus.

[Joint work with Michael Drmota.]

In this talk we shall analyze the Hamiltonian properties of faulty random networks. This consideration is of interest when considering wireless broadcast networks. A random geometric network is a graph whose vertices correspond to points uniformly and independently distributed in the unit square, and whose edges connect any pair of vertices if their distance is below some specified bound. A faulty random geometric network is a random geometric network whose vertices or edges fail at random. Algorithms to find Hamiltonian cycles in faulty random geometric networks are presented.

We consider the problem of partitioning randomly chosen integers between and into two subsets such that the discrepancy, the absolute value of the difference of their sums, is minimized. A partition is called perfect if its discrepancy is when the sum of all integers in the original set is even, or when the sum is odd. Introducing , we prove that the problem undergoes a phase transition at , in the sense that for a.s. there are many perfect partitions, while for a.s. there are no perfect partitions. We also determine a scaling window about the transition point , by showing that the probability of a perfect partition tends to , , or some explicit function , depending on whether tends to , , or , respectively. We prove that in the subcritical phase the number of perfect partitions is normal in the limit. For the scaling window (critical phase) and the supercritical phase we determine the limiting distribution of the (scaled) optimum discrepancy. This appears to be a first case of combinatorial optimization problem for which Derrida's random energy approximation model is proven to be sharp in the limit.

Joint work with Jennifer Chayes and Christian Borgs (Microsoft).

Permutations admitting an -th root

The number of permutations of the symmetric group that admit an -th root is asymptotically equivalent to

The traditional model for tries is to flip a coin whenever a decision has to be made. The new russian model chooses a word of length n (over a two-letter alphabet) for each of the m data at random and uses its bits. In the limit , the classical model resurfaces.

In a joint effort with W. Szpankowski it was possible to compute the average search costs exactly, under several different boundary conditions. The Patricia version and the size of tries can also be successfully handled.

The treatment of digital search trees (under the russian probability model) seems to be a challenge.

Word counting satisfies a Large Deviation Principle. The existence of a generating function allows the derivation of an accurate estimate of the tail distribution. Notably, the parameters in Bahadur & Rao Theorem are explicitely computed. Additionnally, these results allow for a computation of the distribution of a word conditioned by the overrepresentation of an other word. This methodology applies to assess the statistical significance of exceptional words overrepresentation in computational biology. Related algorithmic and complexity issues are discussed and compared to previous results.

This talk is based on some joint work with Ralph Neininger. It is a continuation of his recent paper on the multivariate contraction method. Our main result gives a limit theorem for divide and conquer type recusions under some general assumptions on the asymptotic behaviour of the first two moments. Using several different metrics this allows to vary the necessary assumptions on the recursion and to analyze a great variety of examples,to obtain e.g. also local type of limit results and in particular to obtain normal limits. The method also allows to establish negative results as in the recent paper of Hwang which shows that for m greater than 26 no normalization can make the space of -ary search trees converge.

In 1998, Sundberg and Thistlethwaite obtained in a remarkable paper the growth rate of the number of prime alternating knots and links. These are the first classical objects of knot theory for which enumerative results are available.

In order to obtain the precise asymptotic behavior of this number of prime alternating links, we will journey in the realm of analytic combinatorics, and look for properties of random planar maps. The relation between planar maps (embeddings of graphs in the plane) and knots simply arises from the representation of knots by planar diagrams with an under-overcrossing structure on each vertex.

In the review of some almost sure facts about random planar maps (probabilistic properties and conjectures), we shall pick a few ingredients for our enumerative problem. In particular the map-Airy law discussed last year in the analysis of a random sampling algorithm (Banderier, Flajolet, Schaeffer and Soria) will surface here again.

As pointed out by Zinn-Justin and Zuber, planar diagrams representing knots and links can be also viewed as configurations of a toy model on a random lattice. Techniques of mathematical physics then allow to make conjectures extending Sundberg and Thistlethwaite's result. Indeed physicists have already studied how their classical models (Ising, percolation, spanning trees, etc.) are perturbed by replacing the usual regular lattice by a random planar map (this is called "coupling the model with quantum gravity"...). From the combinatorial point of view, these approaches raise a number of intriguing questions.

(Based on join work with Sebastien Kunz-jacques)

We consider the problem of maintaining a binary search tree BST

that minimizes the average access cost needed to satisfy randomly generated requests. We analyze scenarios in which the accesses are generated according to a vector of fixed probabilities which is unknown.

We devise policies for modifying the tree structure dynamically, using rotations of accessed records. The aim is to produce good approximations of the optimal structure of the tree, while keeping the number of rotations as small as possible. The heuristics that we propose achieve a close approximation to the optimal BST, with lower organization costs than any previously studied.

We introduce the MOVE_ONCE rule. The average access cost to the tree under this rule is shown to equal the value achieved by the common rule Move to the Root (MTR). The advantage of MOVE_ONCE over MTR and similar rules is that it relocates each of the items in the tree at most once. We show that the total expected cost of modifying the tree by the MOVE_ONCE rule is bounded from above by rotations (in a tree with records), where is the th harmonic number. Extensive experiments show that this value is an over-estimate, and in fact the number of rotations is linear for all the access probability vectors we tested. An approximate analysis is shown to match the experimental results, producing the expected number .

Next we combine the MOVE_ONCE

MOVE_ONCE rule with reference counters, one per record, that provide estimates of the reference probabilities. We show that, for any , and sufficiently large , the resulting reorganization rule achieves a cost that approaches the optimum up to an absolute difference of with probability higher than , within a number of accesses that is proportional to .

This is joint work with Micha Hofri.

Recently, the concept of a -histogram has been introduced to perform a combinatorial study of the queue of a slow device (e.g., a printer) attached to a computer. The concept is equivalent to that of "staircase poliominoes", and precisely a -histogram is a sequence of columns (each column composed by cells of the same dimension ) in which the height of the th column is at most , if is the height of column ; furthermore, the first column has height not greater than . In the past, -histograms have been studied by number of columns, and in that respect they have strong connections with -ary tree. Here we wish to study them by area, which seems to be a more difficult problem. A well-known result concerns the case and is due to Odlyzko and Wilf. We use a different approach to count -histograms with a given area. This approach is related to the infinite triangles of histograms counted by the height of their last column. Since these histograms represent the queue stories when the total waiting time of users has been fixed, their study can give useful information in dealing with this sort of slow devices.

Let and be sequences generated over a finite alphabet. We call the pattern and the text. The basic questions we are interested in are:

how many times H occurs in T;

how long one has to wait until H occurs in T.

We consider the pattern matching problem in various settings, namely:

In the string matching problem the pattern is considered to be a string, while in the subsequence matching problem the pattern is a substring.

The pattern can occur exactly or approximately.

In most cases we assume that the text is generated by a random source and the pattern is given. But in the repetitive pattern matching problem the pattern is a part of the random text.

Finally, one may assume that the text is generated among all possible strings. In the restricted pattern matching problem the text satisfies some additional constraints (e.g., in a sequence there is no runs of 's shorter than and longer than ).

In this talk we review analyses of the above mentioned pattern matching problems. We show how to compute moments, limiting distributions and large deviations for the number of pattern occurrences and the waiting time (i.e., the first occurrence of the pattern). Throughout we use combinatorial (e.g., formal calculus) and analytic methods (e.g., generating function, singularity analysis) of analysis of algorithms.

This is a joint work with Y. Guivarch', P. Flajolet and W. Szpankowski.

We consider the sequence comparison problem, also known as hidden pattern (word) problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A characteristic parameter is the number of occurrences of a given pattern  of length as a subsequence in a random text of length generated by a memoryless source. Spacings between letters of the pattern may either be constrained or not in order to define valid occurrences. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law. These results are obtained via combinatorics on words, formal languages techniques, and methods of analytic combinatorics based on generating functions and convergence of moments. The motivation to study this problem comes from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.

We give a precise average-case analysis of Rabin's algorithm for testing the irreducibility of polynomials over finite fields. The main technical contribution of this work is the study of the probability that a random polynomial of degree contains an irreducible factor of degree dividing several maximal divisors of the degree n. We then study the expected value and the variance of the number of operations performed by the algorithm and some of its variants. We present an exact analysis when n is a prime or a product of two primes and an asymptotic analysis for the general case. We also determine the ordering of prime divisors of that minimizes the leading factor.

In this talk we will present and motivate the problem, explain the most important technical aspects of our analysis, and show how our analysis can be generalized to other algorithms that deal with similar divisor conditions.

This is a joint work with Daniel Panario, Boris Pittel and Bruce Richmond.

Rapidly growing functions can be used as a scale for measuring the complexity of certain combinatorial principles like: Friedman's miniaturization of Kruskal's theorem, Friedman's miniaturization of the well-foundedness of the nested multiset ordering, the termination of the hydra and Goodstein processes and Paris' and Harrington's extension of the finite Ramsey theorem. Surprisingly, results from analytical combinatorics (e.g. Otter 1949, Yamashita 1979) can be used for classifying the complexities of these principles in terms of sublinear bounding functions. We give an informal survey on this material and we address some related open problems.