Median Bounds and Their Application

Alan Siegel

doi:10.1006/jagm.2000.1138

Median Bounds and Their Application

Alan Siegel

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English (US)
Pages (from-to)	184-236
Number of pages	53
Journal	Journal of Algorithms
Volume	38
Issue number	1
DOIs	https://doi.org/10.1006/jagm.2000.1138
State	Published - Jan 2001

Keywords

Bernoulli trials
Conditioned Bernoulli trials
Conditioned hypergeometric distribution
Hypergeometric distribution
Interpolation search
Median
PRAM emulation
Weighted selection

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1006/jagm.2000.1138

Cite this

@article{38c41e28336347f6a25b8c357d5712e1,

title = "Median Bounds and Their Application",

abstract = "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.",

keywords = "Bernoulli trials, Conditioned Bernoulli trials, Conditioned hypergeometric distribution, Hypergeometric distribution, Interpolation search, Median, PRAM emulation, Weighted selection",

author = "Alan Siegel",

note = "Funding Information: 1Supported, in part, by NSF Grant CCR-9503793.",

year = "2001",

month = jan,

doi = "10.1006/jagm.2000.1138",

language = "English (US)",

volume = "38",

pages = "184--236",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Median Bounds and Their Application

AU - Siegel, Alan

N1 - Funding Information: 1Supported, in part, by NSF Grant CCR-9503793.

PY - 2001/1

Y1 - 2001/1

N2 - 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.

AB - 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.

KW - Bernoulli trials

KW - Conditioned Bernoulli trials

KW - Conditioned hypergeometric distribution

KW - Hypergeometric distribution

KW - Interpolation search

KW - Median

KW - PRAM emulation

KW - Weighted selection

UR - http://www.scopus.com/inward/record.url?scp=0346492027&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346492027&partnerID=8YFLogxK

U2 - 10.1006/jagm.2000.1138

DO - 10.1006/jagm.2000.1138

M3 - Article

AN - SCOPUS:0346492027

SN - 0196-6774

VL - 38

SP - 184

EP - 236

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Median Bounds and Their Application

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this