Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelf-similar real trees defined as fixed-points and their geometric properties
209
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
Forman et al. (2020+) constructed $(alpha,theta)$-interval partition evolutions for $alphain(0,1)$ and $thetage 0$, in which the total sums of interval lengths (total mass) evolve as squared Bessel processes of dimension $2theta$, where $thetage 0$ acts as an immigration parameter. These evolutions have pseudo-stationary distributions related to regenerative Poisson--Dirichlet interval partitions. In this paper we study symmetry properties of $(alpha,theta)$-interval partition evolutions. Furthermore, we introduce a three-parameter family ${rm SSIP}^{(alpha)}(theta_1,theta_2)$ of self-similar interval partition evolutions that have separate left and right immigration parameters $theta_1ge 0$ and $theta_2ge 0$. They also have squared Bessel total mass processes of dimension $2theta$, where $theta=theta_1+theta_2-alphage-alpha$ covers emigration as well as immigration. Under the constraint $max{theta_1,theta_2}gealpha$, we prove that an ${rm SSIP}^{(alpha)}(theta_1,theta_2)$-evolution is pseudo-stationary for a new distribution on interval partitions, whose ranked sequence of lengths has Poisson--Dirichlet distribution with parameters $alpha$ and $theta$, but we are unable to cover all parameters without developing a limit theory for composition-valued Markov chains, which we do in a sequel paper.
Decision trees are popular machine learning models that are simple to build and easy to interpret. Even though algorithms to learn decision trees date back to almost 50 years, key properties affecting their generalization error are still weakly bounded. Hence, we revisit binary decision trees on real-valued features from the perspective of partitions of the data. We introduce the notion of partitioning function, and we relate it to the growth function and to the VC dimension. Using this new concept, we are able to find the exact VC dimension of decision stumps, which is given by the largest integer $d$ such that $2ell ge binom{d}{leftlfloorfrac{d}{2}rightrfloor}$, where $ell$ is the number of real-valued features. We provide a recursive expression to bound the partitioning functions, resulting in a upper bound on the growth function of any decision tree structure. This allows us to show that the VC dimension of a binary tree structure with $N$ internal nodes is of order $N log(Nell)$. Finally, we elaborate a pruning algorithm based on these results that performs better than the CART algorithm on a number of datasets, with the advantage that no cross-validation is required.
Rooted, weighted continuum random trees are used to describe limits of sequences of random discrete trees. Formally, they are random quadruples $(mathcal{T},d,r,p)$, where $(mathcal{T},d)$ is a tree-like metric space, $rinmathcal{T}$ is a distinguished root, and $p$ is a probability measure on this space. The underlying branching structure is carried implicitly in the metric $d$. We explore various ways of describing the interaction between branching structure and mass in $(mathcal{T},d,r,p)$ in a way that depends on $d$ only by way of this branching structure. We introduce a notion of mass-structure equivalence and show that two rooted, weighted $mathbb{R}$-trees are equivalent in this sense if and only if the discrete hierarchies derived by i.i.d. sampling from their weights, in a manner analogous to Kingmans paintbox, have the same distribution. We introduce a family of trees, called interval partition trees that serve as representatives of mass-structure equivalence classes, and which naturally represent the laws of the aforementioned hierarchies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
