DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science

---

1. Convergence to the coalescent and its relation to the time back to the most recent common ancestor

Martin Möhle.

For the class of haploid exchangeable population models with non-overlapping generations and population size $N$ it is shown that, as $N$ tends to infinity, convergence of the time-scaled ancestral process to Kingman's coalescent and convergence in distribution of the scaled times back to the most recent common ancestor (MRCA) to the corresponding times back to the MRCA of the Kingman coalescent are equivalent. Extensions of this equivalence are derived for exchangeable population models being in the domain of attraction of a coalescent process with multiple collisions. The proofs are based on the property that the total rates of a coalescent with multiple collisions already determine the distribution of the coalescent. It is finally shown that similar results cannot be obtained for the full class of exchangeable coalescents allowing for simultaneous multiple collisions of ancestral lineages, essentially because the total rates do not determine the distribution of a general exchangeable coalescent.

---

2. The size of random fragmentation intervals

Rafik Aguech.

Two processes of random fragmentation of an interval are investigated. For each of them, there is a splitting probability at each step of the fragmentation process whose overall effect is to stabilize the global number of splitting events. More precisely, we consider two models. In the first model, the fragmentation stops which a probability $p$ witch can not depend on the fragment size. The number of stable fragments with sizes less than a given $t \geq 0$, denoted by $K(t)$, is introduced and studied. In the second one the probability to split a fragment of size $x$ is $p(x)=1-e^{-x}$. For this model we utilize the contraction method to show that the distribution of a suitably normalized version of the number of stable fragments converges in law. It's shown that the limit is the fixed-point solution (in the Wasserstein space) to a distributional equation. An explicit solution to the fixed-point equation is easily verified to be Gaussian.

---

3. The Degree Distribution of Thickened Trees

Michael Drmota ; Bernhard Gittenberger ; Alois Panholzer.

We develop a combinatorial structure to serve as model of random real world networks. Starting with plane oriented recursive trees we substitute the nodes by more complex graphs. In such a way we obtain graphs having a global tree-like structure while locally looking clustered. This fits with observations obtained from real-world networks. In particular we show that the resulting graphs are scale-free, that is, the degree distribution has an asymptotic power law.

---

4. The continuous limit of large random planar maps

Jean-François Le Gall.

We discuss scaling limits of random planar maps chosen uniformly over the set of all $2p$-angulations with $n$ faces. This leads to a limiting space called the Brownian map, which is viewed as a random compact metric space. Although we are not able to prove the uniqueness of the distribution of the Brownian map, many of its properties can be investigated in detail. In particular, we obtain a complete description of the geodesics starting from the distinguished point called the root. We give applications to various properties of large random planar maps.

---

5. Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding

Wojciech Szpankowski.

Analytic information theory aims at studying problems of information theory using analytic techniques of computer science and combinatorics. Following Hadamard's precept, these problems are tackled by complex analysis methods such as generating functions, Mellin transform, Fourier series, saddle point method, analytic poissonization and depoissonization, and singularity analysis. This approach lies at the crossroad of computer science and information theory. In this survey we concentrate on one facet of information theory (i.e., source coding better known as data compression), namely the $\textit{redundancy rate}$ problem. The redundancy rate problem determines by how much the actual code length exceeds the optimal code length. We further restrict our interest to the $\textit{average}$ redundancy for $\textit{known}$ sources, that is, when statistics of information sources are known. We present precise analyses of three types of lossless data compression schemes, namely fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and variable-to-variable (VV) length codes. In particular, we investigate average redundancy of Huffman, Tunstall, and Khodak codes. These codes have succinct representations as $\textit{trees}$, either as coding or parsing trees, and we analyze here some of their parameters (e.g., the average path from the root to a leaf).

---

6. Point process stabilization methods and dimension estimation

J. E. Yukich.

We provide an overview of stabilization methods for point processes and apply these methods to deduce a central limit theorem for statistical estimators of dimension.

---

7. Error bounds in stochastic-geometric normal approximation

Mathew Penrose ; Tom Rosoman.

We provide normal approximation error bounds for sums of the form $\sum_x \xi_x$, indexed by the points $x$ of a Poisson process (not necessarily homogeneous) in the unit $d$-cube, with each term $\xi_x$ determined by the configuration of Poisson points near to $x$ in some sense. We consider geometric graphs and coverage processes as examples of our general results.

