Discrete differential equations of order k are of the form R(z,u,F(z,u),Δ F(z,u),…,Δ^kF(z,u)) = 0, where Δ F(z,u) = (F(z,u)-F(z,0))/u and Δ^k F(z,u) = Δ(Δ^{k-1} F(z,u)) for k ≥ 2. Such equations appear most prominently in planar map enumeration but also in several other contexts such as statistical mechanics, lattice path enumeration, pattern avoiding permutations or stack-sortable permutations. Mostly, one is interested in the function F(z,0) that is usually the corresponding counting generating function. In this work, we consider discrete differential equations with an additional parameter x, where the order of the equation is 1 for x = 1 but k > 1 for x ≠ 1. We call such equations singularly perturbed. The solution theory of higher order discrete differential equations is much more involved than for degree 1 and it is a priori not clear that there is a smooth transition from x = 1 to x ≠ 1. The main contribution of this work is to show that there is actually a smooth transition under certain natural assumptions. As an application of this result we consider pattern counts in triangular planar maps and derive a central limit theorem for these counts.

The composition ℱ∘𝒢 of two combinatorial classes ℱ and 𝒢 is a standard combinatorial construction and translates into the composition F(G(z)) of their corresponding counting generating functions. Such a composition is called critical if G(ρ_G) = ρ_F, where ρ_F and ρ_G denote the corresponding radii of convergence of F and G, respectively. In this case, both the singular behaviours of F and G influence that of F∘G. Such critical composition schemes arise frequently in map enumeration. For example, by using the block-decomposition, one has M(z) = B (z(1+M(z))²) and ρ_B = ρ_M (1+M(ρ_M))², where M(z) denotes the generating function of all rooted planar maps and B(y) the generating functions of 2-connected rooted planar maps. This can be extended to multivariate generating functions by taking several statistics into account, for example face counts. Since critical composition schemes exhibit (usually) a condensation phenomenon - in the above situation this means that there is a giant 2-connected block of linear size and linearly many small blocks - it is very plausible that statistical properties on 2-connected maps transfer to corresponding properties of all maps and back. The purpose of the present paper is to make this precise at the level of the singular structure of the corresponding multivariate generating functions. In particular, we show that moving 3/2-singularities transfer. Since such singularities are closely related to central limit theorems of the corresponding statistics, this method also provides a kind of transfer of central limit theorems. Actually, this method is quite flexible and is applied to a variety of face and pattern counting statistics in map enumeration.

In this paper we prove a quantiative local limit theorem for the distribution of the number of triangles in the Erdős-Renyi random graph $G(n,p)$, for a fixed $p\in (0,1)$. This proof is an extension of the previous work of Gilmer and Kopparty, who proved that the local limit theorem held asymptotically for triangles. Our work gives bounds on the $\ell^1$ and $\ell^\infty$ distance of the triangle distribution from a suitable discrete normal.

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss overTrounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts withunbounded d-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce aregularizedversion of the average (fixed design) minimax regret by imposing asoft constrainton the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide aprecisecharacterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike thed/2 logTregret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)dlogTwhen the regularization parameter is of order Θ(T−α) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.

In online learning, a learner receives data in rounds 1$t T$and at each round predicts a label which is then compared to the true label resulting in a loss. The total loss over$T$rounds, when compared to a loss over the best expert from a class of experts, is called the regret. This paper focuses on logarithmic loss over a class of experts represented by a probability distribution$p$and parameterized by addimensional weight vector w. Unlike previous work that studied bounded weights, we assume that the norm of the weights can be unbounded. This unboundedness poses a challenging problem that leads to unexpected results. For such a class of weighted experts we analyze the (fixed design) minimax regret for the best predictor and worst label sequence. Such a minimax regret turns out to be a universal lower bound for most regrets analyzed in the literature. For bounded weights it is known that the minimax regret can grow like where$R$is an upper bound on the weight norm. In contrast, we show in this paper that for unbounded norm with$R$the minimax regret is asymptotically (d - 1) for a logistic-like expert class which we also extend to$R$We prove our findings by introducing the so called splittable label sequences that partition the weight space into regions with maximum sequence probability equal to 1. Finally, for a general class of monotone experts we present an upper bound 2d log$T$for the regret.

The main goal of this paper is to determine the asymptotic behavior of the number X_n of cut-vertices in random planar maps with n edges. It is shown that X_n/n → c in probability (for some explicit c>0). For so-called subcritial subclasses of planar maps like outerplanar maps we obtain a central limit theorem, too.

