Median Bounds and Their Application

✍ Scribed by Alan Siegel

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 329 KB
• Volume: 38
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2000.1138

✦ Synopsis

Basic methods are given to evaluate or estimate the median for various probability distributions. These methods are then applied to determine the precise median of several nontrivial distributions, including weighted selection and the sum of heterogeneous Bernoulli trials conditioned to lie within any interval centered about the mean. These bounds are then used to give simple analyses of algorithms such as interpolation search and some aspects of PRAM emulation.