---

8. Concentration of measure and mixing for Markov chains

Malwina Luczak.

We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution. We illustrate our results with applications to some known chains from computer science and statistical mechanics.

---

9. The height of random binary unlabelled trees

Nicolas Broutin ; Philippe Flajolet.

This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.

---

10. The register function for lattice paths

Guy Louchard ; Helmut Prodinger.

The register function for binary trees is the minimal number of extra registers required to evaluate the tree. This concept is also known as Horton-Strahler numbers. We extend this definition to lattice paths, built from steps $\pm 1$, without positivity restriction. Exact expressions are derived for appropriate generating functions. A procedure is presented how to get asymptotics of all moments, in an almost automatic way; this is based on an earlier paper of the authors.

---

11. Degree distribution in random planar graphs

Michael Drmota ; Omer Gimenez ; Marc Noy.

We prove that for each $k \geq 0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, and moreover that $\sum_k d_k =1$. The proof uses the tools developed by Gimènez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=\sum_k d_k w^k$. From the explicit expression for $p(w)$ we can compute the $d_k$ to any degree of accuracy, and derive asymptotic estimates for large values of $k$.

---

12. Constructions for Clumps Statistics.

Frédérique Bassino ; Julien Clément ; Julien Fayolle ; Pierre Nicodème.

We consider a component of the word statistics known as clump; starting from a finite set of words, clumps are maximal overlapping sets of these occurrences. This object has first been studied by Schbath with the aim of counting the number of occurrences of words in random texts. Later work with similar probabilistic approach used the Chen-Stein approximation for a compound Poisson distribution, where the number of clumps follows a law close to Poisson. Presently there is no combinatorial counterpart to this approach, and we fill the gap here. We also provide a construction for the yet unsolved problem of clumps of an arbitrary finite set of words. In contrast with the probabilistic approach which only provides asymptotic results, the combinatorial method provides exact results that are useful when considering short sequences.

---

13. Distribution of the Number of Encryptions in Revocation Schemes for Stateless Receivers

Christopher Eagle ; Zhicheng Gao ; Mohamed Omar ; Daniel Panario ; Bruce Richmond.

We study the number of encryptions necessary to revoke a set of users in the complete subtree scheme (CST) and the subset-difference scheme (SD). These are well-known tree based broadcast encryption schemes. Park and Blake in: Journal of Discrete Algorithms, vol. 4, 2006, pp. 215―238, give the mean number of encryptions for these schemes. We continue their analysis and show that the limiting distribution of the number of encryptions for these schemes is normal. This implies that the mean numbers of Park and Blake are good estimates for the number of necessary encryptions used by these schemes.

---

14. On square permutations

Enrica Duchi ; Dominique Poulalhon.

Severini and Mansour introduced $\textit{square polygons}$, as graphical representations of $\textit{square permutations}$, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.

---

15. Polynomial tails of additive-type recursions

Eva-Maria Schopp.

Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms. In particular they arise as parameters of divide and conquer type algorithms. We mainly focuss on polynomial tails that arise due to heavy tail bounds of the toll term and the starting distributions. Besides estimating the tail probability directly we use a modified version of a theorem from regular variation theory. This theorem states that upper bounds on the asymptotic tail probability can be derived from upper bounds of the Laplace―Stieltjes transforms near zero.

---

16. Small parts in the Bernoulli sieve

Alexander Gnedin ; Alex Iksanov ; Uwe Roesler.

Sampling from a random discrete distribution induced by a 'stick-breaking' process is considered. Under a moment condition, it is shown that the asymptotics of the sequence of occupancy numbers, and of the small-parts counts (singletons, doubletons, etc) can be read off from a limiting model involving a unit Poisson point process and a self-similar renewal process on the half-line.

---

17. On the number of zero increments of random walks with a barrier

Alex Iksanov ; Pavlo Negadajlov.

Continuing the line of research initiated in Iksanov and Möhle (2008) and Negadajlov (2008) we investigate the asymptotic (as $n \to \infty$) behaviour of $V_n$ the number of zero increments before the absorption in a random walk with the barrier $n$. In particular, when the step of the unrestricted random walk has a finite mean, we prove that the number of zero increments converges in distribution. We also establish a weak law of large numbers for $V_n$ under a regular variation assumption.

