Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal limit of the fixed point forest
53
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Consider the following partial sorting algorithm on permutations: take the first entry of the permutation in one-line notation and insert it into the position of its own value. Continue until the first entry is 1. This process imposes a forest structure on the set of all permutations of size $n$, where the roots are the permutations starting with 1 and the leaves are derangements. Viewing the process in the opposite direction towards the leaves, one picks a fixed point and moves it to the beginning. Despite its simplicity, this fixed point forest exhibits a rich structure. In this paper, we consider the fixed point forest in the limit $nto infty$ and show using Steins method that at a random permutation the local structure weakly converges to a tree defined in terms of independent Poisson point processes. We also show that the distribution of the length of the longest path to a leaf converges to the geometric distribution with mean $e-1$, and the length of the shortest path converges to the Poisson distribution with mean 1. In addition, the higher moments are bounded and hence the expectations converge as well.
rate research
Read More
We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer $k$, take a sequence of random (rooted) trees of increasing size, say $(t_n)_{nge 1}$, and label each of these random trees uniformly at random in order to get a random Boolean expression on $k$ variables. We prove that, under rather weak local conditions on the sequence of random trees $(t_n)_{nge 1}$, the distribution induced on Boolean functions by this procedure converges as $n$ tends to infinity. In particular, we characterise two different behaviours of this limit distribution depending on the shape of the local limit of $(t_n)_{nge 1}$: a degenerate case when the local limit has no leaves; and a non-degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton--Watson trees).
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.
Let $Y_i,igeq1$, be i.i.d. random variables having values in an $m$-dimensional manifold $mathcal {M}subset mathbb{R}^d$ and consider sums $sum_{i=1}^nxi(n^{1/m}Y_i,{n^{1/m}Y_j}_{j=1}^n)$, where $xi$ is a real valued function defined on pairs $(y,mathcal {Y})$, with $yin mathbb{R}^d$ and $mathcal {Y}subset mathbb{R}^d$ locally finite. Subject to $xi$ satisfying a weak spatial dependence and continuity condition, we show that such sums satisfy weak laws of large numbers, variance asymptotics and central limit theorems. We show that the limit behavior is controlled by the value of $xi$ on homogeneous Poisson point processes on $m$-dimensional hyperplanes tangent to $mathcal {M}$. We apply the general results to establish the limit theory of dimension and volume content estimators, R{e}nyi and Shannon entropy estimators and clique counts in the Vietoris-Rips complex on ${Y_i}_{i=1}^n$.
The Robbins-Monro algorithm is a recursive, simulation-based stochastic procedure to approximate the zeros of a function that can be written as an expectation. It is known that under some technical assumptions, a Gaussian convergence can be established for the procedure. Here, we are interested in the local limit theorem, that is, quantifying this convergence on the density of the involved objects. The analysis relies on a parametrix technique for Markov chains converging to diffusions, where the drift is unbounded.
We consider a particle undergoing Brownian motion in Euclidean space of any dimension, forced by a Gaussian random velocity field that is white in time and smooth in space. We show that conditional on the velocity field, the quenched density of the particle after a long time can be approximated pointwise by the product of a deterministic Gaussian density and a spacetime-stationary random field $U$. If the velocity field is additionally assumed to be incompressible, then $Uequiv 1$ almost surely and we obtain a local central limit theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
