The paper studies the behaviour of selection algorithms that are based on dichotomy principles. On the entry formed by an ordered list L and a searched element x not in L, they return the interval of the list L the element x belongs to. We focus here on the case of words, where dichotomy principles lead to a selection algorithm designed by Crochemore, Hancart and Lecroq, which appears to be "quasi-optimal". We perform a probabilistic analysis of this algorithm that exhibits its quasi-optimality on average.

We introduce and study a multiple gcd algorithm that is a natural extension of the usual Euclid algorithm, and coincides with it for two entries; it performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun. We perform the average-case analysis of this algorithm, and prove that the mean number of steps is linear with respect to the size of the entry. The method relies on dynamical analysis, and is based on the study of the underlying Brun dynamical system. The dominant constant of the analysis is related to the entropy of the system. We also compare this algorithm to another extension of the Euclid algorithm, proposed by Knuth, and already analyzed by the authors.

Based on rescaling by some suitable sequence instead of the number of time units, the usual notion of divergence rate is here extended to define and determine meaningful generalized divergence rates. Rescaling entropy rates appears as a special case. Suitable rescaling is naturally induced by the asymptotic behavior of the marginal divergences. Closed-form formulas are obtained as soon as the marginal divergences behave like powers of some analytical functions. A wide class of countable Markov chains is proved to satisfy this property. Most divergence and entropy functionals defined in the literature are concerned, e.g., the classical Shannon, Kullback-Leibler, Rényi, and Tsallis. For illustration purposes, Ferreri or Basu-Harris-Hjort-Jones - among others - are also considered.

This paper provides a probabilistic analysis of an algorithm which computes the gcd of ℓ inputs (with ℓ ≥ 2), with a succession of ℓ - 1 phases, each of them being the Euclid algorithm on two entries. This algorithm is both basic and natural, and two kinds of inputs are studied: polynomials over the finite field Fq and integers. The analysis exhibits the precise probabilistic behaviour of the main parameters, namely the number of iterations in each phase and the evolution of the length of the current gcd along the execution. We first provide an average-case analysis. Then we make it even more precise by a distributional analysis. Our results rigorously exhibit two phenomena: (i) there is a strong difference between the first phase, where most of the computations are done and the remaining phases; (ii) there is a strong similarity between the polynomial and integer cases, as can be expected.

We study entropy rates of random sequences for general entropy functionals including the classical Shannon and Rényi entropies and the more recent Tsallis and Sharma–Mittal ones. In the first part, we obtain an explicit formula for the entropy rate for a large class of entropy functionals, as soon as the process satisfies a regularity property known in dynamical systems theory as the quasi-power property. Independent and identically distributed sequence of random variables naturally satisfy this property. Markov chains are proven to satisfy it, too, under simple explicit conditions on their transition probabilities. All the entropy rates under study are thus shown to be either infinite or zero except at a threshold where they are equal to Shannon or Rényi entropy rates up to a multiplicative constant. In the second part, we focus on the estimation of the marginal generalized entropy and entropy rate for parametric Markov chains. Estimators with good asymptotic properties are built through a plug-in procedure using a maximum likelihood estimation of the parameter.

In data mining, enumerate the frequent or the closed patterns is often the first difficult task leading to the association rules discovery. The number of these patterns represents a great interest. The lower bound is known to be constant whereas the upper bound is exponential, but both situations correspond to pathological cases. For the first time, we give an average analysis of the number of frequent or closed patterns. Average analysis is often closer to real situations and gives more information about the role of the parameters. In this paper, two probabilistic models are studied: a Bernoulli and a Markovian. In both models and for large databases, we prove that the number of frequent patterns, for a fixed frequency threshold, is exponential in the number of items and polynomial in the number of transactions. On the other hand, for a proportional frequency threshold, the number of frequent patterns is polynomial in the number of items and does not involve the number of transactions. Finally, we prove in the Bernoulli model that the number of closed patterns, for a proportional frequency threshold, is polynomial in the number of items.