---

18. Evaluation of a Special Hankel Determinant of Binomial Coefficients

Ömer Eugeciouglu ; Timothy Redmond ; Charles Ryavec.

This paper makes use of the recently introduced technique of $\gamma$-operators to evaluate the Hankel determinant with binomial coefficient entries $a_k = (3 k)! / (2k)! k!$. We actually evaluate the determinant of a class of polynomials $a_k(x)$ having this binomial coefficient as constant term. The evaluation in the polynomial case is as an almost product, i.e. as a sum of a small number of products. The $\gamma$-operator technique to find the explicit form of the almost product relies on differential-convolution equations and establishes a second order differential equation for the determinant. In addition to $x=0$, product form evaluations for $x = \frac{3}{5}, \frac{3}{4}, \frac{3}{2}, 3$ are also presented. At $x=1$, we obtain another almost product evaluation for the Hankel determinant with $a_k = ( 3 k+1) ! / (2k+1)!k!$.

---

19. Random Records and Cuttings in Split Trees: Extended Abstract

Cecilia Holmgren.

We study the number of records in random split trees on $n$ randomly labelled vertices. Equivalently the number of random cuttings required to eliminate an arbitrary random split tree can be studied. After normalization the distributions are shown to be asymptotically $1$-stable. This work is a generalization of our earlier results for the random binary search tree which is one specific case of split trees. Other important examples of split trees include $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees.

---

20. A variant of the Recoil Growth algorithm to generate multi-polymer systems

Florian Simatos.

The Recoil Growth algorithm, proposed in 1999 by Consta $\textit{et al.}$, is one of the most efficient algorithm available in the literature to sample from a multi-polymer system. Such problems are closely related to the generation of self-avoiding paths. In this paper, we study a variant of the original Recoil Growth algorithm, where we constrain the generation of a new polymer to take place on a specific class of graphs. This makes it possible to make a fine trade-off between computational cost and success rate. We moreover give a simple proof for a lower bound on the irreducibility of this new algorithm, which applies to the original algorithm as well.

---

21. Analysis of an algorithm catching elephants on the Internet

Yousra Chabchoub ; Christine Fricker ; Frédéric Meunier ; Danielle Tibi.

The paper deals with the problem of catching the elephants in the Internet traffic. The aim is to investigate an algorithm proposed by Azzana based on a multistage Bloom filter, with a refreshment mechanism (called $\textit{shift}$ in the present paper), able to treat on-line a huge amount of flows with high traffic variations. An analysis of a simplified model estimates the number of false positives. Limit theorems for the Markov chain that describes the algorithm for large filters are rigorously obtained. The asymptotic behavior of the stochastic model is here deterministic. The limit has a nice formulation in terms of a $M/G/1/C$ queue, which is analytically tractable and which allows to tune the algorithm optimally.

---

22. Generating Functions of Stochastic L-Systems and Application to Models of Plant Development

Cedric Loi ; Paul Henry Cournède.

If the interest of stochastic L-systems for plant growth simulation and visualization is broadly acknowledged, their full mathematical potential has not been taken advantage of. In this article, we show how to link stochastic L-systems to multitype branching processes, in order to characterize the probability distributions and moments of the numbers of organs in plant structure. Plant architectural development can be seen as the combination of two subprocesses driving the bud population dynamics, branching and differentiation. By writing the stochastic L-system associated to each subprocess, we get the generating function associated to the whole system by compounding the associated generating functions. The modelling of stochastic branching is classical, but to model differentiation, we introduce a new framework based on multivariate phase-type random vectors.

---

23. A functional limit law for the profile of plane-oriented recursive trees.

Henning Sulzbach.

We give a functional limit law for the normalized profile of random plane-oriented recursive trees. The proof uses martingale convergence theorems in discrete and continuous-time. This complements results of Hwang (2007).

---

24. Hopcroft's automaton minimization algorithm and Sturmian words

Jean Berstel ; Luc Boasson ; Olivier Carton.

