Analysis of algorithms is concerned with accurate estimates of complexity parameters of algorithms and aims at predicting the behaviour of a given algorithm run in a given environment. It develops general methods for obtaining closed-form formulae, asymptotic estimates, and probability distributions for combinatorial or probabilistic quantities, that are of interest in the optimization of algorithms. Interest is also placed on the methods themselves, whether combinatorial, probabilistic, or analytic. Combinatorial and statistical properties of discrete structures (strings, trees, tries, dags, graphs, and so on) as well as mathematical objects (e.g., continued fractions, polynomials, operators) that are relevant to the design of efficient algorithms are investigated.
Editors:Luc Devroye, Philippe Jacquet, Wojciech Szpankowski
Editors:Luc Devroye, Philippe Jacquet, Wojciech Szpankowski
We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the set of possible limits and its structure as a metric space. For random trees the subtree size topology arises in the context of algorithms for searching and sorting when applied to random input, resulting in a sequence of nested trees. For these we obtain a structural result based on a local version of exchangeability. This in turn leads to a central limit theorem, with possibly mixed asymptotic normality. Comment: Journal version
In 2010, Kh. Hessami Pilehrood and T. Hessami Pilehrood introduced generating function identities used to obtain series accelerations for values of Dirichlet's $\beta$ function, via the Markov--Wilf--Zeilberger method. Inspired by these past results, together with related results introduced by Chu et al., we introduce a variety of hypergeometric recurrences. We prove these recurrences using the WZ method, and we apply these recurrences to obtain series acceleration identities. We introduce a family of summations generalizing a Ramanujan-type series for $\frac{1}{\pi^2}$ due to Guillera, and a family of summations generalizing an accelerated series for Catalan's constant due to Lupa\c{s}, and many related results.
We study the following problem. Given a multiset $M$ of non-negative integers, decide whether there exist and, in the positive case, compute two non-trivial multisets whose Minkowski sum is equal to $M$. The Minkowski sum of two multisets A and B is a multiset containing all possible sums of any element of A and any element of B. This problem was proved to be NP-complete when multisets are replaced by sets. This version of the problem is strictly related to the factorization of boolean polynomials that turns out to be NP-complete as well. When multisets are considered, the problem is equivalent to the factorization of polynomials with non-negative integer coefficients. The computational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposing multisets of non-negative integers. Experimental results show that our heuristic decomposes multisets of hundreds of elements within seconds independently of the magnitude of numbers belonging to the multisets. Our heuristic can be used also for factoring polynomials in N[x]. We show that, when the degree of the polynomials gets larger, our technique is much faster than the state-of-the-art algorithms implemented in commercial software like Mathematica and MatLab.
Anna M. Brandenberger, Luc Devroye, Marcel K. Goh, Rosie Y. Zhao
Abstract
This note defines a notion of multiplicity for nodes in a rooted tree and presents an asymptotic calculation of the maximum multiplicity over all leaves in a Bienaym\'e-Galton-Watson tree with critical offspring distribution $\xi$, conditioned on the tree being of size $n$. In particular, we show that if $S_n$ is the maximum multiplicity in a conditional Bienaym\'e-Galton-Watson tree, then $S_n = \Omega(\log n)$ asymptotically in probability and under the further assumption that ${\bf E}\{2^\xi\} < \infty$, we have $S_n = O(\log n)$ asymptotically in probability as well. Explicit formulas are given for the constants in both bounds. We conclude by discussing links with an alternate definition of multiplicity that arises in the root-estimation problem. Comment: 17 pages, 6 figures, final journal version
We are given $n$ balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the same size. We can ask sets of $k$ balls as queries, and the problem has different variants, according to what the answers to the queries can be. These questions has attracted several researchers, but the focus of most research was the adaptive version, where queries are decided sequentially, after learning the answer to the previous query. Here we study the non-adaptive version, where all the queries have to be asked at the same time. Comment: 12 pages
Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a $k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdots w^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of the same length. For an infinite word $w$ and a positive integer $k$, define $AP_j(w,k)$ to be the set of all integers $m$ such that $w_{j+1} w_{j+2} \cdots w_{j+km}$ is a $k$-anti-power, where $w_i$ denotes the $i$-th letter of $w$. Define also $\mathcal{F}_j(k) = (2 \mathbb{Z}^+ - 1) \cap AP_j(\mathbf{t},k)$, where $\mathbf{t}$ denotes the Thue-Morse word. For all $k \in \mathbb{Z}^+$, $\gamma_j(k) = \min (AP_j(\mathbf{t},k))$ is a well-defined positive integer, and for $k \in \mathbb{Z}^+$ sufficiently large, $\Gamma_j(k) = \sup ((2 \mathbb{Z}^+ -1) \setminus \mathcal{F}_j(k))$ is a well-defined odd positive integer. In his 2018 paper, Defant shows that $\gamma_0(k)$ and $\Gamma_0(k)$ grow linearly in $k$. We generalize Defant's methods to prove that $\gamma_j(k)$ and $\Gamma_j(k)$ grow linearly in $k$ for any nonnegative integer $j$. In particular, we show that $\displaystyle 1/10 \leq \liminf_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 9/10$ and $\displaystyle 1/5 \leq \limsup_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 3/2$. Additionally, we show that $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and $\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$. Comment: 21 pages
Margaret Archibald, Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, Stephan Wagner, Mark Ward
Abstract
A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length $n$. We also obtain the asymptotics for the expected number as $n \to \infty$. Comment: 18 pages, 1 table, 1 figure. This is the final version for publication
A word of length $n$ is rich if it contains $n$ nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent $2+\sqrt{2}/2$ ($\approx 2.707$) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is $2+\sqrt{2}/2$). In this article, we give a structure theorem for infinite binary rich words that avoid $14/5$-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is $2+\sqrt{2}/2$, as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets. Comment: 16 pages
The problem of estimating the number n of distinct keys of a large collection of N data is well known in computer science. A classical algorithm is the adaptive sampling (AS). n can be estimated by R2 J , where R is the final bucket size and J is the final depth at the end of the process. Several new interesting questions can be asked about AS (some of them were suggested by P.Flajolet and popularized by J.Lumbroso). The distribution of W = log(R2 J /n) is known, we rederive this distribution in a simpler way. We provide new results on the moments of J and W. We also analyze the final cache size R distribution. We consider colored keys: assume also that among the n distinct keys, m do have color K We show how to estimate p = m n. We study keys with some multiplicity : we provide a way to estimate the total number M of some color K keys among the total number N of keys. We consider the case where we know a priori the multiplicities but not the colors. There we want to estimate the total number of keys N. An appendix is devoted to the case where the hashing function provides bits with probability different from 1/2.
In a barter exchange market, agents bring items and seek to exchange their items with one another. Agents may agree to a k-way exchange involving a cycle of k agents. A barter exchange market can be represented by a digraph where the vertices represent items and the edges out of a vertex indicate the items that an agent is willing to accept in exchange for that item. It is known that the problem of finding a set of vertex-disjoint cycles with the maximum total number of vertices (MAX-SIZE-EXCHANGE) can be solved in polynomial time. We consider a barter exchange where each agent may bring multiple items, and items of the same agent are represented by vertices with the same color. A set of cycles is said to be tropical if for every color there is a cycle that contains a vertex of that color. We show that the problem of determining whether there exists a tropical set of vertex-disjoint cycles in a digraph (TROPICAL-EXCHANGE) is NP-complete and APX-hard. This is equivalent to determining whether it is possible to arrange an exchange of items among agents such that every agent trades away at least one item. TROPICAL-MAX-SIZE-EXCHANGE is a similar problem, where the goal is to find a set of vertex-disjoint cycles that contains the maximum number of vertices and also contains all of the colors in the graph. We show that this problem is likewise NP-complete and APX-hard. For the restricted case where there are at most two vertices of each color (corresponding to a restriction that each agent may bring at most two items), both problems remain NP-hard but are in APX. Finally, we consider MAX-SIZE-TROPICAL-EXCHANGE, where the set of cycles must primarily include as many colors as possible and secondarily include as many vertices as possible. We show that this problem is NP-hard. Comment: Published in Discrete Mathematics and Theoretical Computer Science
In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis.
Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch
Abstract
Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to the study of the set of the representations of integers. This prefix-closed subset of the free monoid is naturally represented as a highly non-regular tree. Its nodes are the integers, its edges bear labels taken in {0,1,...,p-1}, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. The bottom word of n is the lexicographically smallest word that is the label of a branch of the subtree. The top word of n is defined similarly. The span-word of n is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infinite automaton whose underlying graph is essentially the same as the tree itself. Second, we study the function that computes for all n the bottom word associated with n+1 from the one associated with n, and show that it is realised by an infinite sequential transducer whose underlying graph is once again essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after the radix point, hence evaluated to a real number. If T is a subtree whose root is n, then the evaluations of the labels of the branches of T form an interval of $\mathbb{R}$. The length of this interval is called the span of n and is equal to the evaluation of the span-word of n. The set of all spans is then a subset of R and we use the preceding construction to study its topological closure. We show that it is an interval when p is greater than or equal to 2q-1, and a Cantor set of measure zero otherwise. Comment: 33 pages
Stanley lists the class of Dyck paths where all returns to the axis are of odd length as one of the many objects enumerated by (shifted) Catalan numbers. By the standard bijection in this context, these special Dyck paths correspond to a class of rooted plane trees, so-called Catalan-Stanley trees. This paper investigates a deterministic growth procedure for these trees by which any Catalan-Stanley tree can be grown from the tree of size one after some number of rounds; a parameter that will be referred to as the age of the tree. Asymptotic analyses are carried out for the age of a random Catalan-Stanley tree of given size as well as for the "speed" of the growth process by comparing the size of a given tree to the size of its ancestors.
In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory), and this article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and a link with a continued fraction expansion. Furthermore, we prove several formulae for related combinatorial structures conjectured in the On-Line Encyclopedia of Integer Sequences. Thanks to the kernel method and via analytic combinatorics, we provide the enumeration and limit laws of these "lattice paths with catastrophes" for any finite set of jumps. We end with an algorithm to generate such lattice paths uniformly at random. Comment: 32 pages
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are pairwise different. A tight tour in $H$ is a tight Euler tour if it contains all edges of $H$. We prove that the problem of deciding if a given $3$-uniform hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph), unless the ETH fails. We also present an exact exponential algorithm for the problem, whose time complexity matches this lower bound, and the space complexity is polynomial. In fact, this algorithm solves a more general problem of computing the number of tight Euler tours in a given uniform hypergraph.
Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking values in a finite state space. The asymptotics as $ m $ tends to infinity, of the first time from which on the trajectories of the $ m $ copies differ, have been studied by Szpankowski (1991) in the setting of tries. We use a different approach and model the $ m $ trajectories by a variant of the occupancy scheme, where we consider a nested sequence of boxes. This approach will enable us to extend the result to the case when the transition probabilities are random. We moreover use the same techniques to study the asymptotics as $ m $ tends to infinity of the time up to which we have observed all the possible trajectories of $ Y $ in random and nonrandom scenery.
The objective of this paper is to find in a setting of n sequential observations of objects a good online policy to select the k bestof these n uniquely rankable objects. This focus is motivated by the fact that it is hard to find closed form solutions of optimalstrategies for general k and n. Selection is without recall, and the idea is to investigate threshold functions which maintain allpresent information, that is thresholds which are functions of all selections made so far. Our main interest lies in the asymptoticbehaviour of these thresholds as n -> infinity and in the corresponding asymptotic performance of the threshold algorithm.
The partial sum of the states of a Markov chain or more generally a Markov source is asymptotically normally distributed under suitable conditions. One of these conditions is that the variance is unbounded. A simple combinatorial characterization of Markov sources which satisfy this condition is given in terms of cycles of the underlying graph of the Markov chain. Also Markov sources with higher dimensional alphabets are considered. Furthermore, the case of an unbounded covariance between two coordinates of the Markov source is combinatorically characterized. If the covariance is bounded, then the two coordinates are asymptotically independent. The results are illustrated by several examples, like the number of specific blocks in $0$-$1$-sequences and the Hamming weight of the width-$w$ non-adjacent form.
The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the asymptotic Hamming weight of a non-adjacent-form-like digit expansion, which was not known before.
In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of formulas for the expected numbers of black balls in a given urn and we analyze some special cases (parallel and serial configurations). We are mainly interested in a counterpart of the Coupon Collector Problem for the model considered. The primary motivation for our research is the formal analysis of the mix networks (introduced by D. Chaum) and its immunity to so-called flooding (blending) attacks.
