DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

---

1. Geometric Bucket Trees: Analysis of Linear Bucket Tree

Philippe Jacquet ; Paul Muhlethaler.

We analyse the average number of buckets in a Linear Bucket tree created by $n$ points uniformly dispatched on an interval of length $y$. A new bucket is created when a point does not fall in an existing bucket. The bucket is the interval of length 2 centered on the point. We illustrate this concept by an interesting tale of how the moon's surface took on its present form. Thanks to an explicit Laplace transform of the Poissonized sequence, and the use of dePoissonization tools, we obtain the explicit asymptotic expansions of the average number of buckets in most of the asymptotic regimes relative to $n$ and $y$.

---

2. Renewal theory in analysis of tries and strings: Extended abstract

Svante Janson.

We give a survey of a number of simple applications of renewal theory to problems on random strings, in particular to tries and Khodak and Tunstall codes.

---

3. The maximum of Brownian motion with parabolic drift (Extended abstract)

Svante Janson ; Guy Louchard ; Anders Martin-Löf.

We study the maximum of a Brownian motion with a parabolic drift; this is a random variable that often occurs as a limit of the maximum of discrete processes whose expectations have a maximum at an interior point. This has some applications in algorithmic and data structures analysis. We give series expansions and integral formulas for the distribution and the first two moments, together with numerical values to high precision.

---

4. Dynamic Threshold Strategy for Universal Best Choice Problem

Jakub Kozik.

We propose a new strategy for universal best choice problem for partially ordered sets. We present its partial analysis which is sufficient to prove that the probability of success with this strategy is asymptotically strictly greater than 1/4, which is the value of the best universal strategy known so far.

---

5. Counting Markov Types

Philippe Jacquet ; Charles Knessl ; Wojciech Szpankowski.

The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so called $\textit{balanced frequency matrix}$ that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length $n$ over an alphabet of size $m$. This turns out to coincide with the number of the balanced frequency matrices as well as with the number of special $\textit{linear diophantine equations}$, and also balanced directed multigraphs. For fixed $m$ we prove that the number of Markov types is asymptotically equal to $d(m) \frac{n^{m^{2-m}}}{(m^2-m)!}$, where $d(m)$ is a constant for which we give an integral representation. For $m \to \infty$ we conclude that asymptotically the number of types is equivalent to $\frac{\sqrt{2}m^{3m/2} e^{m^2}}{m^{2m^2} 2^m \pi^{m/2}} n^{m^2-m}$ provided that $m=o(n^{1/4})$ (however, our techniques work for $m=o(\sqrt{n})$). These findings are derived by analytical techniques ranging from multidimensional generating functions to the saddle point method.

---

6. The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth

Carlos Hoppen.

The analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. In this paper, we show that similar ideas may be used to obtain deterministic bounds for one such parameter in the case of regular graphs with large girth. More precisely, we address the problem of finding a large induced forest in a graph $G$, by which we mean an acyclic induced subgraph of $G$ with a lot of vertices. For a fixed integer $r \geq 3$, we obtain new lower bounds on the size of a maximum induced forest in graphs with maximum degree $r$ and large girth. These bounds are derived from the solution of a system of differential equations that arises naturally in the analysis of an iterative probabilistic procedure to generate an induced forest in a graph. Numerical approximations suggest that these bounds improve substantially the best previous bounds. Moreover, they improve previous asymptotic lower bounds on the size of a maximum induced forest in a random regular graph.

---

7. The Bernoulli sieve: an overview

Alexander Gnedin ; Alexander Iksanov ; Alexander Marynych.

The Bernoulli sieve is a version of the classical balls-in-boxes occupancy scheme, in which random frequencies of infinitely many boxes are produced by a multiplicative random walk, also known as the residual allocation model or stick-breaking. We give an overview of the limit theorems concerning the number of boxes occupied by some balls out of the first $n$ balls thrown, and present some new results concerning the number of empty boxes within the occupancy range.

---

8. Phase transitions in Proof Theory

Lev Gordeev ; Andreas Weiermann.