This paper is concerned with the analysis of the worst case behavior of Hopcroft's algorithm for minimizing deterministic finite state automata. We extend a result of Castiglione, Restivo and Sciortino. They show that Hopcroft's algorithm has a worst case behavior for the automata recognizing Fibonacci words. We prove that the same holds for all standard Sturmian words having an ultimately periodic directive sequence (the directive sequence for Fibonacci words is $(1,1,\ldots)$).

---

25. Are even maps on surfaces likely to be bipartite?

Guillaume Chapuy.

It is well known that a planar map is bipartite if and only if all its faces have even degree (what we call an even map). In this paper, we show that rooted even maps of positive genus $g$ chosen uniformly at random are bipartite with probability tending to $4^{−g}$ when their size goes to infinity. Loosely speaking, we show that each of the $2g$ fundamental cycles of the surface of genus $g$ contributes a factor $\frac{1}{2}$ to this probability.We actually do more than that: we obtain the explicit asymptotic behaviour of the number of even maps and bipartite maps of given genus with any finite set of allowed face degrees. This uses a generalisation of the Bouttier-Di Francesco-Guitter bijection to the case of positive genus, a decomposition inspired by previous works of Marcus, Schaeffer and the author, and some involved manipulations of generating series counting paths. A special case of our results implies former conjectures of Gao.

---

26. Branching processes in random environment die slowly

Vladimir Vatutin ; Andreas Kyprianou.

Let $Z_n,n=0,1,\ldots,$ be a branching process evolving in the random environment generated by a sequence of iid generating functions $f_0(s),f_1(s),\ldots,$ and let $S_0=0$, $S_k=X_1+ \ldots +X_k,k \geq 1$, be the associated random walk with $X_i=\log f_{i-1}^{\prime}(1), \tau (m,n)$ be the left-most point of minimum of $\{S_k,k \geq 0 \}$ on the interval $[m,n]$, and $T=\min \{ k:Z_k=0\}$. Assuming that the associated random walk satisfies the Doney condition $P(S_n > 0) \to \rho \in (0,1), n \to \infty$, we prove (under the quenched approach) conditional limit theorems, as $n \to \infty$, for the distribution of $Z_{nt}, Z_{\tau (0,nt)}$, and $Z_{\tau (nt,n)}, t \in (0,1)$, given $T=n$. It is shown that the form of the limit distributions essentially depends on the location of $\tau (0,n)$ with respect to the point $nt$.

---

27. On subcritical multi-type branching process in random environment

Elena Dyakonova.

We investigate a multi-type Galton-Watson process in a random environment generated by a sequence of independent identically distributed random variables. Suppose that the associated random walk constructed by the logarithms of the Perron roots of the reproduction mean matrices has negative mean and assuming some additional conditions, we find the asymptotics of the survival probability at time $n$ as $n \to \infty$.

---

28. Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups

Lorenz A. Gilch.

We consider random walks on the set of all words over a finite alphabet such that in each step only the last two letters of the current word may be modified and only one letter may be adjoined or deleted. We assume that the transition probabilities depend only on the last two letters of the current word. Furthermore, we consider also the special case of random walks on free products by amalgamation of finite groups which arise in a natural way from random walks on the single factors. The aim of this paper is to compute several equivalent formulas for the rate of escape with respect to natural length functions for these random walks using different techniques.

---

29. A Note on the Transience of Critical Branching Random Walks on the Line

Gerold Alsmeyer ; Matthias Meiners.

Gantert and Müller (2006) proved that a critical branching random walk (BRW) on the integer lattice is transient by analyzing this problem within the more general framework of branching Markov chains and making use of Lyapunov functions. The main purpose of this note is to show how the same result can be derived quite elegantly and even extended to the nonlattice case within the theory of weighted branching processes. This is done by an analysis of certain associated random weighted location measures which, upon taking expectations, provide a useful connection to the well established theory of ordinary random walks with i.i.d. increments. A brief discussion of the asymptotic behavior of the left- and rightmost particles in a critical BRW as time goes to infinity is provided in the final section by drawing on recent work by Hu and Shi (2008).

---

30. Subcritical pattern languages for and/or trees

Jakub Kozik.

