Details
| Original language | English |
|---|---|
| Pages (from-to) | 36-45 |
| Number of pages | 10 |
| Journal | Journal of applied probability |
| Volume | 35 |
| Issue number | 1 |
| Publication status | Published - 1 Jan 1998 |
Abstract
We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
Keywords
- Convergence in distribution, Markov chains, Randomized algorithms, Stochastic ordering
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Mathematics(all)
- General Mathematics
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Journal of applied probability, Vol. 35, No. 1, 01.01.1998, p. 36-45.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Hoare's Selection Algorithm
T2 - A Markov Chain Approach
AU - Grübel, Rudolf
PY - 1998/1/1
Y1 - 1998/1/1
N2 - We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
AB - We obtain bounds for the distribution of the number of comparisons needed by Hoare’s randomized selection algorithm FIND and give a new proof for Grübel and Räsler’s (1996) result on the convergence of this distribution. Our approach is based on the construction and analysis of a suitable associated Markov chain. Some numerical results for the quantiles of the limit distributions are included, leading for example to the statement that, for a set S with n elements and n large, FIND will need with probability 0.9about 4.72 × n comparisons to find the median of S.
KW - Convergence in distribution
KW - Markov chains
KW - Randomized algorithms
KW - Stochastic ordering
UR - http://www.scopus.com/inward/record.url?scp=85037205177&partnerID=8YFLogxK
U2 - 10.1239/jap/1032192549
DO - 10.1239/jap/1032192549
M3 - Article
AN - SCOPUS:85037205177
VL - 35
SP - 36
EP - 45
JO - Journal of applied probability
JF - Journal of applied probability
SN - 0021-9002
IS - 1
ER -