BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We revisit the problem of the estimation of the differential entropy H(f) of a random vector X in Rd with density f, assuming that H(f) exists and is finite. In this note, we study the consistency of the popular nearest neighbor estimate Hn of Kozachenko and Leonenko. Without any smoothness condition we show that the estimate is consistent (E{∣Hn−H(f)∣}→0 as n→∞) if and only if E{log(∥X∥+1)}<∞. Furthermore, if X has compact support, then Hn→H(f) almost surely.
This thesis presents analysis of the properties and run-time of the Rapidly-exploring Random Tree (RRT) algorithm. It is shown that the time for the RRT with stepsize ε to grow close to every point in the d-dimensional unit cube is Θ(εd1log(ε1)). Also, the time it takes for the tree to reach a region of positive probability is O(ε−23). Finally, a relationship is shown to the Nearest Neighbour Tree (NNT). This relationship shows that the total Euclidean path length after n steps is O(n) and the expected height of the tree is bounded above by (e+o(1))logn.
A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element U. The value of the root is the key quantity of interest in general. In this first study, all node values and function values are in a finite set S. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on S, and the tree Tn is a random Galton--Watson tree of size n.
Let G be an undirected graph with m edges and d vertices. We show that d-dimensional Ising models on G can be learned from n i.i.d. samples within expected total variation distance some constant factor of min{1,(m+d)/n}, and that this rate is optimal. We show that the same rate holds for the class of d-dimensional multivariate normal undirected graphical models with respect to G. We also identify the optimal rate of min{1,m/n} for Ising models with no external magnetic field.
We define the (random) k-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except now a node must be cut k times before it is destroyed. The first order terms of the expectation and variance of Xn, the k-cut number of a path of length n, are proved. We also show that Xn, after rescaling, converges in distribution to a limit Bk, which has a complicated representation. The paper then briefly discusses the k-cut number of some trees and general graphs. We conclude by some analytic results which may be of interest.
We study the conditions for families of subtrees to exist with high probability (whp) in a Galton-Walton tree of size n. We first give a Poisson approximation of fringe subtree counts, which yields the height of the maximal complete r-ary fringe subtree. Then we determine the maximal Kn such that every tree of size at most Kn appears as fringe subtree whp. Finally, we study non-fringe subtree counts and determine the height of the maximal complete r-ary non-fringe subtree.
In 1952, von Neumann introduced the rejection method for random variate generation. We revisit this algorithm when we have a source of perfect bits at our disposal. In this random bit model, there are universal lower bounds for generating a random variate with a given density to within an accuracy ε derived by Knuth and Yao, and refined by the authors. In general, von Neumann's method fails in this model. We propose a modification that insures proper behavior for all Riemann-integrable densities on compact sets, and show that the expected number of random bits needed behaves optimally with respect to universal lower bounds. In particular, we introduce the notion of an oracle that evaluates the supremum and infimum of a function on any rectangle of Rd, and develop a quadtree-style extension of the classical rejection method.
A deterministic finite automaton (DFA) of n states over a k-letter alphabet can be seen as a digraph with n vertices which all have exactly k labeled out-arcs (k-out digraph). In 1973 Grusho first proved that with high probability (whp) in a random k-out digraph there is a strongly connected component (SCC) of linear size that is reachable from all vertices, i.e., a giant. He also proved that the size of the giant follows a central limit law. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of overlapping tree-like structures. Thus the directed acyclic graph (DAG) of a random k-out digraph is almost the same as the digraph with the giant contracted into one vertex. These findings lead to a new, concise and self-contained proof of Grusho's theorem. This work also contains some other results including the structure outside the giant, the phase transition phenomenon in strong connectivity, the typical distance, and an extension to simple digraphs.
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than two decades and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n log n) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve on the prior art with a protocol that needs only O(n log n) bits of communication and O(log^2 n) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.
In this paper we explore maximal deviations of large random structures from their typical behavior. We introduce a model for a high-dimensional random graph process and ask analogous questions to those of Vapnik and Chervonenkis for deviations of averages: how "rich" does the process have to be so that one sees atypical behavior. In particular, we study a natural process of Erdős-Rényi random graphs indexed by unit vectors in Rd. We investigate the deviations of the process with respect to three fundamental properties: clique number, chromatic number, and connectivity. In all cases we establish upper and lower bounds for the minimal dimension d that guarantees the existence of "exceptional directions" in which the random graph behaves atypically with respect to the property. For each of the three properties, four theorems are established, to describe upper and lower bounds for the threshold dimension in the subcritical and supercritical regimes.
We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least 1−ε, the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in 1/ε, and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in 1/ε. We conclude the paper with several open problems.
n independent random points drawn from a density f in Rd define a random Voronoi partition. We study the measure of a typical cell of the partition. We prove that the asymptotic distribution of the probability measure of the cell centered at a point x∈Rd is independent of x and the density f. We determine all moments of the asymptotic distribution and show that the distribution becomes more concentrated as d becomes large. In particular, we show that the variance converges to zero exponentially fast in d. %We also study the measure of the largest cell of the partition. %{\red We also obtain a density-free bound for the rate of convergence of the diameter of a typical Voronoi cell.
We discuss the possibilities and limitations of estimating the mean of a real-valued random variable from independent and identically distributed observations from a non-asymptotic point of view. In particular, we define estimators with a sub-Gaussian behavior even for certain heavy-tailed distributions. We also prove various impossibility results for mean estimators.
Kademlia is the de facto standard searching algorithm for P2P (peer-to-peer) networks on the Internet. In our earlier work, we introduced two slightly different models for Kademlia and studied how many steps it takes to search for a target node by using Kademlia's searching algorithm. The first model, in which nodes of the network are labelled with deterministic IDs, had been discussed in that paper. The second one, in which nodes are labelled with random IDs, which we call the Random ID Model, was only briefly mentioned. Refined results with detailed proofs for this model are given in this paper. Our analysis shows that with high probability it takes about clogn steps to locate any node, where n is the total number of nodes in the network and c is a constant that does not depend on n.
A random geometric irrigation graph Γn(rn,ξ) has n vertices identified by n independent uniformly distributed points X1,…,Xn in the unit square [0,1]2. Each point Xi selects ξi neighbors at random, without replacement, among those points Xj (j=i) for which ∥Xi−Xj∥<rn, and the selected vertices are connected to Xi by an edge. The number ξi of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each Xi such that ξi satisfies 1≤ξi≤κ for a constant κ>1. We prove that when rn=γnlogn/n for γn→∞ with γn=o(n1/6/log5/6n), then the random geometric irrigation graph experiences explosive percolation in the sense that when Eξi=1, then the largest connected component has size o(n) but if Eξi>1, then the size of the largest connected component is with high probability n−o(n). This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.
Consider a random geometric graph defined on n vertices uniformly distributed in the d-dimensional unit torus. Two vertices are connected if their distance is less than a "visibility radius" rn. We consider {\sl Bluetooth networks} that are locally sparsified random geometric graphs. Each vertex selects c of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of n−(1−δ)/d for some δ>0, then a constant value of c is sufficient for the graph to be connected, with high probability. It suffices to take c≥(1+ε)/δ+K for any positive ε where K is a constant depending on d only. On the other hand, with c≤(1−ε)/δ, the graph is disconnected, with high probability.
Let T be an infinite rooted tree with weights we assigned to its edges. Denote by mn(T) the minimum weight of a path from the root to a node of the nth generation. We consider the possible behaviour of mn(T) with focus on the two following cases: we say T is explosive if limn→∞mn(T)<∞, and say that T exhibits linear growth if liminfn→∞nmn(T)>0. We consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. We then apply this characterization to obtain new results concerning the event of explosion in infinite randomly weighted spherically-symmetric trees, answering a question of Pemantle and Peres. As a further application, we consider the random real tree generated by attaching sticks of deterministic decreasing lengths, and determine for which sequences of lengths the tree has finite height almost surely.
Kademlia is currently the most widely used searching algorithm in P2P (peer-to-peer) networks. This work studies an essential question about Kademlia from a mathematical perspective: how long does it take to locate a node in the network? To answer it, we introduce a random graph K and study how many steps are needed to locate a given vertex in K using Kademlia's algorithm, which we call the routing time. Two slightly different versions of K are studied. In the first one, vertices of K are labelled with fixed IDs. In the second one, vertices are assumed to have randomly selected IDs. In both cases, we show that the routing time is about c*log(n), where n is the number of nodes in the network and c is an explicitly described constant.
The cellular tree classifier model addresses a fundamental problem in the design of classifiers for a parallel or distributed computing world: Given a data set, is it sufficient to apply a majority rule for classification, or shall one split the data into two or more parts and send each part to a potentially different computer (or cell) for further processing? At first sight, it seems impossible to define with this paradigm a consistent classifier as no cell knows the "original data size", n. However, we show that this is not so by exhibiting two different consistent classifiers. The consistency is universal but is only shown for distributions with nonatomic marginals.
Consider a branching random walk on R, with offspring distribution Z and nonnegative displacement distribution W. We say that explosion occurs if an infinite number of particles may be found within a finite distance of the origin. In this paper, we investigate this phenomenon when the offspring distribution Z is heavy-tailed. Under an appropriate condition, we are able to characterize the pairs (Z, W) for which explosion occurs, by demonstrating the equivalence of explosion with a seemingly much weaker event: that the sum over generations of the minimum displacement in each generation is finite. Furthermore, we demonstrate that our condition on the tail is best possible for this equivalence to occur. We also investigate, under additional smoothness assumptions, the behavior of Mn, the position of the particle in generation n closest to the origin, when explosion does not occur (and hence limn→∞Mn=∞).
We propose a version of the follow-the-perturbed-leader online prediction algorithm in which the cumulative losses are perturbed by independent symmetric random walks. The forecaster is shown to achieve an expected regret of the optimal order O(sqrt(n log N)) where n is the time horizon and N is the number of experts. More importantly, it is shown that the forecaster changes its prediction at most O(sqrt(n log N)) times, in expectation. We also extend the analysis to online combinatorial optimization and show that even in this more general setting, the forecaster rarely switches between experts while having a regret of near-optimal order.
We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.
We design a data-dependent metric in Rd and use it to define the k-nearest neighbors of a given point. Our metric is invariant under all affine transformations. We show that, with this metric, the standard k-nearest neighbor regression estimate is asymptotically consistent under the usual conditions on k, and minimal requirements on the input data.
We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, \K(X_i,X_j) log n/n), where \K \ge 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.
We study depth properties of a general class of random recursive trees where each node i attaches to the random node iX_i and X_0, ..., X_n is a sequence of i.i.d. random variables taking values in [0,1). We call such trees scaled attachment random recursive trees (SARRT). We prove that the typical depth D_n, the maximum depth (or height) H_n and the minimum depth M_n of a SARRT are asymptotically given by D_n \sim μ^{-1} \log n, H_n \sim α_{\max} \log n and M_n \sim α_{\min} \log n where μ, α_{\max} and α_{\min} are constants depending only on the distribution of X_0 whenever X_0 has a density. In particular, this gives a new elementary proof for the height of uniform random recursive trees H_n \sim e \log n that does not use branching random walks.
We study the connectivity properties of random Bluetooth graphs that model certain "ad hoc" wireless networks. The graphs are obtained as "irrigation subgraphs" of the well-known random geometric graph model. There are two parameters that control the model: the radius r that determines the "visible neighbors" of each node and the number of edges c that each node is allowed to send to these. The randomness comes from the underlying distribution of data points in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r,c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.
Given a set S of n \geq d points in general position in R^d, a random hyperplane split is obtained by sampling d points uniformly at random without replacement from S and splitting based on their affine hull. A random hyperplane search tree is a binary space partition tree obtained by recursive application of random hyperplane splits. We investigate the structural distributions of such random trees with a particular focus on the growth with d. A blessing of dimensionality arises--as d increases, random hyperplane splits more closely resemble perfectly balanced splits; in turn, random hyperplane search trees more closely resemble perfectly balanced binary search trees. We prove that, for any fixed dimension d, a random hyperplane search tree storing n points has height at most (1 + O(1/sqrt(d))) log_2 n and average element depth at most (1 + O(1/d)) log_2 n with high probability as n \rightarrow \infty. Further, we show that these bounds are asymptotically optimal with respect to d.
Given an arbitrary three-dimensional correlation matrix, we prove that there exists a three-dimensional joint distribution for the random variable (X,Y,Z) such that X,Y and Z are identically distributed with beta distribution βk,k(dx) on (0,1) if k≥1/2. This implies that any correlation structure can be attained for three-dimensional copulas.
Let R^d -> A be a query problem over R^d for which there exists a data structure S that can compute P(q) in O(log n) time for any query point q in R^d. Let D be a probability measure over R^d representing a distribution of queries. We describe a data structure called the odds-on tree, of size O(n^ε) that can be used as a filter that quickly computes P(q) for some query values q in R^d and relies on S for the remaining queries. With an odds-on tree, the expected query time for a point drawn according to D is O(H*+1), where H* is a lower-bound on the expected cost of any linear decision tree that solves P. Odds-on trees have a number of applications, including distribution-sensitive data structures for point location in 2-d, point-in-polytope testing in d dimensions, ray shooting in simple polygons, ray shooting in polytopes, nearest-neighbour queries in R^d, point-location in arrangements of hyperplanes in R^d, and many other geometric searching problems that can be solved in the linear-decision tree model. A standard lifting technique extends these results to algebraic decision trees of constant degree. A slightly different version of odds-on trees yields similar results for orthogonal searching problems that can be solved in the comparison tree model.
We study a class of hypothesis testing problems in which, upon observing the realization of an n-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been ``contaminated,'' that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.
Let G be a (possibly disconnected) planar subdivision and let D be a probability measure over R2. The current paper shows how to preprocess (G,D) into an O(n) size data structure that can answer planar point location queries over G. The expected query time of this data structure, for a query point drawn according to D, is O(H+1), where H is a lower bound on the expected query time of any linear decision tree for point location in G. This extends the results of Collette et al (2008, 2009) from connected planar subdivisions to disconnected planar subdivisions. A version of this structure, when combined with existing results on succinct point location, provides a succinct distribution-sensitive point location structure.
We study the height and width of a Galton--Watson tree with offspring distribution B satisfying E(B)=1, 0 < Var(B) < infinity, conditioned on having exactly n nodes. Under this conditioning, we derive sub-Gaussian tail bounds for both the width (largest number of nodes in any level) and height (greatest level containing a node); the bounds are optimal up to constant factors in the exponent. Under the same conditioning, we also derive essentially optimal upper tail bounds for the number of nodes at level k, for 1 <= k <= n.
In a uniform random recursive k-dag, there is a root, 0, and each node in turn, from 1 to n, chooses k uniform random parents from among the nodes of smaller index. If S_n is the shortest path distance from node n to the root, then we determine the constant σsuch that S_n/log(n) tends to σin probability as n tends to infinity. We also show that max_{1 \le i \le n} S_i/log(n) tends to σin probability.
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex t for a packet currently located at vertex v is made based only on the coordinates of v, t, and the neighbourhood, N(v), of v. The current paper explores the limitations of such algorithms by showing that, for any (randomized) memoryless routing algorithm A, there exists a convex subdivision on which A takes Omega(n^2) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by Bose etal (2002,2004) requires 2^{Ω(n)} time to route between some pair of vertices.
A transversal in a rooted tree is any set of nodes that meets every path from the root to a leaf. We let c(T,k) denote the number of transversals of size k in a rooted tree T. We define a partial order on the set of all rooted trees with n nodes by saying that a tree T succeeds a tree T' if c(T,k) is at least c(T',k) for all k and strictly greater than c(T',k) for at least one k. We prove that, for every choice of positive integers d and n, the set of all rooted trees on n nodes where each node has at most d children has a unique minimal element with respect to this partial order and we describe this tree.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.