The storage complexity of some estimators of the median (Q1316141): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q311391
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / reviewed by
 
Property / reviewed by: Gabriel Dimitriu / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5538132 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5545070 / rank
 
Normal rank

Latest revision as of 13:30, 22 May 2024

scientific article
Language Label Description Also known as
English
The storage complexity of some estimators of the median
scientific article

    Statements

    The storage complexity of some estimators of the median (English)
    0 references
    0 references
    0 references
    10 April 1994
    0 references
    The authors investigate the computational complexity of various procedures for finding the median of an unknown distribution from which independent random samples of any size can be drawn. They prove that the computation of the sample median of arbitrarily large samples requires storage of unbounded amounts of data. Precisely, they 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, an algorithm 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 is introduced.
    0 references
    0 references
    0 references
    0 references
    0 references
    storage complexity
    0 references
    estimators of the median
    0 references
    computational complexity
    0 references
    sample median
    0 references
    0 references
    0 references