اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدUniversal height and width bounds for random trees
137
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
In this paper we study height fluctuations of random lozenge tilings of polygonal domains on the triangular lattice through nonintersecting Bernoulli random walks. For a large class of polygons which have exactly one horizontal upper boundary edge, w
e show that these random height functions converge to a Gaussian Free Field as predicted by Kenyon and Okounkov [28]. A key ingredient of our proof is a dynamical version of the discrete loop equations as introduced by Borodin, Guionnet and Gorin [5], which might be of independent interest.
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.
For an $ntimes n$ matrix $A_n$, the $rto p$ operator norm is defined as $$|A_n|_{rto p}:= sup_{boldsymbol{x} in mathbb{R}^n:|boldsymbol{x}|_rleq 1 } |A_nboldsymbol{x}|_pquadtext{for}quad r,pgeq 1.$$ For different choices of $r$ and $p$, this norm cor
responds to key quantities that arise in diverse applications including matrix condition number estimation, clustering of data, and finding oblivious routing schemes in transportation networks. This article considers $rto p$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of ErdH{o}s-Renyi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1< pleq r< infty$, the asymptotic normality, as $ntoinfty$, of the appropriately centered and scaled norm $|A_n|_{rto p}$ is established. When $p geq 2$, this is shown to imply, as a corollary, asymptotic normality of the solution to the $ell_p$ quadratic maximization problem, also known as the $ell_p$ Grothendieck problem. Furthermore, a sharp $ell_infty$-approximation bound for the unique maximizing vector in the definition of $|A_n|_{rto p}$ is obtained. This result, which may be of independent interest, is in fact shown to hold for a broad class of deterministic sequences of matrices having certain asymptotic expansion properties. The results obtained can be viewed as a generalization of the seminal results of F{u}redi and Koml{o}s (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices, which corresponds to the special case $r=p=2$ considered here. In the general case with $1< pleq r < infty$, spectral methods are no longer applicable, and so a new approach is developed, which involves a refined convergence analysis of a nonlinear power method and a perturbation bound on the maximizing vector.
We consider the discrete-time threshold-$theta ge 2$ contact process on a random r-regular graph on n vertices. In this process, a vertex with at least theta occupied neighbors at time t will be occupied at time t+1 with probability p, and vacant oth
erwise. We show that if $theta ge 2$ and $r ge theta+2$, $epsilon_1$ is small and p is at least $p_1(epsilon_1)$, then starting from all vertices occupied the fraction of occupied vertices stays above $1-2epsilon_1$ up to time $exp(gamma_1(r)n)$ with probability at least $1 - exp(-gamma_1(r)n)$. In the other direction, we show that for $p_2 < 1$ there is an $epsilon_2(p_2)>0$ so that if $p le p_2$ and the number of occupied vertices in the initial configuration is at most $epsilon_2(p_2)n$, then with high probability all vertices are vacant at time $C_2(p_2) log(n)$. These two conclusions imply that on the random r-regular graph there cannot be a quasi-stationary distribution with density of occupied vertices between 0 and $epsilon_2(p_1)$, and allow us to conclude that the process on the r-tree has a first order phase transition.
Consider a uniformly sampled random $d$-regular graph on $n$ vertices. If $d$ is fixed and $n$ goes to $infty$ then we can relate typical (large probability) properties of such random graph to a family of invariant random processes (called typical pr
ocesses) on the infinite $d$-regular tree $T_d$. This correspondence between ergodic theory on $T_d$ and random regular graphs is already proven to be fruitful in both directions. This paper continues the investigation of typical processes with a special emphasis on entropy. We study a natural notion of micro-state entropy for invariant processes on $T_d$. It serves as a quantitative refinement of the notion of typicality and is tightly connected to the asymptotic free energy in statistical physics. Using entropy inequalities, we provide new sufficient conditions for typicality for edge Markov processes. We also extend these notions and results to processes on unimodular Galton-Watson random trees.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