Using standard methods of analytic combinatorics we elaborate critical points (thresholds) of phase transitions from provability to unprovability of arithmetical well-partial-ordering assertions in several familiar theories occurring in the reverse mathematics program.

---

9. Random Generation Using Binomial Approximations

Dominique Gouyou-Beauchamps ; Cyril Nicaud.

Generalizing an idea used by Alonso to generate uniformly at random Motzkin words, we outline an approach to build efficient random generators using binomial distributions and rejection algorithms. As an application of this method, we present random generators, both efficient and easy to implement, for partial injections and colored unary-binary trees.

---

10. The degree distribution in unlabelled $2$-connected graph families

Veronika Kraus.

We study the random variable $X_n^k$, counting the number of vertices of degree $k$ in a randomly chosen $2$-connected graph of given families. We prove a central limit theorem for $X_n^k$ with expected value $\mathbb{E}X_n^k \sim \mu_kn$ and variance $\mathbb{V}X_n^k \sim \sigma_k^2n$, both asymptotically linear in $n$, for both rooted and unrooted unlabelled $2$-connected outerplanar or series-parallel graphs.

---

11. A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems

Cedric Loi ; Paul-Henry Cournède ; Jean Françon.

The analysis of pattern occurrences has numerous applications, in particular in biology. In this article, a symbolic method is proposed to compute the distribution associated to the number of occurences of a specific pattern in a random text generated by a stochastic 0L-system. To that purpose, a semiring structure is set for combinatorial classes composed of weighted words. This algebraic structure relies on new union and concatenation operators which, under some assumptions, are admissible constructions. Decomposing the combinatorial classes of interest by using these binary operators enables the direct translation of specifications into a set of functional equations relating generating functions thanks to transformation rules. The article ends with two examples. The first one deals with unary patterns and the connection with multitype branching process is established. The second one is about a pattern composed of two letters and underlines the importance of writing a proper specification.

---

12. Almost sure asymptotics for the random binary search tree

Matthew Roberts.

We consider a (random permutation model) binary search tree with $n$ nodes and give asymptotics on the $\log$ $\log$ scale for the height $H_n$ and saturation level $h_n$ of the tree as $n \to \infty$, both almost surely and in probability. We then consider the number $F_n$ of particles at level $H_n$ at time $n$, and show that $F_n$ is unbounded almost surely.

---

13. On unary nodes in tries

Stephan Wagner.

The difference between ordinary tries and Patricia tries lies in the fact that all unary nodes are removed in the latter. Their average number is thus easily determined from earlier results on the size of tries/Patricia tries. In a well-known contention resolution algorithm, whose probabilistic model is essentially equivalent to tries, unary nodes correspond to repetitions, i.e., steps in the algorithm that do not resolve anything at all. In this paper, we take an individual's view on such repetitions: we consider the distribution of the number of repetitions a certain contender encounters in the course of the algorithm―-which is equivalent to the number of unary nodes on the path from the root to a random string in a trie. We encounter an example of a sequence of distributions that does not actually converge to a limit distribution, but rather oscillates around a (discrete) limit distribution.

---

14. Asymptotic Rational Approximation To Pi: Solution of an "Unsolved Problem'' Posed By Herbert Wilf

Mark Daniel Ward.

The webpage of Herbert Wilf describes eight Unsolved Problems. Here, we completely resolve the third of these eight problems. The task seems innocent: find the first term of the asymptotic behavior of the coefficients of an ordinary generating function, whose coefficients naturally yield rational approximations to $\pi$. Upon closer examination, however, the analysis is fraught with difficulties. For instance, the function is the composition of three functions, but the innermost function has a non-zero constant term, so many standard techniques for analyzing function compositions will completely fail. Additionally, the signs of the coefficients are neither all positive, nor alternating in a regular manner. The generating function involves both a square root and an arctangent. The complex-valued square root and arctangent functions each rely on complex logarithms, which are multivalued and fundamentally depend on branch cuts. These multiple values and branch cuts make the function extremely tedious to visualize using Maple. We provide a complete asymptotic analysis of the coefficients of Wilf's generating function. The asymptotic expansion is naturally additive (not multiplicative); each term of the expansion contains oscillations, which we precisely characterize. The proofs rely on complex analysis, in particular, singularity analysis (which, in turn, rely on a Hankel contour and transfer theorems).

