共查询到20条相似文献,搜索用时 421 毫秒
1.
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. 相似文献
2.
In this paper, the continuous-time independent edge-Markovian random
graph process model is constructed. The authors also define the
interval isolated nodes of the random graph process, study the
distribution sequence of the number of isolated nodes and the
probability of having no isolated nodes when the initial
distribution of the random graph process is stationary distribution,
derive the lower limit of the probability in which two arbitrary
nodes are connected and the random graph is also connected, and
prove that the random graph is almost everywhere connected when the
number of nodes is sufficiently large. 相似文献
3.
Luc Devroye 《Random Structures and Algorithms》1991,2(3):303-315
Limit laws for several quantities in random binary search trees that are related to the local shape of a tree around each node can be obtained very simply by applying central limit theorems for w-dependent random variables. Examples include: the number of leaves (Ln), the number of nodes with k descendants (k fixed), the number of nodes with no left child, the number of nodes with k left descendants. Some of these results can also be obtained via the theory of urn models, but the present method seems easier to apply. 相似文献
4.
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. 相似文献
5.
Gabriel Berzunza 《Random Structures and Algorithms》2017,51(3):404-427
We destroy a finite tree of size n by cutting its edges one after the other and in uniform random order. Informally, the associated cut‐tree describes the genealogy of the connected components created by this destruction process. We provide a general criterion for the convergence of the rescaled cut‐tree in the Gromov‐Prohorov topology to an interval endowed with the Euclidean distance and a certain probability measure, when the underlying tree has branching points close to the root and height of order . In particular, we consider uniform random recursive trees, binary search trees, scale‐free random trees and a mixture of regular trees. This yields extensions of a result in Bertoin (Probab Stat 5 (2015), 478–488) for the cut‐tree of uniform random recursive trees and also allows us to generalize some results of Kuba and Panholzer (Online J Anal Combin (2014), 26) on the multiple isolation of vertices. The approach relies in the close relationship between the destruction process and Bernoulli bond percolation, which may be useful for studying the cut‐tree of other classes of trees. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 404–427, 2017 相似文献
6.
Shmerling Efraim Hochberg Kenneth J. 《Methodology and Computing in Applied Probability》2004,6(2):203-218
The problem of finding the probability distribution of the number of zeros in some real interval of a random polynomial whose coefficients have a given continuous joint density function is considered. An algorithm which enables one to express this probability as a multiple integral is presented. Formulas for the number of zeros of random quadratic polynomials and random polynomials of higher order, some coefficients of which are non-random and equal to zero, are derived via use of the algorithm. Finally, the applicability of these formulas in numerical calculations is illustrated. 相似文献
7.
设G为有限连通图.本文研究图G的子图空间G上的三类概率测度,它们分别刻画图的随机扩张树,随机扩张森林和随机连通子图.基于G上均匀扩张树的边负相关性,我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图.此外,我们还给出一定条件下图上均匀扩张森林的边负相关性. 相似文献
8.
Yves Nievergelt 《Numerische Mathematik》1995,70(1):111-118
Summary. For real functions that cross the unit interval, the method of bisection converges linearly if, but only if, the point of crossing is a diadic number where the function does not vanish, or, except for finitely many digits, its binary expansion coincides with that of one third or two thirds. Otherwise, the order of convergence remains undefined. If the point of crossing is one of Borel's normal real numbers (Lebesgue's measure of all of which equals one), then the sequence of ratios of two consecutive errors accumulates simultaneously at zero, one half, and negative infinity. Thus, in every finite sequence of estimates from the bisection, the last estimate need not be more accurate than the first one. 相似文献
9.
In this article we study the one‐dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
10.
Federico Bassetti Fabrizio Leisen 《Methodology and Computing in Applied Probability》2011,13(3):475-486
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. 相似文献
11.
《Random Structures and Algorithms》2018,53(1):15-58
We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees). 相似文献
12.
We derive exact moments of the number of 2-protected nodes in binary search trees grown from random permutations. Furthermore, we show that a properly normalized version of this tree parameter converges to a Gaussian limit. 相似文献
13.
14.
Jean Jabbour‐Hattab 《Random Structures and Algorithms》2001,19(2):112-127
We establish an almost sure large deviations theorem for the depth of the external nodes of binary search trees (BSTs). To achieve this, a parametric family of martingales is introduced. This family also allows us to get asymptotic results on the number of external nodes at deepest level. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 112–127, 2001 相似文献
15.
本文将计算随机映射图的给定顶点集的任意分类的连接概率及其极限性质,导出随机映射图的连通分支个数的分布与渐进分布. 相似文献
16.
Nina Gantert 《Probability Theory and Related Fields》1994,98(1):7-20
Summary Using self-similarity of Brownian motion and its representation as a product measure on a binary tree, we construct a random sequence of probability measures which converges to the distribution of the Brownian bridge. We establish a large deviation principle for random fields on a binary tree. This leads to a class of probability measures with a certain self-similarity property. The same construction can be carried out forC[0, 1]-valued processes and we can describe, for instance, aC[0, 1]-valued Ornstein-Uhlenbeck process as a large deviation of Brownian sheet. 相似文献
17.
《Journal of Computational and Applied Mathematics》2005,181(2):364-387
Three random fragmentation of an interval processes are investigated. For each of them, there is a splitting probability and a probability not to split at each step of the fragmentation process whose overall effect is to stabilize the global number of splitting events. Some of their statistical features are studied in each case among which fragments’ size distribution, partition function, structure of the underlying random fragmentation tree, occurrence of a phase transition. In the first homogeneous model, splitting probability does not depend on fragments’ size at each step. In the next two fragmentation models, splitting probability is fragments’ length dependent. In the first such models, fragments further split with probability one if their sizes exceed some cutoff value only; in a second model considered, splitting probability of finite-size objects is assumed to increase algebraically with fragments’ size at each step. The impact of these dependencies on statistical properties of the resulting random partitions are studied. Several examples are supplied. 相似文献
18.
19.
Philippe Flajolet Xavier Gourdon Conrado Martínez 《Random Structures and Algorithms》1997,11(3):223-244
In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997 相似文献
20.
Svante Janson 《Random Structures and Algorithms》2020,56(4):1070-1116
We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph. 相似文献