Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEffective resistance of random trees
214
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
Let $mathcal{T}$ be a rooted tree endowed with the natural partial order $preceq$. Let $(Z(v))_{vin mathcal{T}}$ be a sequence of independent standard Gaussian random variables and let $alpha = (alpha_k)_{k=1}^infty$ be a sequence of real numbers with $sum_{k=1}^infty alpha_k^2<infty$. Set $alpha_0 =0$ and define a Gaussian process on $mathcal{T}$ in the following way: [ G(mathcal{T}, alpha; v): = sum_{upreceq v} alpha_{|u|} Z(u), quad v in mathcal{T}, ] where $|u|$ denotes the graph distance between the vertex $u$ and the root vertex. Under mild assumptions on $mathcal{T}$, we obtain a necessary and sufficient condition for the almost sure boundedness of the above Gaussian process. Our condition is also necessary and sufficient for the almost sure uniform convergence of the Gaussian process $G(mathcal{T}, alpha; v)$ along all rooted geodesic rays in $mathcal{T}$.
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.
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton-Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