---

15. Ordered increasing $k$-trees: Introduction and analysis of a preferential attachment network model

Alois Panholzer ; Georg Seitz.

We introduce a random graph model based on $k$-trees, which can be generated by applying a probabilistic preferential attachment rule, but which also has a simple combinatorial description. We carry out a precise distributional analysis of important parameters for the network model such as the degree, the local clustering coefficient and the number of descendants of the nodes and root-to-node distances. We do not only obtain results for random nodes, but in particular we also get a precise description of the behaviour of parameters for the $j$-th inserted node in a random $k$-tree of size $n$, where $j=j(n)$ might grow with $n$. The approach presented is not restricted to this specific $k$-tree model, but can also be applied to other evolving $k$-tree models.

---

16. The total Steiner $k$-distance for $b$-ary recursive trees and linear recursive trees

Götz Olaf Munsonius.

We prove a limit theorem for the total Steiner $k$-distance of a random $b$-ary recursive tree with weighted edges. The total Steiner $k$-distance is the sum of all Steiner $k$-distances in a tree and it generalises the Wiener index. The limit theorem is obtained by using a limit theorem in the general setting of the contraction method. In order to use the contraction method we prove a recursion formula and determine the asymptotic expansion of the expectation using the so-called Master Theorem by Roura (2001). In a second step we prove a transformation of the total Steiner $k$-distance of $b$-ary trees with weighted edges to arbitrary recursive trees. This transformation yields the limit theorem for the total Steiner $k$-distance of the linear recursive trees when the parameter of these trees is a non-negative integer.

---

17. An optimal cardinality estimation algorithm based on order statistics and its full analysis

Jérémie Lumbroso.

Building on the ideas of Flajolet and Martin (1985), Alon et al. (1987), Bar-Yossef et al. (2002), Giroire (2005), we develop a new algorithm for cardinality estimation, based on order statistics which, according to Chassaing and Gerin (2006), is optimal among similar algorithms. This algorithm has a remarkably simple analysis that allows us to take its $\textit{fine-tuning}$ and the $\textit{characterization of its properties}$ further than has been done until now. We prove that, asymptotically, it is $\textit{strictly unbiased}$ (contrarily to Probabilistic Counting, Loglog, Hyperloglog), we verify that its relative precision is about $1/\sqrt{m-2}$ when $m$ words of storage are used, and we fully characterize the limit law of the estimates it provides, in terms of gamma distribution―-this is the first such algorithm for which the limit law has been established. We also develop a Poisson analysis for the pre-asymptotic regime. In this way, we are able to devise a complete algorithm, covering all cardinalities ranges from $0$ to very large.

---

18. Partial Quicksort and Quickpartitionsort

Conrado Martínez ; Uwe Rösler.

Partial Quicksort sorts the $l$ smallest elements in a list of length $n$. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time $c_1l\ln l+c_2l+n+o(n)$. The constant $c_1$ can be as small as the information theoretic lower bound $\log_2 e$.

---

19. Square root singularities of infinite systems of functional equations

Johannes F. Morgenbesser.

Infinite systems of equations appear naturally in combinatorial counting problems. Formally, we consider functional equations of the form $\mathbf{y} (x)=F(x,\mathbf{y} (x))$, where $F(x,\mathbf{y} ):\mathbb{C} \times \ell^p \to \ell^p$ is a positive and nonlinear function, and analyze the behavior of the solution $\mathbf{y} (x)$ at the boundary of the domain of convergence. In contrast to the finite dimensional case different types of singularities are possible. We show that if the Jacobian operator of the function $F$ is compact, then the occurring singularities are of square root type, as it is in the finite dimensional setting. This leads to asymptotic expansions of the Taylor coefficients of $\mathbf{y} (x)$.

---

