Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA limit field for orthogonal range searches in two-dimensional random point search trees
57
0
0.0
(
0
)
Added by
Henning Sulzbach
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for $2$-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an old question of Chanzy, Devroye and Zamora-Cura [emph{Acta Inf.}, 37:355--383, 2000]
rate research
Read More
We consider a natural model of inhomogeneous random graphs that extends the classical ErdH os-Renyi graphs and shares a close connection with the multiplicative coalescence, as pointed out by Aldous [AOP 1997]. In this model, the vertices are assigned weights that govern their tendency to form edges. It is by looking at the asymptotic distributions of the masses (sum of the weights) of the connected components of these graphs that Aldous and Limic [EJP 1998] have identified the entrance boundary of the multiplicative coalescence, which is intimately related to the excursion lengths of certain Levy-type processes. We, instead, look at the metric structure of these components and prove their Gromov-Hausdorff-Prokhorov convergence to a class of random compact measured metric spaces that have been introduced in a companion paper. Our asymptotic regimes relate directly to the general convergence condition appearing in the work of Aldous and Limic. Our techniques provide a unified approach for this general critical regime, and relies upon two key ingredients: an encoding of the graph by some Levy process as well as an embedding of its connected components into Galton-Watson forests. This embedding transfers asymptotically into an embedding of the limit objects into a forest of Levy trees, which allows us to give an explicit construction of the limit objects from the excursions of the Levy-type process. The mains results combined with the ones in the other paper allow us to extend and complement several previous results that had been obtained via regime-specific proofs, for instance: the case of ErdH os-Renyi random graphs obtained by Addario-Berry, Goldschmidt and B. [PTRF 2012], the asymptotic homogeneous case as studied by Bhamidi, Sen and Wang [PTRF 2017], or the power-law case as considered by Bhamidi, Sen and van der Hofstad [PTRF 2018].
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).
We study Random Walks in an i.i.d. Random Environment (RWRE) defined on $b$-regular trees. We prove a functional central limit theorem (FCLT) for transient processes, under a moment condition on the environment. We emphasize that we make no uniform ellipticity assumptions. Our approach relies on regenerative levels, i.e. levels that are visited exactly once. On the way, we prove that the distance between consecutive regenerative levels have a geometrically decaying tail. In the second part of this paper, we apply our results to Linearly Edge-Reinforced Random Walk (LERRW) to prove FCLT when the process is defined on $b$-regular trees, with $ b ge 4$, substantially improving the results of the first author (see Theorem 3 of Collevecchio (2006)).
There have been several recent articles studying homology of various types of random simplicial complexes. Several theorems have concerned thresholds for vanishing of homology, and in some cases expectations of the Betti numbers. However little seems known so far about limiting distributions of random Betti numbers. In this article we establish Poisson and normal approximation theorems for Betti numbers of different kinds of random simplicial complex: ErdH{o}s-Renyi random clique complexes, random Vietoris-Rips complexes, and random v{C}ech complexes. These results may be of practical interest in topological data analysis.
We consider reversible random walks in random environment obtained from symmetric long--range jump rates on a random point process. We prove almost sure transience and recurrence results under suitable assumptions on the point process and the jump rate function. For recurrent models we obtain almost sure estimates on effective resistances in finite boxes. For transient models we construct explicit fluxes with finite energy on the associated electrical network.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
