| Título: | Novel characteristics of split trees by use of renewal theory |
| Autores: | Holmgren, Cecilia Ingrid; Cambridge University |
| Fecha: | 2012-01-01 |
| Publicador: | Electronic journal of probability |
| Fuente: |
 |
| Tipo: | Peer-reviewed Article |
| Tema: |
Random Trees, Split Trees, Renewal Theory 05C05; 05C80; 68W40; 68P10;68R10; 60C05; 68P05 |
| Descripción: | We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e.g., binary search trees, $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n balls (which often represent data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In Devroye [SIAM J Comput 28, 409-432, 1998] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth $\ln n/\mu+O(\ln n)^{1/2})$, where $\mu$ is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of nodes with depths $\geq \mu^{-1}\ln n-(\ln n)^{1/2+\epsilon}$ or depths $\leq\mu^{-1}\ln n+(\ln n)^{1/2+\epsilon}$ for any choice of $\epsilon>0$. We also find the first asymptotic of the variances of the depths of the balls in the tree. |
| Idioma: | Inglés |
1 Lévy Classes and Self-Normalization por Khoshnevisan, Davar; University of Utah | 6 Time-Space Analysis of the Cluster-Formation in Interacting Diffusions por Fleischmann, Klaus; Weierstrass Institute for Applied Analysis and Stochastics,Greven, Andreas; Universitat Erlangen-Nurnberg |
2 Hausdorff Dimension of Cut Points for Brownian Motion por Lawler, Gregory F.; Duke University and Cornell University | 7 Conditional Moment Representations for Dependent Random Variables por Bryc, Wlodzimierz; University of Cincinnati |
3 Eigenvalue Expansions for Brownian Motion with an Application to Occupation Times por Bass, Richard F.; University of Washington,Burdzy, Krzysztof; University of Washington | 8 Almost Sure Exponential Stability of Neutral Differential Difference Equations with Damped Stochastic Perturbations por Liao, Xiao Xin; University of Strathclyde,Mao, Xuerong; University of Strathclyde |
4 Random Discrete Distributions Derived from Self-Similar Random Sets por Pitman, Jim; University of California, Berkeley,Yor, Marc; Université Pierre et Marie Curie | 9 Quantitative Bounds for Convergence Rates of Continuous Time Markov Processes por Roberts, Gareth O.; University of Cambridge,Rosenthal, Jeffrey S.; University of Toronto |
5 A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences por Seppäläinen, Timo; Iowa State University | 10 Metastability of the Three Dimensional Ising Model on a Torus at Very Low Temperatures por Ben Arous, Gérard; Ecole Normale Supérieure,Cerf, Raphaël; Université Paris Sud |