随机二叉搜索树的子树

本文讨论随机二叉搜索树上不同大小的子树和与给定某个二叉树同构的子树. 利用递归分布等式,　我们得出了它们各自数目的期望和方差\bd 最后, 用压缩法得出了它们的中心极限定理.     

On Weighted Depths in Random Binary Search Trees

Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133–141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.     

Profile of Random Exponential Binary Trees

We introduce the random exponential binary tree (EBT) and study its profile. As customary, the tree is extended by padding each leaf node (considered internal), with the appropriate number of external nodes, so that the outdegree of every internal node is made equal to 2. In a random EBT, at every step, each external node is promoted to an internal node with probability p, stays unchanged with probability 1 - p, and the resulting tree is extended. We study the internal and external profiles of a random EBT and get exact expectations for the numbers of internal and external nodes at each level. Asymptotic analysis shows that the average external profile is richest at level \(\frac {2p}{p+1}n\), and it experiences phase transitions at levels a n, where the a’s are the solutions to an algebraic equation. The rates of convergence themselves go through an infinite number of phase changes in the sublinear range, and then again at the nearly linear levels.     

Random Minimum Length Spanning Trees in Regular Graphs

r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

On the Combinatorics of Rooted Binary Phylogenetic Trees

We study subtree-prune-and-regraft (SPR) operations on leaf-labelled rooted binary trees, also known as rooted binary phylogenetic trees. This study is motivated by the problem of graphically representing evolutionary histories of biological sequences subject to recombination. We investigate some basic properties of the induced SPR-metric on the space of leaf-labelled rooted binary trees with n leaves. In contrast to the case of unrooted trees, the number |U(T)| of trees in which are one SPR operation away from a given tree depends on the topology of T. In this paper, we construct recursion relations which allow one to determine the unit-neighbourhood size |U(T)| efficiently for any tree topology. In fact, using the recursion relations we are able to derive a simple closed-form formula for the unit-neighbourhood size. As a corollary, we construct sharp upper and lower bounds on the size of unit-neighbourhoods and investigate the diameter of . Lastly, we consider an enumeration problem relevant to population genetics.AMS Subject Classification: 05C05, 92D15.     

Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees

We study the joint probability distribution of the number of nodes of outdegree 0, 1, and 2 in a random recursive tree. We complete the known partial list of exact means and variances for outdegrees up to two by obtaining exact combinatorial expressions for the remaining means, variances, and covariances. The joint probability distribution of the number of nodes of outdegree 0, 1, and 2 is shown to be asymptotically trivariate normal and the asymptotic covariance structure is explicitly determined. It is also shown how to extend the results (at least in principle) to obtain a limiting multivariate normal distribution for nodes of outdegree 0, 1, …, k.     

Non-Universality of Nodal Length Distribution for Arithmetic Random Waves

“Arithmetic random waves” are the Gaussian Laplace eigenfunctions on the two-dimensional torus (Rudnick and Wigman in Annales de l’Insitute Henri Poincaré 9(1):109–130, 2008; Krishnapur et al. in Annals of Mathematics (2) 177(2):699–737, 2013). In this paper we find that their nodal length converges to a non-universal (non-Gaussian) limiting distribution, depending on the angular distribution of lattice points lying on circles. Our argument has two main ingredients. An explicit derivation of the Wiener–Itô chaos expansion for the nodal length shows that it is dominated by its 4th order chaos component (in particular, somewhat surprisingly, the second order chaos component vanishes). The rest of the argument relies on the precise analysis of the fourth order chaotic component.     

Left and Right Length of Paths in Binary Trees or on a Question of Knuth

We consider extended binary trees and study the joint right and left depth of leaf j, where the leaves are labelled from left to right by 0, 1, . . . , n, and the joint right and left external pathlength of binary trees of size n. Under the random tree model, i.e., the Catalan model, we characterize the joint limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf j in a random size-n binary tree when j ~ ρn with 0 < ρ > 1, as well as the joint limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-n binary tree. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

完全二叉树理论的计算复杂度

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

Imbalance in Random Digital Trees

The imbalance factor of the nodes containing keys in a trie (a sort of digital trees) is investigated. Accurate asymptotics for the mean are derived for a randomly chosen key in the trie via poissonization and the Mellin transform, and the inverse of the two operations. It is also shown from an analysis of the moving poles of the Mellin transform of the poissonized moment generating function that the imbalance factor (under appropriate centering and scaling) follows a Gaussian limit law.      

On the Spectral Distribution of Gaussian Random Matrices

We consider the empirical spectral distribution （ESD） of a random matrix from the Gaussian Unitary Ensemble. Based on the Plancherel-Rotaeh approximation formula for Hermite polynomials, we prove that the expected empirical spectral distribution converges at the rate of O（n^-1） to the Wigner distribution function uniformly on every compact intervals [u,v] within the limiting support （-1, 1）. Furthermore, the variance of the ESD for such an interval is proved to be （πn）^-2 logn asymptotically which surprisingly enough, does not depend on the details （e.g. length or location） of the interval, This property allows us to determine completely the covariance function between the values of the ESD on two intervals.     

On the Distribution of Random Samples from Finite Populations of Random Variables

This article deals with probability distributions of sums of simple random sample and Bernoulli sample when samples are selected from finite population of independent random variables. Random variables are quasi-lattice. Probability distributions from class ? and Poisson distribution are used for approximation. Analogue of Cornish-Fisher transformation is obtained in case of limit distributions from class ?.     

全平面上的随机Dirichlet级数的值分布

对于无限级随机Dirichlet级数几乎每一条水平线都是无限级无例外小函数的强Borel线.     

关于DRCE随机变量渐近分布性质的探讨

本文讨论了ＤＲＣＥ随机变量渐近正态收敛速度的一致上、下界，并对一类特殊的ＤＲＣＥ随机变量，讨论了其退化情况的不变原理。     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

A Characterization of Joint Distribution of Two-Valued Random Variables and Its Applications

We obtain an explicit representation for joint distribution of two-valued random variables with given marginals and for a copula corresponding to such random variables. The results are applied to prove a characterization of r-independent two-valued random variables in terms of their mixed first moments. The characterization is used to obtain an exact estimate for the number of almost independent random variables that can be defined on a discrete probability space and necessary conditions for a sequence of r-independent random variables to be stationary.