We consider additive functionals X_n(ϕ) with small toll functions on split trees and a generalization of split trees, which we call fractional split trees, where the split vector does not need to sum up to 1. These additive functionals encompass e.g. the number of nodes, number of leaves and the number of fringe trees of a certain size. We show convergence of the first moment to a limit, which we can explicitly compute if all balls are distributed multinomially and for some models with Beta-distributed splitter. Generally, the first moment is given in terms of negative moments of a perpetuity and can often be approximated to arbitrary precision with known bounds. In split trees and certain fractional split trees, the standard deviation is of smaller order than the first moment, where we show a weak law of large numbers. In other fractional split trees, the standard deviation is of the same order and we show a distribution limit using the contraction method.

We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a small number of bits per substream are saved to achieve a relative accuracy proportional to 1 / M . Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Performance hypotheses are validated through experiments using a realistic input stream, with the general conclusion that our algorithms are significantly more accurate than HyperLogLog when using the same amount of memory, and they use significantly less memory than HyperLogLog to achieve a given accuracy. • Efficient algorithms for estimating the number of distinct items in a data stream. • Explicit characterization of the distribution of reported values. • Detailed fair comparisons with other algorithms in the literature. • Sufficient detail to enable development of real-world implementations.

We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a constant number of bits per substream are saved to achieve a relative accuracy proportional to 1/√M. Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Hypotheses about performance are validated through experiments using a realistic input stream, with the conclusion that our algorithms are more accurate than HyperLogLog when using the same amount of memory, and they use two-thirds as much memory as HyperLogLog to achieve a given accuracy.

We prove that the number of fringe subtrees, isomorphic to a given tree, in uniformly random trees with given vertex degrees, asymptotically follows a normal distribution. As an application, we establish the same asymptotic normality for random simply generated trees (conditioned Galton-Watson trees). Our approach relies on an extension of Gao and Wormald's (2004) theorem to the multivariate setting.

We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan.

We consider a random permutation drawn from the set of permutations of length n that avoid some given set of patterns of length 3. We show that the number of occurrences of another pattern $$\sigma $$ has a limit distribution, after suitable scaling. In several cases, the number is asymptotically normal; this contrasts to the cases of permutations avoiding a single pattern of length 3 studied in earlier papers.

We study I(T), the number of inversions in a tree T with its vertices labeled uniformly at random. We first show that the cumulants of I(T) have explicit formulas. Then we consider X_n, the normalized version of I(T_n), for a sequence of trees T_n. For fixed T_n's, we prove a sufficient condition for X_n to converge in distribution. For T_n being split trees [Devroye, 1999], we show that X_n converges to the unique solution of a distributional equation. Finally, when T_n's are conditional Galton-Watson trees, we show that X_n converges to a random variable defined in terms of Brownian excursions. Our results generalize and extend previous work by Panholzer and Seitz [Panholzer and Seitz, 2012].

Consider a random permutation drawn from the set of permutations of length n that avoid a given set of one or several patterns of length 3. We show that the number of occurrences of another pattern has a limit distribution, after suitable scaling. In several cases, the limit is normal, as it is in the case of unrestricted random permutations; in other cases the limit is a non-normal distribution, depending on the studied pattern. In the case when a single pattern of length 3 is forbidden, the limit distributions can be expressed in terms of a Brownian excursion. The analysis is made case by case; unfortunately, no general method is known, and no general pattern emerges from the results.

In the late 19th century, Lars Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants one minimizing the maximal load and one minimizing the variance of loads —and a sequential variant. We study Phragmén's methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sánchez-Fernández et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the com- putational complexity of Phragmén's methods and provide mixed-integer programming based algorithms for computing them.

