Joint degree distributions of preferential attachment random graphs

Giant descendant trees, matchings, and independent sets in age-biased attachment graphs

We study two models of an age-biased graph process: the $\delta$ -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with m attachments for each of the incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for $m=1$ , to a limit whose distribution is a mixture of two beta distributions and a single beta distribution respectively, and that for $m>1$ the limit is 1. We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine – for each model and each greedy algorithm – both a limiting fraction of vertices involved and an almost sure convergence rate.

Single-Block Recursive Poisson–Dirichlet Fragmentations of Normalized Generalized Gamma Processes

Dong, Goldschmidt and Martin (2006) (DGM) showed that, for 0<α<1, and θ>−α, the repeated application of independent single-block fragmentation operators based on mass partitions following a two-parameter Poisson–Dirichlet distribution with parameters (α,1−α) to a mass partition having a Poisson–Dirichlet distribution with parameters (α,θ) leads to a remarkable nested family of Poisson—Dirichlet distributed mass partitions with parameters (α,θ+r) for r=0,1,2,⋯. Furthermore, these generate a Markovian sequence of α-diversities following Mittag-Leffler distributions, whose ratios lead to independent Beta-distributed variables. These Markov chains are referred to as Mittag-Leffler Markov chains and arise in the broader literature involving Pólya urn and random tree/graph growth models. Here we obtain explicit descriptions of properties of these processes when conditioned on a mixed Poisson process when it equates to an integer n, which has interpretations in a species sampling context. This is equivalent to obtaining properties of the fragmentation operations of (DGM) when applied to mass partitions formed by the normalized jumps of a generalized gamma subordinator and its generalizations. We focus primarily on the case where n=0,1.

Gibbs partitions, Riemann–Liouville fractional operators, Mittag–Leffler functions, and fragmentations derived from stable subordinators

Pitman (2003), and subsequently Gnedin and Pitman (2006), showed that a large class of random partitions of the integers derived from a stable subordinator of index $\alpha\in(0,1)$ have infinite Gibbs (product) structure as a characterizing feature. The most notable case are random partitions derived from the two-parameter Poisson–Dirichlet distribution, $\textrm{PD}(\alpha,\theta)$, whose corresponding $\alpha$-diversity/local time have generalized Mittag–Leffler distributions, denoted by $\textrm{ML}(\alpha,\theta)$. Our aim in this work is to provide indications on the utility of the wider class of Gibbs partitions as it relates to a study of Riemann–Liouville fractional integrals and size-biased sampling, and in decompositions of special functions, and its potential use in the understanding of various constructions of more exotic processes. We provide characterizations of general laws associated with nested families of $\textrm{PD}(\alpha,\theta)$ mass partitions that are constructed from fragmentation operations described in Dong et al. (2014). These operations are known to be related in distribution to various constructions of discrete random trees/graphs in [n], and their scaling limits. A centerpiece of our work is results related to Mittag–Leffler functions, which play a key role in fractional calculus and are otherwise Laplace transforms of the $\textrm{ML}(\alpha,\theta)$ variables. Notably, this leads to an interpretation within the context of $\textrm{PD}(\alpha,\theta)$ laws conditioned on Poisson point process counts over intervals of scaled lengths of the $\alpha$-diversity.

Rate of convergence for traditional Pólya urns

Consider a Pólya urn with balls of several colours, where balls are drawn sequentially and each drawn ball is immediately replaced together with a fixed number of balls of the same colour. It is well known that the proportions of balls of the different colours converge in distribution to a Dirichlet distribution. We show that the rate of convergence is $\Theta(1/n)$ in the minimal $L_p$ metric for any $p\in[1,\infty]$, extending a result by Goldstein and Reinert; we further show the same rate for the Lévy distance, while the rate for the Kolmogorov distance depends on the parameters, i.e. on the initial composition of the urn. The method used here differs from the one used by Goldstein and Reinert, and uses direct calculations based on the known exact distributions.

Dirichlet approximation of equilibrium distributions in Cannings models with mutation

Consider a haploid population of fixed finite size with a finite number of allele types and having Cannings exchangeable genealogy with neutral mutation. The stationary distribution of the Markov chain of allele counts in each generation is an important quantity in population genetics but has no tractable description in general. We provide upper bounds on the distributional distance between the Dirichlet distribution and this finite-population stationary distribution for the Wright–Fisher genealogy with general mutation structure and the Cannings exchangeable genealogy with parent independent mutation structure. In the first case, the bound is small if the population is large and the mutations do not depend too much on parent type; 'too much' is naturally quantified by our bound. In the second case, the bound is small if the population is large and the chance of three-mergers in the Cannings genealogy is small relative to the chance of two-mergers; this is the same condition to ensure convergence of the genealogy to Kingman's coalescent. These results follow from a new development of Stein's method for the Dirichlet distribution based on Barbour's generator approach and a probabilistic description of the semigroup of the Wright–Fisher diffusion due to Griffiths and Li (1983) and Tavaré (1984).