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.

The designer of a nonparametric discrimination or estimation procedure is almost always interested in the conditional risk of his procedure, or nde, conditioned on the available data. Unfortunately,L_{n}, the risk conditioned on a data set containingnobservations, cannot be computed without exact knowledge of the underlying probability distribution functions. Since such knowledge is unavailable, the designer must be content with estimates ofL_{n}. Two such estimates are the deleted estimate,L_{n}^{D}, and the holdout estimate,L_{n}^{H}. This paper presents the results of an experimental study of these two estimates and compares these results with some recently obtained distribution.free theoretical results. Among other things, the experimental data indicates that fork-nearest neighbor rules in{\bf R^{1}}with several examples of underlying distributions,P{|L_{n}-L^{D}_{n}| \geq 2e^{-2 \epsilon^{2}n}\mbox{P{|}L_{n}-L^{H}_{n}| \geq \epsilon} 2e^{-2 \epsilon^{2} \sqrt{n}.}

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.

A disadvantage of the kernel estimate of a probability density is that the degree of smoothing about the observation points is chosen without regard to the data. A modification of the kernel estimate is proposed that allows the data to play a role in this smoothing and, at the same time, retains the desirable features of the kernel estimate.

The topic of this paper is a probabilistic analysis of demand paging algorithms for storage hierarchies. Two aspects of algorithm performance are studied under the assumption that the sequence of page requests is statistically independent: the page fault probability for a fixed memory size and the variation of performance with memory. Performance bounds are obtained which are independent of the page request probabilities. It is shown that simple algorithms exist which yield fault probabilities close to optimal with only a modest increase in memory.

We demonstrate in this correspondence that the procedure introduced by Chow and Liu for estimating tree-dependent probability distributions is consistent.

The editedknearest neighbor rule (k-NNR) consists of 1) eliminating those samples from the data which are not classified correctly by thek-NNR and the remainder of the data, and 2) using the NNR with the samples which remain from 1) to classify new observations. Wilson has shown that this rule has an asymptotic probability of error which is better than that of thek-NNR. A key step in his development is showing the convergence of the edited nearest neighbor. His lengthy argument is replaced here by a somewhat simpler one which uses an intuitive fact about the editing procedure.

LetX_1,X_2,\cdotsbe a sequence of independent identically distributed observations with a common mean\mu. Assume that0 \leq X_i \leq 1with probability 1. We show that for each\varepsilon > 0there exists an integerm, a finite-valued statisticT_n = T_n(X_1, \cdots , X_n) \in \{t_1,\cdots,t_m\}and a real-valued functionddefined on\{t_1,\cdots,t_m\}such thati)T_{n+1} = f_n(T_n,X_{n+1}); ii)P[\lim \sup \mid d(T_n) - \mu \mid \leq \varepsilon] = 1. Thus we have a recursive-like estimate of\mu, for which the data are summarized for eachnby one ofmstates and which converges to within\varepsilonof\muwith probability 1. The constraint on memory here is time varying as contrasted to the time-invariant constraint that would haveT_{n+1} = f(T_n, X_{n+1})for alln.

For the case where the channel states are the same as the channel outputs a simple necessary and sufficient condition is given to determine when the capacity of a finite-state channel is positive.

If the nearest neighbor rule (NNR) is used to classify unknown samples, then Cover and Hart [1] have shown that the average probability of error usingnknown samples (denoted byR_n) converges to a numberRasntends to infinity, whereR^ {\ast} \leq R \leq 2R^ {\ast} (1 - R^ {\ast}), andR^ {\ast}is the Bayes probability of error. Here it is shown that when the samples lie inn-dimensional Euclidean space, the probability of error for the NNR conditioned on thenknown samples (denoted byL_n. so thatEL_n = R_n)converges toRwith probability 1 for mild continuity and moment assumptions on the class densities. Two estimates ofRfrom thenknown samples are shown to be consistent. Rates of convergence ofL_ntoRare also given.

The effect on the probability of error from intersymbol interference caused by a repeated use of a continuous-time Gaussian channel is examined. The model assumes that signals that are power constrained are put through a linear filter after which Gaussian noise is added to produce the received signal. One can view the linear filter as a frequency constraint on the inputs. Because of the memory in the filter, past inputs affect the filter output for the current input. It is shown that this interference can be treated as an additional input whose reproducing kernel Hilbert space (RKHS) norm is upper bounded by a function that tends to 0 with increasing block length. Describing the channel in RKHS terms, we show that the exponential error bounds obtained by Gallager are unchanged if one takes intersymbol interference into account.

The two category classification problem is treated. No a priori knowledge of the statistics of the classes is assumed. A sequence of labeled samples from the two classes is used to construct a sequence of approximations of a discriminant function that is optimum in the sense of minimizing the probability of misclassification but which requires knowledge of all the statistics of the classes. Depending on the assumptions made about the probability densities corresponding to the two classes, the integrated square error of the approximations converges to0in probability or with probability1. The approximations are nonparametric and recursive for each fixed point of the domain. Rates of convergence are given. The approximations are used to define a decision procedure for classifying unlabeled samples. It is shown that as the number of labeled samples used to construct the approximations increases, the resulting sequence of discriminant functions is asymptotically optimal in the sense that the probability of misclassification when using the approximations in the decision procedure converges in probability or with probability1, depending on the assumptions made, to the probability of misclassification of the optimum discriminant function. The results can be easily extended to the multicategory problem and to the case of arbitrary loss functions, that is, where the costs of misclassification are not necessarily equal to1.

A Gilbert bound for periodic binary convolutional (PBC) codes is established. This bound shows that regardless of previous decoding decisions any fraction of errors less than\alpha/2can be corrected in a constraint length by some PBC code if the constraint length is sufficiently large andR, the code rate, is less than[1 - H(\alpha)]/2, 0 \leq \alpha < \frac{1}{2}.

The generator matrices of(n, 2)codes which are optimum for the BSC with sufficiently small channel error probabilitypare given.

The purpose of this correspondence is to apply the results of Patterson to a pattern classification problem which has been considered frequently in the literature and to show that a convergence result is obtained which is as strong as any presented to date.

Let {Yn} be a stationary random process where each Y value takes values in a finite set B. Then define Hnand enso that H is the entropy of {Yn} and e is the probability of error in predicting Y0from the infinite past. The purpose of this correspondence is to give an example which shows that {Hn- H} and {en- e} are not, in general, asymptotically identical for a stationary process {Yn}.