Search

In the coupon collector problem with $n$ items, the collector needs a random number of tries $T_{n}\simeq n\ln n$ to complete the collection. Also, after $nt$ tries, the collector has secured approximately a fraction $\zeta_{\infty}(t)=1-e^{-t}$ of the complete collection, so we call $\zeta_{\infty}$ the (asymptotic) \emph{completion curve}. In this paper, for $\nu>0$, we address the asymptotic shape $\zeta (\nu,.) $ of the completion curve under the condition $T_{n}\leq \left( 1+\nu \right) n$, i.e. assuming that the collection is \emph{completed unlikely fast}. As an application to the asymptotic study of complete accessible automata, we provide a new derivation of a formula due to Kor\v{s}unov.

International audience

A classification strategy based on $\delta$-patterns is developed via a combinatorial optimization problem related with the maximal clique generation problem on a graph. The proposed solution uses the cross entropy method and has the advantage to be particularly suitable for large datasets. This study is tailored for the particularities of the genomic data.

We show that the number of spanning trees in the finite Sierpiński graph of level $n$ is given by $\sqrt[4]{\frac{3}{20}} (\frac{5}{3})^{-n/2} (\sqrt[4]{540})^{3^n}$. The proof proceeds in two steps: First, we show that the number of spanning trees and two further quantities satisfy a $3$-dimensional polynomial recursion using the self-similar structure. Secondly, it turns out, that the dynamical behavior of the recursion is given by a $2$-dimensional polynomial map, whose iterates can be computed explicitly.

