Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRecursive construction of continuum random trees
235
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
A modification of Koetter-Kschischang codes for random networks is presented (these codes were also studied by Wang et al. in the context of authentication problems). The new codes have higher information rate, while maintaining the same error-correcting capabilities. An efficient error-correcting algorithm is proposed for these codes.
Motivated by limits of critical inhomogeneous random graphs, we construct a family of sequences of measured metric spaces that we call continuous multiplicative graphs, that are expected to be the universal limit of graphs related to the multiplicative coalescent (the ErdH{o}s--Renyi random graph, more generally the so-called rank-one inhomogeneous random graphs of various types, and the configuration model). At the discrete level, the construction relies on a new point of view on (discrete) inhomogeneous random graphs that involves an embedding into a Galton--Watson forest. The new representation allows us to demonstrate that a processus that was already present in the pionnering work of Aldous [Ann. Probab., vol.~25, pp.~812--854, 1997] and Aldous and Limic [Electron. J. Probab., vol.~3, pp.~1--59, 1998] about the multiplicative coalescent actually also (essentially) encodes the limiting metric: The discrete embedding of random graphs into a Galton--Watson forest is paralleled by an embedding of the encoding process into a Levy process which is crucial in proving the very existence of the local time functionals on which the metric is based; it also yields a transparent approach to compactness and fractal dimensions of the continuous objects. In a companion paper, we show that the continuous Levy graphs are indeed the scaling limit of inhomogeneous random graphs.
A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element $U$. The value of the root is the key quantity of interest in general. In this first study, all node values and function values are in a finite set $S$. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on $S$, and the tree $T_n$ is a random Galton--Watson tree of size $n$.
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.
We study a generalisation of the random recursive tree (RRT) model and its multigraph counterpart, the uniform directed acyclic graph (DAG). Here, vertices are equipped with a random vertex-weight representing initial inhomogeneities in the network, so that a new vertex connects to one of the old vertices with a probability that is proportional to their vertex-weight. We first identify the asymptotic degree distribution of a uniformly chosen vertex for a general vertex-weight distribution. For the maximal degree, we distinguish several classes that lead to different behaviour: For bounded vertex-weights we obtain results for the maximal degree that are similar to those observed for RRTs and DAGs. If the vertex-weights have unbounded support, then the maximal degree has to satisfy the right balance between having a high vertex-weight and being born early. For vertex-weights in the Frechet maximum domain of attraction the first order behaviour of the maximal degree is random, while for those in the Gumbel maximum domain of attraction the leading order is deterministic. Surprisingly, in the latter case, the second order is random when considering vertices in a compact window in the optimal region, while it becomes deterministic when considering all vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