20. Random sampling of lattice paths with constraints, via transportation

Lucas Gerin.

We build and analyze in this paper Markov chains for the random sampling of some one-dimensional lattice paths with constraints, for various constraints. These chains are easy to implement, and sample an "almost" uniform path of length $n$ in $n^{3+\epsilon}$ steps. This bound makes use of a certain $\textit{contraction property}$ of the Markov chain, and is proved with an approach inspired by optimal transport.

---

21. No Shannon effect on probability distributions on Boolean functions induced by random expressions

Antoine Genitrini ; Bernhard Gittenberger.

The Shannon effect states that "almost all'' Boolean functions have a complexity close to the maximal possible for the uniform probability distribution. In this paper we use some probability distributions on functions, induced by random expressions, and prove that this model does not exhibit the Shannon effect.

---

22. Analyzing a Weighted Digital Sum Variant

Y. K. Cheung ; Mordecai Golin.

Consider the following weighted digital sum (WDS) variant: write integer $n$ as $n=2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}$ with $i_1 > i_2 > \cdots > i_k \geq 0$ and set $W_M(n) := \sum_{t=1}^k t^M 2^{i_t}$. This type of weighted digital sum arises (when $M=1$) in the analysis of bottom-up mergesort but is not "smooth'' enough to permit a clean analysis. We therefore analyze its average $TW_M(n) := \frac{1}{n}\sum_{j \gt n} W_M(j)$. We show that $TW_M(n)$ has a solution of the form $n G_M(\lg n) + d_M \lg ^M n + \sum\limits_{d=0}^{M-1}(\lg ^d n)G_{M,d}(\lg n)$, where $d_M$ is a constant and $G_M(u), G_{M,d}(u)$'s are periodic functions with period one (given by absolutely convergent Fourier series).

---

23. A Note on Invariant Random Variables

Jacek Cichoń ; Marek Klonowski.

In this paper we present a simple theory, based on the notion of group action on a set, which explains why processes of throwing random sets of points and throwing random lines are similar up to the second moment of counting functions connected with them. We also discuss other applications of this method and show how to calculate higher moments using the group acting on a set.

---

24. The number of Euler tours of a random $d$-in/$d$-out graph

Páidí Creed ; Mary Cryan.

In this paper we obtain the expectation and variance of the number of Euler tours of a random $d$-in/$d$-out directed graph, for $d \geq 2$. We use this to obtain the asymptotic distribution and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every $d$-in/$d$-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of a $d$-in/$d$-out graph is the product of the number of arborescences and the term $[(d-1)!]^n/n$. Therefore most of our effort is towards estimating the asymptotic distribution of the number of arborescences of a random $d$-in/$d$-out graph.

---

25. The height of scaled attachment random recursive trees

Luc Devroye ; Omar Fawzi ; Nicolas Fraiman.

We study depth properties of a general class of random recursive trees where each node $n$ attaches to the random node $\lfloor nX_n \rfloor$ and $X_0, \ldots , X_n$ is a sequence of i.i.d. random variables taking values in $[0,1)$. We call such trees scaled attachment random recursive trees (SARRT). We prove that the height $H_n$ of a SARRT is asymptotically given by $H_n \sim \alpha_{\max} \log n$ where $\alpha_{\max}$ is a constant depending only on the distribution of $X_0$ whenever $X_0$ has a bounded density. This gives a new elementary proof for the height of uniform random recursive trees $H_n \sim e \log n$ that does not use branching random walks.

---

26. Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient

Stephen Chestnut ; Manuel E. Lladser.

We state and prove new properties about Doeblin's ergodicity coefficient for finite Markov chains. We show that this coefficient satisfies a sub-multiplicative type inequality (analogous to the Markov-Dobrushin's ergodicity coefficient), and provide a novel but elementary proof of Doeblin's characterization of weak-ergodicity for non-homogeneous chains. Using Doeblin's coefficient, we illustrate how to approximate a homogeneous but possibly non-stationary Markov chain of duration $n$ by independent and short-lived realizations of an auxiliary chain of duration of order $\ln (n)$. This leads to approximations of occupancy distributions in homogeneous chains, which may be particularly useful when exact calculations via one-step methods or transfer matrices are impractical, and when asymptotic approximations may not be yet reliable. Our findings may find applications to pattern problems in Markovian and non-Markovian sequences that are treatable via embedding techniques.

