Abstract. Given some binary matrix [Formula: see text], suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, can we recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant [Formula: see text] such that the algorithm terminates in [Formula: see text] time with high probability and in expectation for random [Formula: see text] binary matrices with i.i.d. entries [Formula: see text] such that [Formula: see text] and [Formula: see text].

We revisit the problem of the estimation of the differential entropy$H(f)$of a random vector$X$in$R^{d}$with density$f$, assuming that$H(f)$exists and is finite. In this note, we study the consistency of the popular nearest neighbor estimate$H_{n}$of Kozachenko and Leonenko. Without any smoothness condition we show that the estimate is consistent ($E\{|H_{n} - H(f)|\} \to 0$as$n \to \infty $) if and only if${\mathbb E}\{ \log (\| X \| + 1)\} < \infty $. Furthermore, if$X$has compact support, then$H_{n} \to H(f)$almost surely.

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(n2) 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(log2n) 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.

We study online combinatorial optimization problems that a learner is interested in minimizing its cumulative regret in the presence of switching costs. To solve such problems, we propose a version of the follow-the-perturbed-leader algorithm in which the cumulative losses are perturbed by independent symmetric random walks. In the general setting, our forecaster is shown to enjoy near-optimal guarantees on both quantities of interest, making it the best known efficient algorithm for the studied problem. In the special case of prediction with expert advice, we show that the forecaster achieves an expected regret of the optimal order O(n log N)1/2), where n is the time horizon and N is the number of experts, while guaranteeing that the predictions are switched at most O(n log N)1/2) times, in expectation.

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(\sqrtn \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(\sqrtn \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.

LetX,X1,X2, ... be independent and identically distributed Rd-valued random variables and letm: Rd→ R be a measurable function such that a densityfofY=m(X) exists. Given a sample of the distribution of (X,Y) and additional independent observations ofX, we are interested in estimatingf. We apply a regression estimate to the sample of (X,Y) and use this estimate to generate additional artificial observations ofY. Using these artificial observations together with the real observations ofY, we construct a density estimate offby using a convex combination of two kernel density estimates. It is shown that if the bandwidths satisfy the usual conditions and if in addition the supremum norm error of the regression estimate converges almost surely faster toward zero than the bandwidth of the kernel density estimate applied to the artificial data, then the convex combination of the two density estimates isL1-consistent. The performance of the estimate for finite sample size is illustrated by simulated data, and the usefulness of the procedure is demonstrated by applying it to a density estimation problem in a simulation model.

We propose a new k-NN regression estimate based on a data-dependent metric in Rdwhich is used to define the k-nearest neighbors of a given point. The metric is invariant under all affine transformations. 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 discuss various methods for generating random Galton–Watson trees conditional on their sizes being equal to n. A linear expected time algorithm is proposed.

A hyperplane search tree is a binary tree used to store a set S of n d-dimensional data points. In a random hyperplane search tree for S, the root represents a hyperplane defined by d data points drawn uniformly at random from S. The remaining data points are split by the hyperplane, and the definition is used recursively on each subset. We assume that the data are points in general position in $\mathbb{R}^d$. We show that, uniformly over all such data sets S, the expected height of the hyperplane tree is not worse than that of the k-d tree or the ordinary one-dimensional random binary search tree, and that, for any fixed $d\ge3$, the expected height improves over that of the standard random binary search tree by an asymptotic factor strictly greater than one.

Based on randomly drawn vectors in a separable Hilbert space, one may construct a k-means clustering scheme by minimizing an empirical squared error. We investigate the risk of such a clustering scheme, defined as the expected squared distance of a random vector X from the set of cluster centers. Our main result states that, for an almost surely bounded , the expected excess clustering risk is O(¿1/n) . Since clustering in high (or even infinite)-dimensional spaces may lead to severe computational problems, we examine the properties of a dimension reduction strategy for clustering based on Johnson-Lindenstrauss-type random projections. Our results reflect a tradeoff between accuracy and computational complexity when one uses k-means clustering after random projection of the data to a low-dimensional space. We argue that random projections work better than other simplistic dimension reduction schemes.

The spanning ratio of a graph defined on n points in the Euclidean plane is the maximum ratio over all pairs of data points (u,v) of the minimum graph distance between u and v divided by the Euclidean distance between u and v. A connected graph is said to be an S-spanner if the spanning ratio does not exceed S. For example, for any S there exists a point set whose minimum spanning tree isnot an S-spanner. At the other end of the spectrum, a Delaunay triangulation is guaranteed to be a 2.42-spanner [J. M. Keil and C. A. Gutwin, Discrete Comput. Geom., 7 (1992), pp. 13-28]. For proximity graphs between these two extremes, such as Gabriel graphs [K. R. Gabriel and R. R. Sokal, Systematic Zoology, 18 (1969), pp. 259-278], relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268], and $\beta$-skeletons [D. G. Kirkpatrick and J. D. Radke, Comput. Geom., G. T. Toussaint, ed., Elsevier, Amsterdam, 1985, pp. 217-248] with $\beta$ in [0,2] some interesting questions arise. We show that the spanning ratio for Gabriel graphs (which are $\beta$-skeletons with $\beta$ = 1) is $\Theta ( \sqrt{n})$ in the worst case. For all $\beta$-skeletons with $\beta$ in [0,1], we prove that the spanning ratio is at most $O(n^\gamma)$, where $\gamma = (1-\log_2(1+\sqrt{1-\beta^2}))/2$. For all $\beta$-skeletons with $\beta$ in [1,2], we prove that there exist point sets whose spanning ratio is at least $\left( \frac{1}{2} - o(1) \right) \sqrt{n} $. For relative neighborhood graphs [G. T. Toussaint, Pattern Recognition, 12 (1980), pp. 261-268] (skeletons with $\beta$ = 2), we show that there exist point sets where the spanning ratio is $\Omega(n)$. For points drawn independently from the uniform distribution on the unit square, we show that the spanning ratio of the (random) Gabriel graph and all $\beta$-skeletons with $\beta$ in [1,2] tends to $\infty$ in probability as $\sqrt{\log n / \log \log n}$.

We present an algorithm for hashing $\lfloor \alpha n \rfloor$ elements into a table with n separate chains that requires O(1) deterministic worst-case insert time and O(1) expected worst-case search time for constant $\alpha$. We exploit the connection between two-way chaining and random graph theory in our techniques.

We consider open addressing hashing and implement it by using the Robin Hood strategy; that is, in case of collision, the element that has traveled the farthest can stay in the slot. We hash $\sim \alpha n$ elements into a table of size n where each probe is independent and uniformly distributed over the table, and $\alpha < 1$ is a constant. Let $M_n$ be the maximum search time for any of the elements in the table. We show that with probability tending to one, $M_n \in [ \log_2 \log n + \sigma, \log_2 \log n + \tau ]$ for some constants $\sigma, \tau$ depending upon $\alpha$ only. This is an exponential improvement over the maximum search time in case of the standard FCFS (firstcome first served) collision strategy and virtually matches the performance of multiple-choice hash methods.

For the random binary search tree with n nodes inserted the number of ancestors of the elements with ranks k and $\ell$, $1 \le k < \ell \le n$, as well as the path distance between these elements in the tree are considered. For both quantities, central limit theorems for appropriately rescaled versions are derived. For the path distance, the condition $\ell-k \to \infty$ as $n\to \infty$ is required. We obtain tail bounds and the order of higher moments for the path distance. The path distance measures the complexity of finger search in the tree.

Let (F/sub k/)/sub k/spl ges/1/ be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to F/sub k//sup */, where k/sup */ is the unknown smallest integer such that f/spl isin/F/sub k/. Given a random sample X/sub 1/,...,X/sub n/ drawn from f, an integer k/sub 0//spl ges/1 and a real number /spl alpha//spl isin/(0,1), we introduce a new, simple, explicit /spl alpha/-level consistent testing procedure of the null hypothesis {H/sub 0/:k/sup */=k/sub 0/} versus the alternative {H/sub 1/:k/sup *//spl ne/k/sub 0/}. Our method is inspired by the combinatorial tools developed in Devroye and Lugosi and it includes a wide range of density models, such as mixture models, neural networks, or exponential families.

We consider sums of functions of subtrees of a random binary search tree and obtain general laws of large numbers and central limit theorems. These sums correspond to random recurrences of the quicksort type, $X_n {\stackrel{\cal L}{=}} X_{I_n} + X'_{n-1-I_n} + Y_n$, $n \ge 1$, where I n is uniformly distributed on {0,1,. . ., n-1 }, Y n is a given random variable, $X_k {\stackrel{\cal L}{=}} X'_k$ for all k, and, given I n , X I n and X' n-1-I n are independent. Conditions are derived such that $(X_n - \mu n )/\sigma \sqrt{n} {\stackrel{\cal L}{\rightarrow}} {\cal N}(0,1)$, the normal distribution, for some finite constants $\mu$ and $\sigma$.

We introduce a simple new hypothesis testing procedure, which, based on an independent sample drawn from a certain density, detects which of k nominal densities is the true density closest to, under the total variation (L/sub 1/) distance. We obtain a density-free uniform exponential bound for the probability of false detection.

We modify the k-d tree on [0,1] d by always cutting the longest edge instead of rotating through the coordinates. This modification makes the expected time behavior of lower-dimensional partial match queries behave as perfectly balanced complete k-d trees on n nodes. This is in contrast to a result of Flajolet and Puech [ J. Assoc. Comput. Mach., 33 (1986), pp. 371--407], who proved that for (standard) random k-d trees with cuts that rotate among the coordinate axes, the expected time behavior is much worse than for balanced complete k-d trees. We also provide results for range searching and nearest neighbor search for our trees.

We give a short proof of the following result. Let (X,Y) be any distribution on N/spl times/{0,1}, and let (X/sub 1/,Y/sub 1/),...,(X/sub n/,Y/sub n/) be an i.i.d. sample drawn from this distribution. In discrimination, the Bayes error L*=inf/sub g/P{g(X)/spl ne/Y} is of crucial importance. Here we show that without further conditions on the distribution of (X,Y), no rate-of-convergence results can be obtained. Let /spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/) be an estimate of the Bayes error, and let {/spl phi//sub n/(.)} be a sequence of such estimates. For any sequence {a/sub n/} of positive numbers converging to zero, a distribution of (X,Y) may be found such that E{|L*-/spl phi//sub n/(X/sub 1/,Y/sub 1/,...,X/sub n/,Y/sub n/)|}/spl ges/a/sub n/ often converges infinitely.

The random hash tree and the N-tree were introduced by Ehrlich in 1981. In the random hash tree, n data points are hashed to values X 1 , . . . , X n , independently and identically distributed random variables taking values that are uniformly distributed on [0,1]. Place the X i 's in n equal-sized buckets as in hashing with chaining. For each bucket with at least two points, repeat the same process, keeping the branch factor always equal to the number of bucketed points. If H n is the height of tree obtained in this manner, we show that H n /log 2 n \to 1 in probability. We also show that the expected number of nodes in the random hash tree and random pebbled hash tree is asymptotic to 2.3020238 . . . n and 1.4183342. . . n, respectively.

We introduce the unoriented $\Theta$-maximum as a new criterion for describing the shape of a set of planar points. We present efficient algorithms for computing the unoriented $\Theta$-maximum of a set of planar points. We also propose a simple linear expected time algorithm for computing the unoriented $\Theta$-maximum of a set of planar points when $\Theta=\pi/2$.

Random binary search trees, b-ary search trees, median-of-(2k+1) trees, quadtrees, simplex trees, tries, and digital search trees are special cases of random split trees. For these trees, we offer a universal law of large numbers and a limit law for the depth of the last inserted point, as well as a law of large numbers for the height.

We consider the computer generation of random binary search trees with n nodes for the standard random permutation model. The algorithms discussed here output the number of external nodes at each level, but not the shape of the tree. This is important, for example, when one wishes to simulate the height of the binary search tree. Various paradigms are proposed, including depth-first search with pruning, incremental methods in which the tree grows with random-sized jumps, and a tree growing procedure gleaned from birth-and-death processes. The last method takes $O(\log^{4} n)$ expected time.

Let $H_{n}$ be the height of a random binary search tree on n nodes. We show that there exists a constant $\alpha = 4.31107 \ldots $ such that ${\textbf P} \{|H_{n} - \alpha \log n| > \beta \log \log n\} \rightarrow 0 $, where $\beta > 15 \alpha/\ln 2 = 93.2933 \ldots $. The proof uses the second moment method and does not rely on properties of branching processes. We also show that $\operatorname{Var}\{H_{n}\} = O((\log\log n)^{2})$.

Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities $p_i $ , and let $H_n $ be the height of the suffix tree constructed from the first n suffixes of this word. It is shown that $H_n $ is asymptotically close to $2\log n/\log (1/\sum_i p_i^2 )$ in many respects: the difference is $O(\log \log n)$ in probability, and the ratio tends to one almost surely and in the mean.

It is shown that the depth of the last node inserted in a random quad tree constructed from independent uniform $[0,1]^d $ random vectors is in probability asymptotic to $({2 / d}) \log n$, where log denotes the natural logarithm. In addition, for $d = 2$, exact values are obtained for all the moments of the depth of the last node.

A test sequence is used to select the best rule from a class of discrimination rules defined in terms of the training sequence. The Vapnik-Chervonenkis and related inequalities are used to obtain distribution-free bounds on the difference between the probability of error of the selected rule and the probability of error of the best rule in the given class. The bounds are used to prove the consistency and asymptotic optimality for several popular classes, including linear discriminators, nearest-neighbor rules, kernel-based rules, histogram rules, binary tree classifiers, and Fourier series classifiers. In particular, the method can be used to choose the smoothing parameter in kernel-based rules, to choose k in the k-nearest neighbor rule, and to choose between parametric and nonparametric rules.>

Let H n be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n . It is shown that H n /log n → c = 4.31107 … in probability as n → ∞, where c is the unique solution of c log((2 e )/ c ) = 1, c ≥ 2. Also, for all p > 0, lim n →∞ E ( H p n )/ log p n = c p . Finally, it is proved that S n /log n → c * = 0.3733 … , in probability, where c * is defined by c log((2 e )/ c ) = 1, c ≤ 1, and S n is the saturation level of the same tree, that is, the number of full levels in the tree.

We analyze and compare several data structures and algorithms for evaluating the kernel density estimate. Frequent evaluations of this estimate are for example needed for plotting, error estimation, Monte Carlo estimation of probabilities and functionals, and pattern classification. An experimental comparison is included.

Consider the basic discrimination problem based on a sample of size n drawn from the distribution of (X, Y) on the Borel sets of Rdx {0, 1}. If 0 ⩽ R*.n→ 0 is an arbitrary positive sequence, then for any discrimination rule one can find a distribution for (X, Y), not depending upon n, with Bayes probability of error R* such that the probability of error (Rn) of the discrimination rule is larger than R* + ønfor infinitely many n. We give a formal proof of this result, which is a generalization of a result by Cover [1]. Furthermore, sup all distributions of (X, Y) with R* = 0 Rn⩾ ½. Thus, any attempt to find a nontrivial distribution-free upper bound for Rnwill fail, and any results on the rate of convergence of Rnto R* must use assumptions about the distribution of (X, Y).

When (X1, ¿1),..., (Xn, ¿n) are independent identically distributed random vectors from IRd X {0, 1} distributed as (X, ¿), and when ¿ is estimated by its nearest neighbor estimate ¿(1), then Cover and Hart have shown that P{¿(1) ¿ ¿}n ¿ ¿ ¿ 2E {¿ (X) (1 - ¿(X))} ¿ 2R*(1 - R*) where R* is the Bayes probability of error and ¿(x) = P{¿ = 1 | X = x}. They have conditions on the distribution of (X, ¿). We give two proofs, one due to Stone and a short original one, of the same result for all distributions of (X, ¿). If ties are carefully taken care of, we also show that P{¿(1) ¿ ¿|X1, ¿1, ..., Xn, ¿n} converges in probability to a constant for all distributions of (X, ¿), thereby strengthening results of Wagner and Fritz.

In the discrimination problem the random variable\theta, known to take values in{1 ,\ldots ,M}, is estimated from the random vectorXtaking values in{\bfR}^{d}. Ali that is known about the joint distribution of(X,O)is that which can be inferred from a sample(X_{1} , \theta_{1}, \ldots , (X_{n}, \theta_{n})of sizendrawn from that distribution. A discrimination rule is any procedure which determines a decision\hat{\theta}for\thetafromXand(X_{1},\theta_{1}) , \ldots , (X_{n}, \theta_{n}). The rule is calledk-local if the decision\hat{\theta}depends only onXand the pairs(X_{i}, \theta_{i}),for whichX_{i}is one of thekclosest toXfromX_{1} , \ldots ,X_{n}. IfL_{n}denotes the probability of error for ak-local rule given the sample, then estimates\hat{L}_{n}ofL_{n}, are determined for whichP {| \hat{L}_{n} - L_{n} \geq \epsilon} \exp (- Bn), whereAandBare positive constants depending only ond,M, and\epsilon.

Probability inequalities are given for the deviation of the resubstitution error estimate from the unknown conditional probability of error. The inequalities are distribution free and can be applied to linear discrimination rules, to nearest neighbor rules with a reduced sample size, and to histogram rules.

In the discrimination problem the random variable\theta, known to take values in{1, \cdots ,M}, is estimated from the random vectorX. All that is known about the joint distribution of(X, \theta)is that which can be inferred from a sample(X_{1}, \theta_{1}), \cdots ,(X_{n}, \theta_{n})of sizendrawn from that distribution. A discrimination nde is any procedure which determines a decision\hat{ \theta}for\thetafromXand(X_{1}, \theta_{1}) , \cdots , (X_{n}, \theta_{n}). For rules which are determined by potential functions it is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded byA/ \sqrt{n}whereAis an explicitly given constant depending only onMand the potential function. TheO(n ^{-1/2})behavior is shown to be the best possible for one of the most commonly encountered rules of this type.

A class of nonparametric regression function estimates generalizing the nearest neighbor estimate of Cover [ 12] is presented. Under various noise conditions, it is shown that the estimates are strongly uniformly consistent. The uniform convergence of the estimates can be exploited to design a simple random search algorithm for the global minimization of the regression function.

It is shown that distribution-free confidence intervals can be placed about the resubstitution estimate of the probability of error of any linear discrimination procedure.

The convergence of statistical (random) search for the minimization of an arbitrary multimodal functional Q(w) is dealt with by using the theorems of convergence of random processes of Braverman and Rozonoer. It is shown that random search can be regarded as a gradient algorithm in the Q-domain. Using this gradient to define the minimum of the functional, the convergence to this minimum is discussed at length. The theorems proved in this paper apply as well to discrete as to continuous optimization problems and as such, the developed technique is competitive with stochastic automata with a variable structure. The optimality of the scheme follows from the convergence in probability of the average performance to the minimum. The freedom in the organization of the search within the boundaries outlined by the conditions of convergence is emphasized. Finally, it is pointed out how various mixed random search and hierarchical search systems fall into the domain of application of the theorems.

An alternative solution to the problem of the selection of the best strategy in a random environment is presented by using a probabilistic search procedure. The asymptotic optimality of the technique is proved, and a brief comparison with stochastic automata with variable structures is made. A specific organization of the optimal search procedure is developed based on continued learning of some statistics of the random environment, and it is shown to be fast-converging, powerful in high noise random environments, and insensitive to search parameter selection.