  Bob predicts a future observation based on a sample of size one. Alice can
draw a sample of any size before issuing her prediction. How much better can
she do than Bob? Perhaps surprisingly, under a large class of loss functions,
which we refer to as the Cover-Hart family, the best Alice can do is to halve
Bob's risk. In this sense, half the information in an infinite sample is
contained in a sample of size one. The Cover-Hart family is a convex cone that
includes metrics and negative definite functions, subject to slight regularity
conditions. These results may help explain the small relative differences in
empirical performance measures in applied classification and forecasting
problems, as well as the success of reasoning and learning by analogy in
general, and nearest neighbor techniques in particular.