Let $P_k(f)$ denote the density of and/or trees defining a boolean function $f$ within the set of and/or trees with fixed number of variables $k$. We prove that there exists constant $B_f$ such that $P_k(f) \sim B_f \cdot k^{-L(f)-1}$ when $k \to \infty$, where $L(f)$ denote the complexity of $f$ (i.e. the size of a minimal and/or tree defining $f$). This theorem has been conjectured by Danièle Gardy and Alan Woods together with its counterpart for distribution $\pi$ defined by some critical Galton-Watson process. Methods presented in this paper can be also applied to prove the analogous property for $\pi$.

---

31. On density of truth of the intuitionistic logic in one variable

Zofia Kostrzycka.

In this paper we focus on the intuitionistic propositional logic with one propositional variable. More precisely we consider the standard fragment $\{ \to ,\vee ,\bot \}$ of this logic and compute the proportion of tautologies among all formulas. It turns out that this proportion is different from the analog one in the classical logic case.

---

32. On the density and the structure of the Peirce-like formulae

Antoine Genitrini ; Jakub Kozik ; Grzegorz Matecki.

Within the language of propositional formulae built on implication and a finite number of variables $k$, we analyze the set of formulae which are classical tautologies but not intuitionistic (we call such formulae - Peirce's formulae). We construct the large family of so called simple Peirce's formulae, whose sequence of densities for different $k$ is asymptotically equivalent to the sequence $\frac{1}{ 2 k^2}$. We prove that the densities of the sets of remaining Peirce's formulae are asymptotically bounded from above by $\frac{c}{ k^3}$ for some constant $c \in \mathbb{R}$. The result justifies the statement that in the considered language almost all Peirce's formulae are simple. The result gives a partial answer to the question stated in the recent paper by H. Fournier, D. Gardy, A. Genitrini and M. Zaionc - although we have not proved the existence of the densities for Peirce's formulae, our result gives lower and upper bound for it (if it exists) and both bounds are asymptotically equivalent to $\frac{1}{ 2 k^2}$.

---

33. Boltzmann Oracle for Combinatorial Systems

Carine Pivoteau ; Bruno Salvy ; Michèle Soria.

Boltzmann random generation applies to well-defined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.

---

34. A note on the fragmentation of a stable tree

Philippe Marchal.

We introduce a recursive algorithm generating random trees, which we identify as skeletons of a continuous, stable tree. We deduce a representation of a fragmentation process on these trees.

---

35. A Markov Chain Algorithm for determining Crossing Times through nested Graphs

Uta Freiberg ; Christoph Thäle.

According to the by now established theory developed in order to define a Laplacian or ― equivalently ― a Brownian motion on a nested fractal, one has to solve certain renormalization problems. In this paper, we present a Markov chain algorithm solving the problem for certain classes of simple fractals $K$ provided that there exists a unique Brownian motion and hence, a unique Laplacian on $K$.

---

36. Volume Laws for Boxed Plane Partitions and Area Laws for Ferrers Diagrams

Uwe Schwerdtfeger.

We asymptotically analyse the volume random variables of general, symmetric and cyclically symmetric plane partitions fitting inside a box. We consider the respective symmetry class equipped with the uniform distribution. We also prove area limit laws for two ensembles of Ferrers diagrams. Most limit laws are Gaussian.

---

37. Plane recursive trees, Stirling permutations and an urn model

Svante Janson.

We exploit a bijection between plane recursive trees and Stirling permutations; this yields the equivalence of some results previously proven separately by different methods for the two types of objects as well as some new results. We also prove results on the joint distribution of the numbers of ascents, descents and plateaux in a random Stirling permutation. The proof uses an interesting generalized Pólya urn.

---

38. Analytic Combinatorics of the Mabinogion Urn

Philippe Flajolet ; Thierry Huillet.

The Mabinogion urn is a simple model of the spread of influences amongst versatile populations. It corresponds to a non-standard urn with balls of two colours: each time a ball is drawn, it causes a ball of the other kind to switch its colour. The process stops once unanimity has been reached. This note provides analytic expressions describing the evolution of the Mabinogion urn, based on a time-reversal transformation applied to the classical Ehrenfest urn. Consequences include a precise asymptotic analysis of the stopping-time distribution―it is asymptotically normal in the "unfair'' case and akin to an extreme-value (double exponential) distribution in the "fair'' case―as well as a characterization of the exponentially small probability of reversing a majority.

---