---

27. On the diameter of random planar graphs

Guillaume Chapuy ; Eric Fusy ; Omer Gimenez ; Marc Noy.

We show that the diameter $D(G_n)$ of a random (unembedded) labelled connected planar graph with $n$ vertices is asymptotically almost surely of order $n^{1/4}$, in the sense that there exists a constant $c>0$ such that $P(D(G_n) \in (n^{1/4-\epsilon} ,n^{1/4+\epsilon})) \geq 1-\exp (-n^{c\epsilon})$ for $\epsilon$ small enough and $n$ large enough $(n \geq n_0(\epsilon))$. We prove similar statements for rooted $2$-connected and $3$-connected embedded (maps) and unembedded planar graphs.

---

28. Stochastic Analysis of the $k$-Server Problem on the Circle

Aris Anagnostopoulos ; Clément Dombry ; Nadine Guillotin-Plantard ; Ioannis Kontoyiannis ; Eli Upfal.

We consider a stochastic version of the $k$-server problem in which $k$ servers move on a circle to satisfy stochastically generated requests. The requests are independent and identically distributed according to an arbitrary distribution on a circle, which is either discrete or continuous. The cost of serving a request is the distance that a server needs to move to reach the request. The goal is to minimize the steady-state expected cost induced by the requests. We study the performance of a greedy strategy, focusing, in particular, on its convergence properties and the interplay between the discrete and continuous versions of the process.

---

29. Bounded discrete walks

C. Banderier ; P. Nicodème.

This article tackles the enumeration and asymptotics of directed lattice paths (that are isomorphic to unidimensional paths) of bounded height (walks below one wall, or between two walls, for $\textit{any}$ finite set of jumps). Thus, for any lattice paths, we give the generating functions of bridges ("discrete'' Brownian bridges) and reflected bridges ("discrete'' reflected Brownian bridges) of a given height. It is a new success of the "kernel method'' that the generating functions of such walks have some nice expressions as symmetric functions in terms of the roots of the kernel. These formulae also lead to fast algorithms for computing the $n$-th Taylor coefficients of the corresponding generating functions. For a large class of walks, we give the discrete distribution of the height of bridges, and show the convergence to a Rayleigh limit law. For the family of walks consisting of a $-1$ jump and many positive jumps, we give more precise bounds for the speed of convergence. We end our article with a heuristic application to bioinformatics that has a high speed-up relative to previous work.

---

30. Multi-dimensional Boltzmann Sampling of Languages

Olivier Bodini ; Yann Ponty.

We address the uniform random generation of words from a context-free language (over an alphabet of size $k$), while constraining every letter to a targeted frequency of occurrence. Our approach consists in a multidimensional extension of Boltzmann samplers. We show that, under mostly $\textit{strong-connectivity}$ hypotheses, our samplers return a word of size in $[(1- \epsilon)n, (1+ \epsilon)n]$ and exact frequency in $\mathcal{O}(n^{1+k/2})$ expected time. Moreover, if we accept tolerance intervals of width in $\Omega (\sqrt{n})$ for the number of occurrences of each letters, our samplers perform an approximate-size generation of words in expected $\mathcal{O}(n)$ time. We illustrate our approach on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.

---

31. Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer length

Bergfinnur Durhuus ; Søren Eilers.

We consider pyramids made of one-dimensional pieces of fixed integer length $a$ and which may have pairwise overlaps of integer length from $1$ to $a$. We give a combinatorial proof that the number of pyramids of size $m$, i.e., consisting of $m$ pieces, equals $\binom{am-1}{m-1}$ for each $a \geq 2$. This generalises a well known result for $a=2$. A bijective correspondence between so-called right (or left) pyramids and $a$-ary trees is pointed out, and it is shown that asymptotically the average width of pyramids equals $\sqrt{\frac{\pi}{2} a(a-1)m}$.

