The storage complexity of some estimators of the median

摘要

We consider the computational complexity of various algorithms for finding the median of an unknown distribution from which independent random samples of any size can be drawn. We present two principal results: We prove that computation of the sample median of arbitrarily large samples requires storage of unbounded amounts of data, which is intuitively reasonable. Indeed, we prove that even if the population consists of a known, finite number K of distinct elements, the computation of the medians of arbitrarily large samples requires K - 1 counters that need unbounded capacity, and no algorithm with either fewer counters or counters with bounded capacities can succeed. In contrast, we then present an algorithm, though not a very efficient one, for computing a sequence of estimators (necessarily not sample medians) that converge almost surely to the median of any given (unknown) distribution and that requires only a small, fixed number of counters (to count certain events) and registers (each of which contains a real number to the same degree of precision as the sample elements).