We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.

The purpose of this paper is to provide a central limit theorem for the number of occurrences of double triangles in random planar maps. This is the first result of this kind that goes beyond face counts of given valency. The method is based on generating functions, an involved combinatorial decomposition scheme that leads to a system of catalytic functional equations and an analytic extension of the Quadratic Method to systems of equations.

For a nonnegative integer $t$, let $c_t$ be the asymptotic density of natural numbers $n$ for which $s(n+t)\geq s(n)$, where $s(n)$ denotes the sum of digits of $n$ in base $2$. We prove that $c_t>1/2$ for $t$ in a set of asymptotic density $1$, thus giving a partial solution to a conjecture of Cusick stating that $c_t > 1/2$ for all $t$. Interestingly, this problem has several equivalent formulations, for example that the polynomial $X(X+1)\cdots (X+t-1)$ has less than $2^t$ zeros modulo $2^{t+1}$. The proof of the main result is based on Chebyshev's inequality and the asymptotic analysis of a trivariate rational function using methods from analytic combinatorics.

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence a n and given b j , b j , p j and δ j , δ j , present some challenges. The discrete nature of this recurrence (represented by the floor and ceiling functions) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi [1998] who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy and prove the Central Limit Theorem for the phrase length. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet’s algorithm to the (asymptotically) optimal Tunstall scheme.

We study the binary deletion channel where each input bit is independently deleted according to a fixed probability. We relate the conditional probability distribution of the output of the deletion channel given the input to the hidden pattern matching problem. This yields a new characterization of the mutual information between the input and output of the deletion channel. Through this characterization we are able to comment on the the deletion channel capacity, in particular for deletion probabilities approaching 0 and 1.

Let Pn denote a graph drawn uniformly at random from the class of all simple planar graphs with n vertices. We show that the maximum degree of a vertex in Pn is with probability 1 − o(1) asymptotically equal to c log n, where c ≈ 2.529 is determined explicitly. A similar result is also true for random 2-connected planar graphs. Our analysis combines two orthogonal methods that complement each other. First, in order to obtain the upper bound, we resort to exact methods, i.e., to generating functions and analytic combinatorics. This allows us to obtain fairly precise asymptotic estimates for the expected number of vertices of any given degree in Pn. On the other hand, for the lower bound we use Boltzmann sampling. In particular, by tracing the execution of an adequate algorithm that generates a random planar graph, we are able to explicitly find vertices of sufficiently high degree in Pn.

Cuckoo hashing was introduced by Pagh and Rodler in 2001. Its main feature is that it provides constant worst-case search time. The aim of this article is to present a precise average case analysis of Cuckoo hashing. In particular, we determine the probability that Cuckoo hashing produces no conflicts and give an upper bound for the construction time, that is linear in the size of the table. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph, and an application of a double saddle point method to obtain asymptotic expansions. Furthermore, we provide some results concerning the structure of these kinds of random graphs. Our results extend the analysis of Devroye and Morin [2003]. Additionally, we provide numerical results confirming the mathematical analysis.

In 1993 Boncelet introduced a block arithmetic scheme for entropy coding that combines advantages of stream arithmetic coding with algorithmic simplicity. It is a variable-to-fixed length encoding in which the source sequence is partitioned into variable length phrases that are encoded by a fixed length dictionary pointer. The parsing is accomplished through a complete parsing tree whose leaves represent phrases. This tree, in its suboptimal heuristic version, is constructed by a simple divide and conquer algorithm, whose analysis is the subject of this paper. For a memoryless source, we first derive the average redundancy and compare it to the (asymptotically) optimal Tunstall's algorithm. Then we prove a central limit theorem for the phrase length. To establish these results, we apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara.

Divide-and-conquer recurrences are one of the most studied equations in computer science. Yet, discrete versions of these recurrences, namely for some known sequence an and given bj, pj and δj, present some challenges. The discrete nature of this recurrence (represented by the floor function) introduces certain oscillations not captured by the traditional Master Theorem, for example due to Akra and Bazzi who primary studied the continuous version of the recurrence. We apply powerful techniques such as Dirichlet series, Mellin-Perron formula, and (extended) Tauberian theorems of Wiener-Ikehara to provide a complete and precise solution to this basic computer science recurrence. We illustrate applicability of our results on several examples including a popular and fast arithmetic coding algorithm due to Boncelet for which we estimate its average redundancy. To the best of our knowledge, discrete divide and conquer recurrences were not studied in this generality and such detail; in particular, this allows us to compare the redundancy of Boncelet's algorithm to the (asymptotically) optimal Tunstall scheme.