---

32. Induced acyclic subgraphs in random digraphs: Improved bounds

Kunal Dutta ; C. R. Subramanian.

Given a simple directed graph $D = (V,A)$, let the size of the largest induced directed acyclic graph $\textit{(dag)}$ be denoted by $mas(D)$. Let $D \in \mathcal{D}(n,p)$ be a $\textit{random}$ instance, obtained by choosing each of the $\binom{n}{2}$ possible undirected edges independently with probability $2p$ and then orienting each chosen edge independently in one of two possible directions with probabibility $1/2$. We obtain improved bounds on the range of concentration, upper and lower bounds of $mas(D)$. Our main result is that $mas(D) \geq \lfloor 2\log_q np - X \rfloor$ where $q = (1-p)^{-1}, X=W$ if $p \geq n^{-1/3+\epsilon}$ ($\epsilon > 0$ is any constant), $X=W/(\ln q)$ if $p \geq n^{-1/2}(\ln n)^2$, and $W$ is a suitably large constant. where we have an $O(\ln \ln np/\ln q)$ term instead of $W$. This improves the previously known lower bound with an $O(\ln \ln np/\ln q)$ term instead of $W$. We also obtain a slight improvement on the upper bound, using an upper bound on the number of acyclic orientations of an undirected graph. We also analyze a polynomial-time heuristic to find a large induced dag and show that it produces a solution whose size is at least $\log _q np + \Theta (\sqrt{\log_q np})$.

---

33. The variance for partial match retrievals in $k$-dimensional bucket digital trees

Michael Fuchs.

The variance of partial match queries in $k$-dimensional tries was investigated in a couple of papers in the mid-nineties, the resulting analysis being long and complicated. In this paper, we are going to re-derive these results with a much easier approach. Moreover, our approach works for $k$-dimensional PATRICIA tries, $k$-dimensional digital search trees and bucket versions as well.

---

34. The distribution of the number of small cuts in a random planar triangulation

Zhicheng Gao ; Gilles Schaeffer.

We enumerate rooted 3-connected (2-connected) planar triangulations with respect to the vertices and 3-cuts (2-cuts). Consequently, we show that the distribution of the number of 3-cuts in a random rooted 3-connected planar triangulation with $n+3$ vertices is asymptotically normal with mean $(10/27)n$ and variance $(320/729)n$, and the distribution of the number of 2-cuts in a random 2-connected planar triangulation with $n+2$ vertices is asymptotically normal with mean $(8/27)n$ and variance $(152/729)n$. We also show that the distribution of the number of 3-connected components in a random 2-connected triangulation with $n+2$ vertices is asymptotically normal with mean $n/3$ and variance $\frac{8}{ 27}n$ .

---

35. Asymptotics of Decomposable Combinatorial Structures of Alg-Log Type With Positive Log Exponent

Zhicheng Gao ; David Laferrière ; Daniel Panario.

We consider the multiset construction of decomposable structures with component generating function $C(z)$ of alg-log type, $\textit{i.e.}$, $C(z) = (1-z)^{-\alpha} (\log \frac{1}{ 1-z})^{\beta}$. We provide asymptotic results for the number of labeled objects of size $n$ in the case when $\alpha$ is positive and $\beta$ is positive and in the case $\alpha = 0$ and $\beta \geq 2$. The case $0<-\alpha <1$ and any $\beta$ and the case $\alpha > 0$ and $\beta = 0$ have been treated in previous papers. Our results extend previous work of Wright.

---

36. Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Philippe Flajolet ; Mathieu Roux ; Brigitte Vallée.