This paper tackles the enumeration and asymptotics of the area below directed lattice paths (walks on $\mathbb{N}$ with a finite set of jumps). It is a nice surprise (obtained via the "kernel method'') that the generating functions of the moments of the area are algebraic functions, expressible as symmetric functions in terms of the roots of the kernel. For a large class of walks, we give full asymptotics for the average area of excursions ("discrete'' reflected Brownian bridge) and meanders ("discrete'' reflected Brownian motion). We show that drift is not playing any role in the first case. We also generalise previous works related to the number of points below a path and to the area between a path and a line of rational slope.

We determine the spectral dimensions of a variety of ensembles of infinite trees. Common to the ensembles considered is that sample trees have a distinguished infinite spine at whose vertices branches can be attached according to some probability distribution. In particular, we consider a family of ensembles of $\textit{combs}$, whose branches are linear chains, with spectral dimensions varying continuously between $1$ and $3/2$. We also introduce a class of ensembles of infinite trees, called $\textit{generic random trees}$, which are obtained as limits of ensembles of finite trees conditioned to have fixed size $N$, as $N \to \infty$. Among these ensembles is the so-called uniform random tree. We show that generic random trees have spectral dimension $d_s=4/3$.

We establish a fundamental isomorphism between discrete-time balanced urn processes and certain ordinary differential systems, which are nonlinear, autonomous, and of a simple monomial form. As a consequence, all balanced urn processes with balls of two colours are proved to be analytically solvable in finite terms. The corresponding generating functions are expressed in terms of certain Abelian integrals over curves of the Fermat type (which are also hypergeometric functions), together with their inverses. A consequence is the unification of the analyses of many classical models, including those related to the coupon collector's problem, particle transfer (the Ehrenfest model), Friedman's "adverse campaign'' and Pólya's contagion model, as well as the OK Corral model (a basic case of Lanchester's theory of conflicts). In each case, it is possible to quantify very precisely the probable composition of the urn at any discrete instant. We study here in detail "semi-sacrificial'' urns, for which the following are obtained: a Gaussian limiting distribution with speed of convergence estimates as well as a characterization of the large and extreme large deviation regimes. We also work out explicitly the case of $2$-dimensional triangular models, where local limit laws of the stable type are obtained. A few models of dimension three or greater, e.g., "autistic'' (generalized Pólya), cyclic chambers (generalized Ehrenfest), generalized coupon-collector, and triangular urns, are also shown to be exactly solvable.

We analyse the distribution of the root pattern of randomly grown multidimensional point quadtrees. In particular, exact, recursive and asymptotic formulas are given for the expected arity of the root.

We solve a problem by V. I. Arnold dealing with "how random" modular arithmetic progressions can be. After making precise how Arnold proposes to measure the randomness of a modular sequence, we show that this measure of randomness takes a simplified form in the case of arithmetic progressions. This simplified expression is then estimated using the methodology of dynamical analysis, which operates with tools coming from dynamical systems theory. In conclusion, this study shows that modular arithmetic progressions are far from behaving like purely random sequences, according to Arnold's definition.

We investigate class of well-poised basic hypergeometric series $\tilde{J}_{k,i}(a;x;q)$, interpreting these series as generating functions for overpartitions defined by multiplicity conditions. We also show how to interpret the $\tilde{J}_{k,i}(a;1;q)$ as generating functions for overpartitions whose successive ranks are bounded, for overpartitions that are invariant under a certain class of conjugations, and for special restricted lattice paths. We highlight the cases $(a,q) \to (1/q,q)$, $(1/q,q^2)$, and $(0,q)$, where some of the functions $\tilde{J}_{k,i}(a;x;q)$ become infinite products. The latter case corresponds to Bressoud's family of Rogers-Ramanujan identities for even moduli.

For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model. While the average in Pugh's original version behaves like $Q \log_Q n$, with $Q = \frac{1}{q}$ a parameter, it is here given by $(Q+1) \log_Q n$.

In this paper, we discuss the problem of estimating the number of "elephants'' in a stream of IP packets. First, the problem is formulated in the context of multisets. Next, we explore some of the theoretical space complexity of this problem, and it is shown that it cannot be solved with less than $\Omega (n)$ units of memory in general, $n$ being the number of different elements in the multiset. Finally, we describe an algorithm, based on Durand-Flajolet's LOGLOG algorithm coupled with a thinning of the packet stream, which returns an estimator of the number of elephants using a small amount of memory. This algorithm allows a good estimation for particular families of random multiset. The mean and variance of this estimator are computed. The algorithm is then tested on synthetic data.

We consider extended binary trees and study the common right and left depth of leaf $j$, where the leaves are labelled from left to right by $0, 1, \ldots, n$, and the common right and left external pathlength of binary trees of size $n$. Under the random tree model, i.e., the Catalan model, we characterize the common limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf $j$ in a random size-$n$ binary tree when $j \sim \rho n$ with $0< \rho < 1$, as well as the common limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-$n$ binary tree.

F.Giroire has recently proposed an algorithm which returns the approximate number of distincts elements in a large sequence of words, under strong constraints coming from the analysis of large data bases. His estimation is based on statistical properties of uniform random variables in $[0,1]$. In this note we propose an optimal estimation, using Kullback information and estimation theory., Comment: Extended and improved version of the published paper

The purpose of this survey is to present recent results concerning concentration properties of extremal parameters of random discrete structures. A main emphasis is placed on the height and maximum degree of several kinds of random trees. We also provide exponential tail estimates for the height distribution of scale-free trees.

Building on theoretical insights and rich experimental data of our preprints, we present here new theoretical and experimental results in three interrelated approaches to the Collatz problem and its generalizations: \emphalgorithmic decidability, random behavior, and Diophantine representation of related discrete dynamical systems, and their \emphcyclic and divergent properties.

An ordered partition of $[n]:=\{1,2,\ldots, n\}$ is a sequence of disjoint and nonempty subsets, called blocks, whose union is $[n]$. The aim of this paper is to compute some generating functions of ordered partitions by the transfer-matrix method. In particular, we prove several conjectures of Steingrímsson, which assert that the generating function of some statistics of ordered partitions give rise to a natural $q$-analogue of $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind.

A result of Foata and Schützenberger states that two statistics on permutations, the number of inversions and the inverse major index, have the same distribution on a descent class. We give a multivariate generalization of this property: the sorted vectors of the Lehmer code, of the inverse majcode, and of a new code (the inverse saillance code), have the same distribution on a descent class, and their common multivariate generating function is a flagged ribbon Schur function.

In this paper we consider the class of $\textit{permutominoes}$, i.e. a special class of polyominoes which are determined by a pair of permutations having the same size. We give a characterization of the permutations associated with convex permutominoes, and then we enumerate various classes of convex permutominoes, including parallelogram, directed-convex, and stack ones.

The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs.

In this paper we study a variant of the Sand Piles Model, where the evolution rule consists of the falling down of one grain to a random column and an avalanche to reach a stable configuration. We prove that the infinite set of all stable configurations have a lattice structure which is a sublattice of Young lattice. At the end, based on a discussion about avalanches, we construct a generating tree of this model and show its strongtly recursive structure.

A leader election algorithm is an elimination process that divides recursively into tow subgroups an initial group of n items, eliminates one subgroup and continues the procedure until a subgroup is of size 1. In this paper the biased case is analyzed. We are interested in the cost of the algorithm e. the number of operations needed until the algorithm stops. Using a probabilistic approach, the asymptotic behavior of the algorithm is shown to be related to the behavior of a hitting time of two random sequences on [0,1].

In this article, we study a variant of the coupon collector's problem introducing a notion of a \emphbonus. Suppose that there are c different types of coupons made up of bonus coupons and ordinary coupons, and that a collector gets every coupon with probability 1/c each day. Moreover suppose that every time he gets a bonus coupon he immediately obtains one more coupon. Under this setting, we consider the number of days he needs to collect in order to have at least one of each type. We then give not only the expectation but also the exact distribution represented by a gamma distribution. Moreover we investigate their limits as the Gumbel (double exponential) distribution and the Gauss (normal) distribution.

We consider growing random recursive trees in random environment, in which at each step a new vertex is attached according to a probability distribution that assigns the tree vertices masses proportional to their random weights.The main aim of the paper is to study the asymptotic behavior of the mean numbers of outgoing vertices as the number of steps tends to infinity, under the assumption that the random weights have a product form with independent identically distributed factors.