We present a unified general method for the asymptotic study of graphs from the so-called subcritical graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works in both the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp., $g_n$) of labelled (resp., unlabelled) graphs on n vertices from a subcritical graph class ${\mathcal{G}}=\cup_n {\mathcal{G}_n}$ satisfies asymptotically the universal behavior $g_n = c \!n^{-5/2} \!\gamma^n \! (1+o(1))$ for computable constants $c,\gamma$, e.g., $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree k (k fixed) in a graph chosen uniformly at random from $\mathcal{G}_n$ converges (after rescaling) to a normal law as $n\to\infty$.

A variable-to-fixed length encoder partitions the source string into variable-length phrases that belong to a given and fixed dictionary. Tunstall, and independently Khodak, designed variable-to-fixed length codes for memoryless sources that are optimal under certain constraints. In this paper, we study the Tunstall and Khodak codes using variety of techniques ranging from stopping times for sums of independent random variables to Tauberian theorems and Mellin transform. After proposing an algebraic characterization of the Tunstall and Khodak codes, we present new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates.

A digital search tree (DST) – one of the most fundamental data structures on words – is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. Such trees find myriad of applications from the popular Lempel-Ziv'78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it is a function of the number of stored strings and the distance from the root. Most parameters of DST (e.g., height, fill-up) can be expressed in terms of the profile. However, from the inception of DST, the analysis of the profile has been elusive and it has become a prominent open problem in the area of analysis of algorithms. We make here the first, but decisive, step towards solving this problem. We present a precise analysis of the average profile when stored strings are generated by a biased memoryless source. The main technical difficulty of analyzing the profile lies in solving a sophisticated recurrence equation. We present such a solution for the Poissonized version of the problem (i.e., when the number of stored strings is generated by a Poisson distribution) in the Mellin transform domain. To accomplish it, we introduce a novel functional operator that allows us to express the solution in an explicit form, and then using analytic algorithmics tools to extract the asymptotic behavior of the profile. This analysis is surprisingly demanding but once it is carried out it reveals unusually intriguing and interesting behavior. The average profile undergoes several phase transitions when moving from the root to the longest path. At first, it resembles a full tree until it abruptly starts growing polynomially and it oscillates in this range. Our results are derived by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis and uniform asymptotic analysis. Index Terms: Digital search trees, trees profile, analytic combinatorics, analysis of algorithms, generating functions, Mellin transform.

Variable-to-variable (VV) codes are very attractive yet not well understood data compression schemes. In 1972, Khodak claimed to provide upper and lower bounds for the achievable redundancy rate, however, he did not offer explicit construction of such codes. In this paper, we first present a constructive and transparent proof of Khodak's result showing that for memoryless sources there exists a code with the average redundancy bounded byD-5/3, whereDis the average delay (e.g., the average length of a dictionary entry). We also describe an algorithm that constructs a VV length code with a small redundancy rate for largeD. Then, we discuss several generalizations. We prove that the worst case redundancy does not exceedD-4/3. Furthermore, we provide similar upper bound for Markov sources (of order 1). Finally, we consider bounds that are valid foralmostallmemoryless and Markov sources for which the set of exceptional source parameters has zero measure. In particular, for all memoryless sources outside this exceptional class, we prove there exists a VV code with the average redundancy rate bounded byD-1-m/3+epsivand the worst case redundancy rate bounded byD-1-m/3+epsiv, wheremis the cardinality of the alphabet. We complete our analysis with a lower bound showing that for all VV codes the average and the worst case redundancy rates are at leastD-2m-1-epsivfor almost all memoryless sources in the sense that the set of exceptional source parameters has zero measure. We prove these results using techniques of Diophantine approximations.

We study the Tunstall code using the machinery from the analysis of algorithms literature. In particular, we propose an algebraic characterization of the Tunstall code which, together with tools like the Mellin transform and the Tauberian theorems, leads to new results on the variance and a central limit theorem for dictionary phrase lengths. This analysis also provides a new argument for obtaining asymptotic results about the mean dictionary phrase length and average redundancy rates

For the register function for t -ary trees, recently introduced by Auber et al., we prove that the average is log 4 n + O (1), if all such trees with n internal nodes are considered to be equally likely.This result remains true for rooted trees where the set of possible out-degrees is finite. Furthermore we obtain exponential tail estimates for the distribution of the register function. Thus, the distribution is highly concentrated around the mean value.

