Degree distribution of the greatest common divisor of polynomials over 𝔽q

We study the degree distribution of the greatest common divisor of two or more random polynomials over a finite field ??_q. We provide estimates for several parameters like number of distinct common irreducible factors, number of irreducible factors counting repetitions, and total degree of the gcd of two or more polynomials. We show that the limiting distribution of a random variable counting the total degree of the gcd is geometric and that the distributions of random variables counting the number of common factors (with and without repetitions) are very close to Poisson distributions when q is large. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Asymptotic Joint Normality of Counts of Uncorrelated Motifs in Recursive Trees

We study the fringe of random recursive trees, by analyzing the joint distribution of the counts of uncorrelated motifs. Our approach allows for finite and countably infinite collections. To be able to deal with the collection when it is infinitely countable, we use measure-theoretic themes. Each member of a collection of motifs occurs a certain number of times on the fringe. We show that these numbers, under appropriate normalization, have a limiting joint multivariate normal distribution. We give a complete characterization of the asymptotic covariance matrix. The methods of proof include contraction in a metric space of distribution functions to a fixed-point solution (limit distribution). We discuss two examples: the finite collection of all possible motifs of size four, and the infinite collection of rooted stars. We conclude with remarks to compare fringe-analysis with matching motifs everywhere in the tree.     

Spectra of Large Random Trees

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity. Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees. We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree. For the linear preferential attachment model with parameter a>?1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by $n^{1/2\gamma_{a}}$ , where ?? _a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.     

Isolating a Leaf in Rooted Trees via Random Cuttings

We consider a recursive procedure for destroying rooted trees and isolating a leaf by removing a random edge and keeping the subtree, which does not contain the original root. For two tree families, the simply generated tree families and increasing tree families, we study here the number of random cuts that are necessary to isolate a leaf. We can show limiting distribution results of this parameter for simply generated trees and certain increasing trees. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

On the Distribution of the Number of Fixed Vectors for the Finite Classical Groups

Motivated by analogous results for the symmetric group and compact Lie groups, we study the distribution of the number of fixed vectors of a random element of a finite classical group. We determine the limiting moments of these distributions, and find exactly how large the rank of the group has to be in order for the moment to stabilize to its limiting value. The proofs require a subtle use of some q-series identities. We also point out connections with orthogonal polynomials.     

Free Energy Fluctuations for Directed Polymers in Random Media in 1 + 1 Dimension

