Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLeaf multiplicity in a Bienayme-Galton-Watson tree
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This note defines a notion of multiplicity for nodes in a rooted tree and presents an asymptotic calculation of the maximum multiplicity over all leaves in a Bienayme-Galton-Watson tree with critical offspring distribution $xi$, conditioned on the tree being of size $n$. In particular, we show that if $S_n$ is the maximum multiplicity in a conditional Bienayme-Galton-Watson tree, then $S_n = Omega(log n)$ asymptotically in probability and under the further assumption that ${bf E}{2^xi} < infty$, we have $S_n = O(log n)$ asymptotically in probability as well. Explicit formulas are given for the constants in both bounds. We conclude by discussing links with an alternate definition of multiplicity that arises in the root-estimation problem.
rate research
Read More
We consider a biased random walk $X_n$ on a Galton-Watson tree with leaves in the sub-ballistic regime. We prove that there exists an explicit constant $gamma= gamma(beta) in (0,1)$, depending on the bias $beta$, such that $X_n$ is of order $n^{gamma}$. Denoting $Delta_n$ the hitting time of level $n$, we prove that $Delta_n/n^{1/gamma}$ is tight. Moreover we show that $Delta_n/n^{1/gamma}$ does not converge in law (at least for large values of $beta$). We prove that along the sequences $n_{lambda}(k)=lfloor lambda beta^{gamma k}rfloor$, $Delta_n/n^{1/gamma}$ converges to certain infinitely divisible laws. Key tools for the proof are the classical Harris decomposition for Galton-Watson trees, a new variant of regeneration times and the careful analysis of triangular arrays of i.i.d. heavy-tailed random variables.
In [1] a detailed analysis was given of the large-time asymptotics of the total mass of the solution to the parabolic Anderson model on a supercritical Galton-Watson random tree with an i.i.d. random potential whose marginal distribution is double-exponential. Under the assumption that the degree distribution has bounded support, two terms in the asymptotic expansion were identified under the quenched law, i.e., conditional on the realisation of the random tree and the random potential. The second term contains a variational formula indicating that the solution concentrates on a subtree with minimal degree according to a computable profile. The present paper extends the analysis to degree distributions with unbounded support. We identify the weakest condition on the tail of the degree distribution under which the arguments in [1] can be pushed through. To do so we need to control the occurrence of large degrees uniformly in large subtrees of the Galton-Watson tree.
In this paper we study the vertex cut-trees of Galton-Watson trees conditioned to have $n$ leaves. This notion is a slight variation of Dieuleveuts vertex cut-tree of Galton-Watson trees conditioned to have $n$ vertices. Our main result is a joint Gromov-Hausdorff-Prokhorov convergence in the finite variance case of the Galton-Watson tree and its vertex cut-tree to Bertoin and Miermonts joint distribution of the Brownian CRT and its cut-tree. The methods also apply to the infinite variance case, but the problem to strengthen Dieuleveuts and Bertoin and Miermonts Gromov-Prokhorov convergence to Gromov-Hausdorff-Prokhorov remains open for their models conditioned to have $n$ vertices.
We are concerned with exploring the probabilities of first order statements for Galton-Watson trees with $Poisson(c)$ offspring distribution. Fixing a positive integer $k$, we exploit the $k$-move Ehrenfeucht game on rooted trees for this purpose. Let $Sigma$, indexed by $1 leq j leq m$, denote the finite set of equivalence classes arising out of this game, and $D$ the set of all probability distributions over $Sigma$. Let $x_{j}(c)$ denote the true probability of the class $j in Sigma$ under $Poisson(c)$ regime, and $vec{x}(c)$ the true probability vector over all the equivalence classes. Then we are able to define a natural recursion function $Gamma$, and a map $Psi = Psi_{c}: D rightarrow D$ such that $vec{x}(c)$ is a fixed point of $Psi_{c}$, and starting with any distribution $vec{x} in D$, we converge to this fixed point via $Psi$ because it is a contraction. We show this both for $c leq 1$ and $c > 1$, though the techniques for these two ranges are quite different.
At each site of a supercritical Galton-Watson tree place a parking spot which can accommodate one car. Initially, an independent and identically distributed number of cars arrive at each vertex. Cars proceed towards the root in discrete time and park in the first available spot they come to. Let $X$ be the total number of cars that arrive to the root. Goldschmidt and Przykucki proved that $X$ undergoes a phase transition from being finite to infinite almost surely as the mean number of cars arriving to each vertex increases. We show that $EX$ is finite at the critical threshold, describe its growth rate above criticality, and prove that it increases as the initial car arrival distribution becomes less concentrated. For the canonical case that either 0 or 2 cars arrive at each vertex of a $d$-ary tree, we give improved bounds on the critical threshold and show that $P(X = 0)$ is discontinuous.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