Divide-and-conquer recurrences of the form f ( n ) = f (⌊ n/2⌋ ) + f ( ⌈ n/2⌉ ) + g ( n ) ( n ⩾ 2), with g ( n ) and f (1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f ( n ) = n P (log 2 n ) − Q ( n ) under an optimum (iff) condition on g ( n ). This form is not only an identity but also an asymptotic expansion because Q ( n ) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.

The time it takes a random walker in a lattice to reach the origin from another vertex x has infinite mean. If the walker can restart the walk at x at will, then the minimum expected hitting time $\gamma(x,0)$ (minimized over restarting strategies) is finite; it was called the “grade” of x by Dumitriu, Tetali, and Winkler. They showed that in a more general setting, the grade (a variant of the “Gittins index”) plays a crucial role in control problems involving several Markov chains. Here we establish several conjectures of Dumitriu, Tetali, and Winkler on the asymptotics of the grade in Euclidean lattices. In particular, we show that in the planar square lattice, $\gamma(x,0)$ is asymptotic to $2|x|^2\log|x|$ as $|x| \to \infty$. The proof hinges on the local variance of the potential kernel h being almost constant on the level sets of h. We also show how the same method yields precise second order asymptotics for hitting times of a random walk (without restarts) in a lattice disk.

In this paper, we consider identifying codes in binary Hamming spaces Fn. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let a code C ¿ Fn. For any set of words X ¿ Fn, denote by Ir(X) = Ir(C; X) the set of codewords within distance r from at least one x ¿ X. Now a code C ¿ Fnis called (r, ¿ ¿)-identifying if the sets Ir(X) are distinct for all X ¿ Fnof size at most ¿. Let us denote by Mr(¿¿)(n) the smallest possible cardinality of an (r, ¿ ¿)-identifying code. In 2002, Honkala and Lobstein showed for ¿ = 1 that limn¿¿1/n log2Mr(¿¿)(n) = 1 - h(¿) where r = [¿n], ¿ ¿ (0, 1) and h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed ¿ ¿ 1 when ¿ ¿ (0, 1/2). We also show that Mr(¿¿)(n) = O(n3/2) for every fixed ¿ and r slightly less than n/2, and give an explicit construction of small (r, ¿ 2)-identifying codes for r = [n/2] - 1.

Andersson and Nilsson introduced in 1993 a level-compressed trie (for short, LC trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. Recent experimental results indicated a “dramatic improvement” when full subtrees are replaced by “partially filled subtrees.” In this article, we provide a theoretical justification of these experimental results, showing, among others, a rather moderate improvement in search time over the original LC tries. For such an analysis, we assume that n strings are generated independently by a binary memoryless source, with p denoting the probability of emitting a “1” (and q = 1 − p ). We first prove that the so-called α-fillup level F n (α) (i.e., the largest level in a trie with α fraction of nodes present at this level) is concentrated on two values with high probability: either F n (α) = k n or F n (α) = k n + 1, where k n = log 1/√ pq n − |ln ( p/q )|/2 ln 3/2 (1√ pq ) Φ −1 (α) √ ln n + O (1) is an integer and Φ( x ) denotes the normal distribution function. This result directly yields the typical depth (search time) D n (α) in the α-LC tries, namely, we show that with high probability D n (α) ∼ C 2 log log n , where C 2 = 1/|log(1 − h /log(1/√ pq ))| for p ≠ q and h = − p log p − q log q is the Shannon entropy rate. This should be compared with recently found typical depth in the original LC tries, which is C 1 log log n , where C 1 = 1/|log(1− h /log(1/min{ p , 1− p }))|. In conclusion, we observe that α affects only the lower term of the α-fillup level F n (α), and the search time in α-LC tries is of the same order as in the original LC tries.

We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some α, 0 < α < 1. (In the case of Last Come, the results are more complicated and less complete than in the other cases.)We also show, using the diagonal Poisson transform studied by Poblete, Viola and Munro, that exact expressions for finitemandncan be obtained from the limits asm,n→ ∞.We end with some results, conjectures and questions about the shape of the limit distributions. These have some relevance for computer applications.

This paper discusses the measure of complexity of a sequence called the complexity index. The complexity index captures the "richness of the language" used in a sequence. The measure is simple but quite intuitive. Sequences with low complexity index contain a large number of repeated substrings and they eventually become periodic (e.g., tandem repeats in a DNA sequence). The complexity index is used to characterize the sequence statistically and has a long history of applications in several fields, such as data compression, computational biology, data mining, computational linguistics, among others.