We show that the variances of the profile (number of nodes at each level) of random binary search trees undergoes asymptotically four phase transitions and exhibits a bimodal or "two-humped" behavior, in contrast to the unimodality of the expected value of the profiles. Precise asymptotic approximations are derived. The same types of phenomena also hold for the profile of random recursive trees.

There are three major classes of lossless compression: fixed-to-variable (FV) length codes, variable-to-fixed (VF) length codes, and finally variable-to-variable (VV) length codes. This paper presents the construction and analysis of a VV-code with small average and maximal redundancy that decays to zero as the average code length increases. A variable-to-variable (VV) code is a concatenation of variable-to-fixed and fixed-to-variable codes.

Recent years have seen a resurgence of interest in redundancy of lossless coding. The redundancy (regret) of universal fixed-to-variable length coding for a class of sources determines by how much the actual code length exceeds the optimal (ideal over the class) code length. In a minimax scenario one finds the best code for the worst source either in the worst case (called also maximal minimax) or on average. We first study the worst case minimax redundancy over a class of stationary ergodic sources and replace Shtarkov's bound by an exact formula. Among others, we prove that a generalized Shannon code minimizes the worst case redundancy, derive asymptotically its redundancy, and establish some general properties. This allows us to obtain precise redundancy for memoryless, Markov, and renewal sources. For example, we present the exact constant of the redundancy for memoryless and Markov sources by showing that the integer nature of coding contributes log(logm/(m-1))/logm+o(1) where m is the size of the alphabet. Then we deal with the average minimax redundancy and regret. Our approach here is orthogonal to most recent research in this area since we aspire to show that asymptotically the average minimax redundancy is equivalent to the worst case minimax redundancy for some classes of sources. After formulating some general bounds relating these two redundancies, we prove our assertion for memoryless and Markov sources. Nevertheless, we provide evidence that maximal redundancy of renewal processes does not have the same leading term as the average minimax redundancy (however, our general results show that maximal and average regrets are asymptotically equivalent).

It is shown that all centralized absolute moments E | H n − E H n | α (α ≥ 0) of the height H n of binary search trees of size n and of the saturation level H n ′ are bounded. The methods used rely on the analysis of a retarded differential equation of the form Φ′( u ) = −α −2 Φ( u /α) 2 with α > 1. The method can also be extended to prove the same result for the height of m -ary search trees. Finally the limiting behaviour of the distribution of the height of binary search trees is precisely determined.

Redundancy is defined as the excess of the code length over the optimal (ideal) code length. We study the average redundancy of an idealized arithmetic coding (for memoryless sources with unknown distributions) in which the Krichevsky and Trofimov (1981) estimator is followed by the Shannon-Fano code. We shall ignore here important practical implementation issues such as finite precisions and finite buffer sizes. In fact, our idealized arithmetic code can be viewed as an adaptive infinite precision implementation of arithmetic encoder that resembles Elias coding. However, we provide very precise results for the average redundancy that takes into account integer-length constraints. These findings are obtained by analytic methods of analysis of algorithms such as theory of distribution of sequences modulo 1 and Fourier series. These estimates can be used to study the average redundancy of codes for tree sources, and ultimately the context-tree weighting algorithms.

We present a general theorem that can be used to identify the limiting distribution for a class of combinatorial schemata. For example, many parameters in random mappings can be covered in this way. In particular, we can derive the limiting distribution of those points with a given number of total predecessors.

It has been well-known for nearly 20 years that the bistable behavior of infinite population slotted ALOHA networks causes the unpleasant effect of eventually reaching an overloaded state, where the number of backlogged stations becomes larger and larger and the useful throughput reduces to zero. The detailed analysis reveals that this statement is true for any average offered load lambda >0, regardless of the retransmission probability p. A challenging, and to the best of the authors' knowledge, not sufficiently solved problem within this context concerns the time until this destabilization occurs. This question is successfully answered based on the fact that the operation of the system may be viewed as a sequence of consecutive busy periods, each starting from backlog 0 and return to backlog 0. It turns out that the whole period of successful operation S consists of a finite sequence of busy periods of finite lengths, which is "terminated" by an infinite busy period (which never returns to backlog 0). Further analysis of this simple renewal process leads to an infinite dimensional system of linear equations, which is shown to have only one meaningful solution. A pair of upper and lower asymptotic bounds for that solution eventually provide the key to the major result, an asymptotic formula for the average number of slots up to the beginning of the infinite busy period, uniformly for p to 0 and lambda to 0.>