Random Structures and Algorithms · 2008 · 48 citations · 8 references
Natural SciencesMathematicsCombinatoricsProbability TheoryStochastic ProcessesLimit TheoremsProbabilistic CombinatoricsDiscrete Probability DistributionsDiscrete Random VariablesRandom TreesRecursionWeak Convergence Of Stochastic Processes
Abstract Let X n be the number of cuts needed to isolate the root in a random recursive tree with n vertices. We provide a weak convergence result for X n . The basic observation for its proof is that the probability distributions of $\{X_n: n=2,3,\ldots\}$ are recursively defined by $X_n {{\rm d}\atop{=}} X_{n-D_n} + 1, \; n=2,3,\ldots, \; X_1=0$ , where D n is a discrete random variable with ℙ ${\{ D_n = k \} = {1 \over {k(k+1)}} {n \over {n-1}}, \; k=1,2,\ldots, n-1}$ , which is independent of $(X_2,\ldots, X_n)$ . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009
8
On the analysis of stochastic divide and conquer algorithms
Uwe Rösler · Algorithmica · 2001 · 88 citations
A. Meir, J. W. Moon · Mathematical Biosciences · 1974 · 80 citations