Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVoronoi cells in random split trees
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the sizes of the Voronoi cells of $k$ uniformly chosen vertices in a random split tree of size $n$. We prove that, for $n$ large, the largest of these $k$ Voronoi cells contains most of the vertices, while the sizes of the remaining ones are essentially all of order $nexp(-mathrm{const}sqrt{log n})$. This discrepancy persists if we modify the definition of the Voronoi cells by (a) introducing random edge lengths (with suitable moment assumptions), and (b) assigning different influence parameters (called speeds in the paper) to each of the $k$ vertices. Our findings are in contrast to corresponding results on random uniform trees and on the continuum random tree, where it is known that the vector of the relative sizes of the $k$ Voronoi cells is asymptotically uniformly distributed on the $(k-1)$-dimensional simplex.
rate research
Read More
In this paper, we construct a new family of random series defined on $R^D$, indexed by one scaling parameter and two Hurst-like exponents. The model is close to Takagi-Knopp functions, save for the fact that the underlying partitions of $R^D$ are not the usual dyadic meshes but random Voronoi tessellations generated by Poisson point processes. This approach leads us to a continuous function whose random graph is shown to be fractal with explicit and equal box and Hausdorff dimensions. The proof of this main result is based on several new distributional properties of the Poisson-Voronoi tessellation on the one hand, an estimate of the oscillations of the function coupled with an application of a Frostman-type lemma on the other hand. Finally, we introduce two related models and provide in particular a box-dimension calculation for a derived deterministic Takagi-Knopp series with hexagonal bases.
We investigate the effective resistance $R_n$ and conductance $C_n$ between the root and leaves of a binary tree of height $n$. In this electrical network, the resistance of each edge $e$ at distance $d$ from the root is defined by $r_e=2^dX_e$ where the $X_e$ are i.i.d. positive random variables bounded away from zero and infinity. It is shown that $mathbf{E}R_n=nmathbf{E}X_e-(operatorname {mathbf{Var}}(X_e)/mathbf{E}X_e)ln n+O(1)$ and $operatorname {mathbf{Var}}(R_n)=O(1)$. Moreover, we establish sub-Gaussian tail bounds for $R_n$. We also discuss some possible extensions to supercritical Galton--Watson trees.
The Maki-Thompson rumor model is defined by assuming that a population represented by a graph is subdivided into three classes of individuals; namely, ignorants, spreaders and stiflers. A spreader tells the rumor to any of its nearest ignorant neighbors at rate one. At the same rate, a spreader becomes a stifler after a contact with other nearest neighbor spreaders, or stiflers. In this work we study the model on random trees. As usual we define a critical parameter of the model as the critical value around which the rumor either becomes extinct almost-surely or survives with positive probability. We analyze the existence of phase-transition regarding the survival of the rumor, and we obtain estimates for the mean range of the rumor. The applicability of our results is illustrated with examples on random trees generated from some well-known discrete distributions.
Consider a Voronoi tiling of the Euclidean space based on a realization of a inhomogeneous Poisson random set. A Voronoi polyomino is a finite and connected union of Voronoi tiles. In this paper we provide tail bounds for the number of boxes that are intersected by a Voronoi polyomino, and vice-versa. These results will be crucial to analyze self-avoiding paths, greedy polyominoes and first-passage percolation models on Voronoi tilings and on the dual graph, named the Delaunay triangulation.
We introduce a general recursive method to construct continuum random trees (CRTs) from independent copies of a random string of beads, that is, any random interval equipped with a random discrete probability measure, and from related structures. We prove the existence of these CRTs as a new application of the fixpoint method for recursive distribution equations formalised in high generality by Aldous and Bandyopadhyay. We apply this recursive method to show the convergence to CRTs of various tree growth processes. We note alternative constructions of existing self-similar CRTs in the sense of Haas, Miermont and Stephenson, and we give for the first time constructions of random compact R-trees that describe the genealogies of Bertoins self-similar growth fragmentations. In forthcoming work, we develop further applications to embedding problems for CRTs, providing a binary embedding of the stable line-breaking construction that solves an open problem of Goldschmidt and Haas.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