Digital trees, also known as $\textit{"tries''}$, are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the $\textit{memoryless source}$, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous $\textit{Dirichlet series}$. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific $\textit{arithmetic properties}$, especially irrationality measures, of the sources under consideration.

---

37. Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort (Extended Abstract)

james Allen fill.

Most previous studies of the sorting algorithm $\mathtt{QuickSort}$ have used the number of key comparisons as a measure of the cost of executing the algorithm. Here we suppose that the $n$ independent and identically distributed (iid) keys are each represented as a sequence of symbols from a probabilistic source and that $\mathtt{QuickSort}$ operates on individual symbols, and we measure the execution cost as the number of symbol comparisons. Assuming only a mild "tameness'' condition on the source, we show that there is a limiting distribution for the number of symbol comparisons after normalization: first centering by the mean and then dividing by $n$. Additionally, under a condition that grows more restrictive as $p$ increases, we have convergence of moments of orders $p$ and smaller. In particular, we have convergence in distribution and convergence of moments of every order whenever the source is memoryless, i.e., whenever each key is generated as an infinite string of iid symbols. This is somewhat surprising: Even for the classical model that each key is an iid string of unbiased ("fair'') bits, the mean exhibits periodic fluctuations of order $n$.

---

38. Asymptotics for Walks in a Weyl chamber of Type $B$ (extended abstract)

Thomas Feierl.

We consider lattice walks in $\mathbb{R}^k$ confined to the region $0 < x_1 < x_2 \ldots < x_k$ with fixed (but arbitrary) starting and end points. The walks are required to be "reflectable", that is, we assume that the number of paths can be counted using the reflection principle. The main result is an asymptotic formula for the total number of walks of length $n$ with fixed but arbitrary starting and end point for a general class of walks as the number $n$ of steps tends to infinity. As applications, we find the asymptotics for the number of $k$-non-crossing tangled diagrams on the set $\{1,2, \ldots,n\}$ as $n$ tends to infinity, and asymptotics for the number of $k$-vicious walkers subject to a wall restriction in the random turns model as well as in the lock step model. Asymptotics for all of these objects were either known only for certain special cases, or have only been partially determined.

---

39. Finding hidden cliques in linear time

Uriel Feige ; Dorit Ron.

In the hidden clique problem, one needs to find the maximum clique in an $n$-vertex graph that has a clique of size $k$ but is otherwise random. An algorithm of Alon, Krivelevich and Sudakov that is based on spectral techniques is known to solve this problem (with high probability over the random choice of input graph) when $k \geq c \sqrt{n}$ for a sufficiently large constant $c$. In this manuscript we present a new algorithm for finding hidden cliques. It too provably works when $k > c \sqrt{n}$ for a sufficiently large constant $c$. However, our algorithm has the advantage of being much simpler (no use of spectral techniques), running faster (linear time), and experiments show that the leading constant $c$ is smaller than in the spectral approach. We also present linear time algorithms that experimentally find even smaller hidden cliques, though it remains open whether any of these algorithms finds hidden cliques of size $o(\sqrt{n})$.

---

40. Stochastic Flips on Dimer Tilings

Thomas Fernique ; Damien Regnault.

This paper introduces a Markov process inspired by the problem of quasicrystal growth. It acts over dimer tilings of the triangular grid by randomly performing local transformations, called $\textit{flips}$, which do not increase the number of identical adjacent tiles (this number can be thought as the tiling energy). Fixed-points of such a process play the role of quasicrystals. We are here interested in the worst-case expected number of flips to converge towards a fixed-point. Numerical experiments suggest a $\Theta (n^2)$ bound, where $n$ is the number of tiles of the tiling. We prove a $O(n^{2.5})$ upper bound and discuss the gap between this bound and the previous one. We also briefly discuss the average-case.

---

41. Cover time of a random graph with given degree sequence

Mohammed Abdullah ; Colin Cooper ; Alan Frieze.

In this paper we establish the cover time of a random graph $G(\textbf{d})$ chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}$. We show that under certain restrictions on $\textbf{d}$, the cover time of $G(\textbf{d})$ is with high probability asymptotic to $\frac{d-1}{ d-2} \frac{\theta}{ d}n \log n$. Here $\theta$ is the average degree and $d$ is the $\textit{effective minimum degree}$. The effective minimum degree is the first entry in the sorted degree sequence which occurs order $n$ times.

---