982 research outputs found
Mod-ϕ Convergence : normality zones and precise deviations
No full textIn this paper, we use the framework of mod- convergence to prove precise large or moderate deviations for quite general sequences of random variables (). The random variables considered can be lattice or non-lattice distributed, and single or multi-dimensional; and one obtains precise estimates of the fluctuations , instead of the usual estimates for the rate of exponential decay log(In the special setting of mod-Gaussian convergence, we shall see that our approach allows us to identify the scale at which the central limit theorem ceases to hold and we are able to quantify the "breaking of symmetry" at this critical scale thanks to the residue or limiting function occurring in mod-f convergence. In particular this provides us with a systematic way to characterise the normality zone, that is the zone in which the Gaussian approximation for the tails is still valid. Besides, the residue function measures the extent to which this approximation fails to hold at the edge of the normality zone.
The first sections of the article are devoted to a proof of these abstract results. We then propose new examples covered by this theory and coming from various areas of mathematics: classical probability theory (multi-dimensional random walks, random point processes), number theory (statistics of additive arithmetic functions), combinatorics (statistics of random permutations), random matrix theory (characteristic polynomials of random matrices in compact Lie groups), graph theory (number of subgraphs in a random Erd˝os-Rényi graph), and non-commutative probability theory (asymptotics of random character values of symmetric groups). In particular, we complete our theory of precise deviations by a concrete method of cumulants and dependency graphs, which applies to many examples of sums of “weakly dependent” random variables. Although the latter methods can only be applied in the more restrictive setting of mod-Gaussian convergence, the large number as well as the variety of examples which are covered there hint at a universality class for second order fluctuations
Binary Search Trees of Permuton Samples
No full textBinary search trees (BST) are a popular type of structure when dealing with ordered data. They allow efficient access and modification of data, with their height corresponding to the worst retrieval time. From a probabilistic point of view, BSTs associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform permutation.
We consider here the case where the input comes from i.i.d. random points in the plane with law μ, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree only depends on the behavior of the measure μ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures μ. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates
An edge-weighted hook formula for labelled trees
No full textA number of hook formulas and hook summation formulas have previously appeared, involving various classes of trees. One of these classes of trees is rooted trees with labelled vertices, in which the labels increase along every chain from the root vertex to a leaf. In this paper we give a new hook summation formula for these (unordered increasing) trees, by introducing a new set of indeterminates indexed by pairs of vertices, that we call edge weights. This new result generalizes a previous result by Féray and Goulden, that arose in the context of representations of the symmetric group via the study of Kerov’s character polynomials. Our proof is by means of a combinatorial bijection that is a generalization of the Prüfer code for labelled trees
An edge-weighted hook formula for labelled trees
No full textInternational audienceA number of hook formulas and hook summation formulas have previously appeared, involving various classes of trees. One of these classes of trees is rooted trees with labelled vertices, in which the labels increase along every chain from the root vertex to a leaf. In this paper we give a new hook summation formula for these (unordered increasing) trees, by introducing a new set of indeterminates indexed by pairs of vertices, that we call edge weights. This new result generalizes a previous result by Féray and Goulden, that arose in the context of representations of the symmetric group via the study of Kerov's character polynomials. Our proof is by means of a combinatorial bijection that is a generalization of the Prüfer code for labelled trees
Asymptotic behavior of some statistics in Ewens random permutations
No full text32 pages: final version for EJP, produced by the author. An extended abstract of 12 pages, published in the proceedings of AofA 2012, is also available as version 3.International audienceThe purpose of this article is to present a general method to find limiting laws for some renormalized statistics on random permutations. The model considered here is Ewens sampling model, which generalizes uniform random permutations. We describe the asymptotic behavior of a large family of statistics, including the number of occurrences of any given dashed pattern. Our approach is based on the method of moments and relies on the following intuition: two events involving the images of different integers are almost independent
Asymptotic behavior of some statistics in Ewens random permutations
No full text32 pages: final version for EJP, produced by the author. An extended abstract of 12 pages, published in the proceedings of AofA 2012, is also available as version 3.International audienceThe purpose of this article is to present a general method to find limiting laws for some renormalized statistics on random permutations. The model considered here is Ewens sampling model, which generalizes uniform random permutations. We describe the asymptotic behavior of a large family of statistics, including the number of occurrences of any given dashed pattern. Our approach is based on the method of moments and relies on the following intuition: two events involving the images of different integers are almost independent
Cyclic inclusion-exclusion
No full textFollowing the lead of Stanley and Gessel, we consider a linear map which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as a multivariate generating series of nondecreasing functions on the graph. We describe the kernel of this linear map by using a simple combinatorial operation that we call cyclic inclusion-exclusion. Our result also holds for the natural noncommutative analogue and for the commutative and noncommutative restrictions to bipartite graphs. An application to the theory of Kerov character polynomials is given
Combinatorial interpretation and positivity of Kerov's character polynomials
No full textInternational audienceKerov's polynomials give irreducible character values of the symmetric group in term of the free cumulants of the associated Young diagram. Using a combinatorial approach with maps, we prove in this article a positivity result on their coefficients, which extends a conjecture of S. Kerov.Les polynômes de Kerov expriment les valeurs des caractères irréductibles du groupe symétrique en fonction des cumulants libres du diagramme de Young associé. Grâce à une approche combinatoire à base de cartes, nous prouvons dans cet article un résultat de positivité sur leurs coefficients, qui généralise une conjecture de S. Kerov
Weighted dependency graphs
No full textThe theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. In this article, we introduce a more general notion of weighted dependency graphs and give normality criteria in this context. We also provide generic tools to prove that some weighted graph is a weighted dependency graph for a given family of random variables. To illustrate the power of the theory, we give applications to the following objects: uniform random pair partitions, the random graph model , uniform random permutations, the symmetric simple exclusion process and multilinear statistics on Markov chains. The application to random permutations gives a bivariate extension of a functional central limit theorem of Janson and Barbour. On Markov chains, we answer positively an open question of Bourdon and Vallée on the asymptotic normality of subword counts in random texts generated by a Markovian source
Partial Jucys-Murphy elements and star factorizations
No full text12 pagesInternational audienceIn this paper, we look at the number of factorizations of a given permutation into star transpositions. In particular, we give a natural explanation of a hidden symmetry, answering a question of I.P. Goulden and D.M. Jackson. We also have a new proof of their explicit formula. Another result is the normalized class expansion of some central elements of the symmetric group algebra introduced by P. Biane. To obtain this results, we use natural analogs of Jucys-Murphy elements in the algebra of partial permutations of V. Ivanov and S. Kerov. We investigate their properties and use a formula of A. Lascoux and J.Y. Thibon to give the expansion of their power sums on the natural basis of the invariant subalgebra
- …
