Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom tree recursions: which fixed points correspond to tangible sets of trees?
153
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{B}$ be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only if its root has children $u$ and $v$ such that the subtrees rooted at $u$ and $v$ belong to it. Let $p$ be the probability that a Galton-Watson tree falls in $mathcal{B}$. The metaproperty makes $p$ satisfy a fixed-point equation, which can have multiple solutions. One of these solutions is $p$, but what is the meaning of the others? In particular, are they probabilities of the Galton-Watson tree falling into other sets satisfying the same metaproperty? We create a framework for posing questions of this sort, and we classify solutions to fixed-point equations according to whether they admit probabilistic interpretations. Our proofs use spine decompositions of Galton-Watson trees and the analysis of Boolean functions.
rate research
Read More
For each $n ge 1$, let $mathrm{d}^n=(d^{n}(i),1 le i le n)$ be a sequence of positive integers with even sum $sum_{i=1}^n d^n(i) ge 2n$. Let $(G_n,T_n,Gamma_n)$ be uniformly distributed over the set of simple graphs $G_n$ with degree sequence $mathrm{d}^n$, endowed with a spanning tree $T_n$ and rooted along an oriented edge $Gamma_n$ of $G_n$ which is not an edge of $T_n$. Under a finite variance assumption on degrees in $G_n$, we show that, after rescaling, $T_n$ converges in distribution to the Brownian continuum random tree as $n to infty$. Our main tool is a new version of Pitmans additive coalescent (https://doi.org/10.1006/jcta.1998.2919), which can be used to build both random trees with a fixed degree sequence, and random tree-weighted graphs with a fixed degree sequence. As an input to the proof, we also derive a Poisson approximation theorem for the number of loops and multiple edges in the superposition of a fixed graph and a random graph with a given degree sequence sampled according to the configuration model; we find this to be of independent interest.
We consider vector fixed point (FP) equations in large dimensional spaces involving random variables, and study their realization-wise solutions. We have an underlying directed random graph, that defines the connections between various components of the FP equations. Existence of an edge between nodes i, j implies the i th FP equation depends on the j th component. We consider a special case where any component of the FP equation depends upon an appropriate aggregate of that of the random neighbor components. We obtain finite dimensional limit FP equations (in a much smaller dimensional space), whose solutions approximate the solution of the random FP equations for almost all realizations, in the asymptotic limit (number of components increase). Our techniques are different from the traditional mean-field methods, which deal with stochastic FP equations in the space of distributions to describe the stationary distributions of the systems. In contrast our focus is on realization-wise FP solutions. We apply the results to study systemic risk in a large financial heterogeneous network with many small institutions and one big institution, and demonstrate some interesting phenomenon.
For a directed graph $G(V_n, E_n)$ on the vertices $V_n = {1,2, dots, n}$, we study the distribution of a Markov chain ${ {bf R}^{(k)}: k geq 0}$ on $mathbb{R}^n$ such that the $i$th component of ${bf R}^{(k)}$, denoted $R_i^{(k)}$, corresponds to the value of the process on vertex $i$ at time $k$. We focus on processes ${ {bf R}^{(k)}: k geq 0}$ where the value of $R_i^{(k+1)}$ depends only on the values ${ R_j^{(k)}: j to i}$ of its inbound neighbors, and possibly on vertex attributes. We then show that, provided $G(V_n, E_n)$ converges in the local weak sense to a marked Galton-Watson process, the dynamics of the process for a uniformly chosen vertex in $V_n$ can be coupled, for any fixed $k$, to a process ${ mathcal{R}_emptyset^{(r)}: 0 leq r leq k}$ constructed on the limiting marked Galton-Watson tree. Moreover, we derive sufficient conditions under which $mathcal{R}^{(k)}_emptyset$ converges, as $k to infty$, to a random variable $mathcal{R}^*$ that can be characterized in terms of the attracting endogenous solution to a branching distributional fixed-point equation. Our framework can also be applied to processes ${ {bf R}^{(k)}: k geq 0}$ whose only source of randomness comes from the realization of the graph $G(V_n, E_n)$.
We prove non-asymptotic stretched exponential tail bounds on the height of a randomly sampled node in a random combinatorial tree, which we use to prove bounds on the heights and widths of random trees from a variety of models. Our results allow us to prove a conjecture and settle an open problem of Janson (https://doi.org/10.1214/11-PS188), and nearly prove another conjecture and settle another open problem from the same work (up to a polylogarithmic factor). The key tool for our work is an equivalence in law between the degrees along the path to a random node in a random tree with given degree statistics, and a random truncation of a size-biased ordering of the degrees of such a tree. We also exploit a Poissonization trick introduced by Camarri and Pitman (https://doi.org/10.1214/EJP.v5-58) in the context of inhomogeneous continuum random trees, which we adapt to the setting of random trees with fixed degrees. Finally, we propose and justify a change to the conventions of branching process nomenclature: the name Galton-Watson trees should be permanently retired by the community, and replaced with the name Bienayme trees.
We consider fixed-point equations for probability measures charging measured compact metric spaces that naturally yield continuum random trees. On the one hand, we study the existence/uniqueness of the fixed-points and the convergence of the corresponding iterative schemes. On the other hand, we study the geometric properties of the random measured real trees that are fixed-points, in particular their fractal properties. We obtain bounds on the Minkowski and Hausdorff dimension, that are proved tight in a number of applications, including the very classical continuum random tree, but also for the dual trees of random recursive triangulations of the disk introduced by Curien and Le Gall [Ann Probab, vol. 39, 2011]. The method happens to be especially efficient to treat cases for which the mass measure on the real tree induced by natural encodings only provides weak estimates on the Hausdorff dimension.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
