Search

It is known that in an irreducible small P��lya urn process, the composition of the urn after suitable normalization converges in distribution to a normal distribution. We show that if the urn also is balanced, this normal convergence holds with convergence of all moments, thus giving asymptotics of (central) moments., 16 pages

International audience; List of the courses:- A Gentle Introduction to Analytic Combinatorics- Markov Chains and Martingales applied to the analysis of random structures- Polya Urn Models - analytic and probabilistic approaches- Random Trees and Probabilities - Automata and Motif Statistics

Infinite random sequences of letters can be viewed as stochastic chains or as strings produced by a source, in the sense of information theory. The relationship between Variable Length Markov Chains (VLMC) and probabilistic dynamical sources is studied. We establish a probabilistic frame for context trees and VLMC and we prove that any VLMC is a dynamical source for which we explicitly build the mapping. On two examples, the ``comb'' and the ``bamboo blossom'', we find a necessary and sufficient condition for the existence and the unicity of a stationary probability measure for the VLMC. These two examples are detailed in order to provide the associated Dirichlet series as well as the generating functions of word occurrences., 45 pages, 15 figures

The fringe of a B-tree with parameter $m$ is considered as a particular P\'olya urn with $m$ colors. More precisely, the asymptotic behaviour of this fringe, when the number of stored keys tends to infinity, is studied through the composition vector of the fringe nodes. We establish its typical behaviour together with the fluctuations around it. The well known phase transition in P\'olya urns has the following effect on B-trees: for $m\leq 59$, the fluctuations are asymptotically Gaussian, though for $m\geq 60$, the composition vector is oscillating; after scaling, the fluctuations of such an urn strongly converge to a random variable $W$. This limit is $\mathbb C$-valued and it does not seem to follow any classical law. Several properties of $W$ are shown: existence of exponential moments, characterization of its distribution as the solution of a smoothing equation, existence of a density relatively to the Lebesgue measure on $\mathbb C$, support of $W$. Moreover, a few representations of the composition vector for various values of $m$ illustrate the different kinds of convergence.

The fringe of a B-tree with parameter $m$ is considered as a particular P��lya urn with $m$ colors. More precisely, the asymptotic behaviour of this fringe, when the number of stored keys tends to infinity, is studied through the composition vector of the fringe nodes. We establish its typical behaviour together with the fluctuations around it. The well known phase transition in P��lya urns has the following effect on B-trees: for $m\leq 59$, the fluctuations are asymptotically Gaussian, though for $m\geq 60$, the composition vector is oscillating; after scaling, the fluctuations of such an urn strongly converge to a random variable $W$. This limit is $\mathbb C$-valued and it does not seem to follow any classical law. Several properties of $W$ are shown: existence of exponential moments, characterization of its distribution as the solution of a smoothing equation, existence of a density relatively to the Lebesgue measure on $\mathbb C$, support of $W$. Moreover, a few representations of the composition vector for various values of $m$ illustrate the different kinds of convergence.

Consider a balanced non triangular two-color P\'olya-Eggenberger urn process, assumed to be large which means that the ratio sigma of the replacement matrix eigenvalues satisfies 1/2

Consider a balanced non triangular two-color P��lya-Eggenberger urn process, assumed to be large which means that the ratio sigma of the replacement matrix eigenvalues satisfies 1/2

We consider a two-color P��lya urn in the case when a fixed number $S$ of balls is added at each step. Assume it is a large urn that is, the second eigenvalue $m$ of the replacement matrix satisfies $1/2, Published in at http://dx.doi.org/10.1214/10-AAP696 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The present text is a synthesis of research papers in mathematics, dealing with algebraic geometry, analytic combinatorics and probabilities. The first part is about three-dimensional complex algebraic varieties. It begins with the computation of the singular cohomology of non complete smooth toric varieties under some topological assumption on their fans. Afterwards, we construct a toroidal model for any quotient-singularity, whose computation requires a precise combinatorial study of the action of all finite unitary groups on the projectif plane. The second part develops a "hybrid" adaptation of Darboux's method and of singularity analysis for the coefficients' asymptotic expansion of power series that admit a natural boundary. Numerous applications in analytic combinatorics are given, including the analysis of factorization algorithms for polynomials on finite fields that are used in symbolic computation and for error-correcting codes. The third part gives an answer to a conjecture on $m$-ary search trees that are fundamental data structures in computer science used in searching and sorting. To this end, we consider them as urn processes that can be generalized to so called Pòlya processes, whose general asymptotics is studied. In the last part, we give the construction of a random tree associated with the \emph{Chaos Game Representation} of DNA sequences used in bioinformatics and biomathematics. Results on the height's and insertion depth's asymptotics are established.; Ce travail est la synthèse de travaux de recherches en mathématiques, dont les thèmes sont empruntés à la géométrie algébrique, la combinatoire analytique et les probabilités. La première partie concerne les variétés algébriques complexes de dimension trois. On y présente un calcul de la cohomologie singulière de variétés toriques lisses non complètes, ainsi que la construction d'un modèle toroïdal des singularités-quotient, dont le calcul nécessite l'étude combinatoire fine de l'action des groupes finis de matrices unitaires sur le plan projectif. La deuxième partie développe une adaptation "hybride" de la méthode de Darboux et de l'analyse des singularités pour le développement asymptotique des coefficients d'une série entière dans certains cas de frontière naturelle d'analyticité. De nombreux exemples issus de l'analyse combinatoire sont ainsi traités, dont celui de l'analyse d'algorithmes de factorisation de polynômes sur les corps finis qui sont utilisés en calcul formel et pour les codes correcteurs d'erreurs. La troisième partie résout une conjecture sur les arbres $m$-aires de recherche qui sont une structure fondamentale de l'algorithmiques des ensembles de données. Le modèle considéré est un modèle d'urnes qui se généralise en la notion de processus aléatoires de Pòlya dont le comportement asymptotique général est étudié. Dans la quatrième partie, on construit un arbre aléatoire associé à la \emph{Chaos Game Representation} utilisée en bio-mathématique et en bio-informatique du génôme. Les asymptotiques de la hauteur et de la profondeur d'insertion de ces arbres y sont établies.

In this paper, we consider a possible representation of a DNA sequence in a quaternary tree, in which one can visualize repetitions of subwords (seen as suffixes of subsequences) The CGR-tree turns a sequence of letters into a Digital Search Tree (DST), obtained from the suffixes of the reversed sequence Several results are known concerning the height, the insertion depth for DST built from independent successive random sequences having the same distribution Here the successive inserted words are strongly dependent We give the asymptotic behaviour of the insertion depth and length of branches for the CGR-tree obtained from the suffixes of a reversed i.i.d. or Markovian sequence As a by-product, asymptotic results on the length of longest runs in a Markovian sequence are obtained