Search results for "Binary tree"

Whom to befriend to influence people

2020

Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person $v$ in the network has a certain threshold $t(v)$ for {\em activation}, i.e adoption of the product or idea. If $v$ has at least $t(v)$ activated neighbors, then $v$ will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This {\em Minimum Links} Problem has applications in viral marketing and the study of epidemics. Its solution can be…

On the relative sizes of learnable sets

1998

Abstract Measure and category (or rather, their recursion-theoretical counterparts) have been used in theoretical computer science to make precise the intuitive notion “for most of the recursive sets”. We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

The pruning-grafting lattice of binary trees

2008

AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.

Skeletizing 3D-Objects by Projections

2004

Skeletization is used to simplify an object and to give an idea of the global shape of an object. This paper concerns the continuous domain. While many methods already exist, they are mostly applied in 2D-space. We present a new method to skeletize the polygonal approximation of a 3D-object, based on projections and 2D-skeletization from binary trees.

Local bandwidth selection for kernel density estimation in a bifurcating Markov chain model

2020

International audience; We propose an adaptive estimator for the stationary distribution of a bifurcating Markov Chain onRd. Bifurcating Markov chains (BMC for short) are a class of stochastic processes indexed by regular binary trees. A kernel estimator is proposed whose bandwidths are selected by a method inspired by the works of Goldenshluger and Lepski [(2011), 'Bandwidth Selection in Kernel Density Estimation: Oracle Inequalities and Adaptive Minimax Optimality',The Annals of Statistics3: 1608-1632). Drawing inspiration from dimension jump methods for model selection, we also provide an algorithm to select the best constant in the penalty. Finally, we investigate the performance of the…

MODERATE DEVIATION PRINCIPLES FOR BIFURCATING MARKOV CHAINS: CASE OF FUNCTIONS DEPENDENT OF ONE VARIABLE

2021

The main purpose of this article is to establish moderate deviation principles for additive functionals of bifurcating Markov chains. Bifurcating Markov chains are a class of processes which are indexed by a regular binary tree. They can be seen as the models which represent the evolution of a trait along a population where each individual has two offsprings. Unlike the previous results of Bitseki, Djellout \& Guillin (2014), we consider here the case of functions which depend only on one variable. So, mainly inspired by the recent works of Bitseki \& Delmas (2020) about the central limit theorem for general additive functionals of bifurcating Markov chains, we give here a moderate deviatio…

Right-arm rotation distance between binary trees

2003

We consider a transformation on binary trees, named right-arm rotation, which is a special instance of the well-known rotation transformation. Only rotations at nodes of the right arm of the trees are allowed. Using ordinal tools, we give an efficient algorithm for computing the right-arm rotation distance between two binary trees, i.e., the minimum number of rightarm rotations necessary to transform one tree into the other.

Short notes: Some Properties of the Rotation Lattice of Binary Trees

1988

MODERATE DEVIATION PRINCIPLES FOR KERNEL ESTIMATOR OF INVARIANT DENSITY IN BIFURCATING MARKOV CHAINS MODELS

2021

Bitseki and Delmas (2021) have studied recently the central limit theorem for kernel estimator of invariant density in bifurcating Markov chains models. We complete their work by proving a moderate deviation principle for this estimator. Unlike the work of Bitseki and Gorgui (2021), it is interesting to see that the distinction of the two regimes disappears and that we are able to get moderate deviation principle for large values of the ergodic rate. It is also interesting and surprising to see that for moderate deviation principle, the ergodic rate begins to have an impact on the choice of the bandwidth for values smaller than in the context of central limit theorem studied by Bitseki and …

CENTRAL LIMIT THEOREM FOR KERNEL ESTIMATOR OF INVARIANT DENSITY IN BIFURCATING MARKOV CHAINS MODELS

2021

Bifurcating Markov chains (BMC) are Markov chains indexed by a full binary tree representing the evolution of a trait along a population where each individual has two children. Motivated by the functional estimation of the density of the invariant probability measure which appears as the asymptotic distribution of the trait, we prove the consistence and the Gaussian fluctuations for a kernel estimator of this density based on late generations. In this setting, it is interesting to note that the distinction of the three regimes on the ergodic rate identified in a previous work (for fluctuations of average over large generations) disappears. This result is a first step to go beyond the thresh…