We consider two models for directed polymers in space‐time independent random media (the O'Connell‐Yor semidiscrete directed polymer and the continuum directed random polymer) at positive temperature and prove their KPZ universality via asymptotic analysis of exact Fredholm determinant formulas for the Laplace transform of their partition functions. In particular, we show that for large time τ, the probability distributions for the free energy fluctuations, when rescaled by τ^1/3, converges to the GUE Tracy‐Widom distribution. We also consider the effect of boundary perturbations to the quenched random media on the limiting free energy statistics. For the semidiscrete directed polymer, when the drifts of a finite number of the Brownian motions forming the quenched random media are critically tuned, the statistics are instead governed by the limiting Baik–Ben Arous–Péché distributions from spiked random matrix theory. For the continuum polymer, the boundary perturbations correspond to choosing the initial data for the stochastic heat equation from a particular class, and likewise for its logarithm—the Kardar‐Parisi‐Zhang equation. The Laplace transform formula we prove can be inverted to give the one‐point probability distribution of the solution to these stochastic PDEs for the class of initial data. © 2014 Wiley Periodicals, Inc.     

On the limiting distribution of sample central moments

We investigate the limiting behavior of sample central moments, examining the special cases where the limiting (as the sample size tends to infinity) distribution is degenerate. Parent (non-degenerate) distributions with this property are called singular, and we show in this article that the singular distributions contain at most three supporting points. Moreover, using the delta-method, we show that the (second-order) limiting distribution of sample central moments from a singular distribution is either a multiple, or a difference of two multiples of independent Chi-square random variables with one degree of freedom. Finally, we present a new characterization of normality through the asymptotic independence of the sample mean and all sample central moments.

     

Properties of the limit shape for some last-passage growth models in random environments

We study directed last-passage percolation on the planar square lattice whose weights have general distributions, or equivalently, queues in series with general service distributions. Each row of the last-passage model has its own randomly chosen weight distribution. We investigate the limiting time constant close to the boundary of the quadrant. Close to the y-axis, where the number of random distributions averaged over stays large, the limiting time constant takes the same universal form as in the homogeneous model. But close to the x-axis we see the effect of the tail of the distribution of the random environment.     

The Polynomial Method for Random Matrices

We define a class of “algebraic” random matrices. These are random matrices for which the Stieltjes transform of the limiting eigenvalue distribution function is algebraic, i.e., it satisfies a (bivariate) polynomial equation. The Wigner and Wishart matrices whose limiting eigenvalue distributions are given by the semicircle law and the Marčenko–Pastur law are special cases. Algebraicity of a random matrix sequence is shown to act as a certificate of the computability of the limiting eigenvalue density function. The limiting moments of algebraic random matrix sequences, when they exist, are shown to satisfy a finite depth linear recursion so that they may often be efficiently enumerated in closed form. In this article, we develop the mathematics of the polynomial method which allows us to describe the class of algebraic matrices by its generators and map the constructive approach we employ when proving algebraicity into a software implementation that is available for download in the form of the RMTool random matrix “calculator” package. Our characterization of the closure of algebraic probability distributions under free additive and multiplicative convolution operations allows us to simultaneously establish a framework for computational (noncommutative) “free probability” theory. We hope that the tools developed allow researchers to finally harness the power of infinite random matrix theory.     

The compound Poisson distribution and return times in dynamical systems

Previously it has been shown that some classes of mixing dynamical systems have limiting return times distributions that are almost everywhere Poissonian. Here we study the behaviour of return times at periodic points and show that the limiting distribution is a compound Poissonian distribution. We also derive error terms for the convergence to the limiting distribution. We also prove a very general theorem that can be used to establish compound Poisson distributions in many other settings.     

The shape of random tanglegrams

A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.     

On the speed of a cookie random walk

We consider the model of the one-dimensional cookie random walk when the initial cookie distribution is spatially uniform and the number of cookies per site is finite. We give a criterion to decide whether the limiting speed of the walk is non-zero. In particular, we show that a positive speed may be obtained for just three cookies per site. We also prove a result on the continuity of the speed with respect to the initial cookie distribution.      

Confidence regional method of stochastic spanning tree problem

We consider a P model version of stochastic spanning tree problems with random edge costs. Parameters of underling probability distribution of edge costs are unknown and so they are estimated by a confidence region from statistical data. The problem is first transformed into a deterministic equivalent problem with a minimax type objective function and a confidence region of means and variances, since we assume normal distributions with respect to random edge costs. Our model reflects the situation that the maximum possible damage due to an unknown parameter should be minimized. We show the problem can be reduced to the deterministic equivalent problem of another stochastic spanning tree problem, which is already investigated by us. Thus, we can find an optimal spanning tree of the original problem very efficiently by this reduction.     

Birth and Death Chains on Finite Trees: Computing their Stationary Distribution and Hitting Times

Every birth and death chain on a finite tree can be represented as a random walk on the underlying tree endowed with appropriate conductances. We provide an algorithm that finds these conductances in linear time. Then, using the electric network approach, we find the values for the stationary distribution and for the expected hitting times between any two vertices in the tree. We show that our algorithms improve classical procedures: they do not exhibit ill-posedness and the orders of their complexities are smaller than those of traditional algorithms found in the literature.     

Random cutting and records in deterministic and random trees

We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On the rate of convergence of the distributions of certain statistics to the Laplace and student distributions

This work deals with asymptotically normal statistics. If the size of sample is replaced by a random variable that is the maximum of n independent random variables with Pareto discrete distribution, then the distribution of these statistics is asymptotically Laplacian. If the size of the sample is replaced by a random variable with negative binomial distribution, then the distribution of these statistics is asymptotically a Student distribution. In the present study, the rates of convergences of these statistics’ distributions to the corresponding limiting distributions are estimated and the constants from expressions for estimating the rates are determined more accurately.     

經驗分佈之比的極限分佈

<正> §1.引言 令x為一隨機變數,其分佈函數為F(x).對於x作n次相互獨立的试驗,便得n個結果x_1,x_2,…,x_n.我們也可以把x_1,x_2,…,x_n看作是遵循同一個分佈函數F(x)的相互獨立隨機變數.現在把x_1,x_2,…,x_n依其值由小到大的次序排列,我們得到     

广义Lorenz 曲线的非参数统计推断

本文讨论了广义Lorenz 曲线的经验似然统计推断. 在简单随机抽样、分层随机抽样和整群随机抽样下, 本文分别定义了广义Lorenz 坐标的pro le 经验似然比统计量, 得出这些经验似然比的极限分布为带系数的自由度为1 的χ² 分布. 对于整个Lorenz 曲线, 基于经验似然方法类似地得出相应的极限过程. 根据所得的经验似然理论, 本文给出了bootstrap 经验似然置信区间构造方法, 并通过数据模拟, 对新给出的广义Lorenz 坐标的bootstrap 经验似然置信区间与渐近正态置信区间以及bootstrap 置信区间等进行了对比研究. 对整个Lorenz 曲线, 基于经验似然方法对其置信域也进行了模拟研究. 最后我们将所推荐的置信区间应用到实例中.     

A graphon approach to limiting spectral distributions of Wigner‐type matrices

We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsity ω(1/n): inhomogeneous random graphs with roughly equal expected degrees, W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results.     

On the structure of random plane-oriented recursive trees and their branches

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Pólya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.