Perfect simulation from the quicksort limit distribution (Q1572752): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Luc P. Devroye / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Yuriy Vasil'ovich Kozachenko / rank | |||
Normal rank |
Revision as of 21:09, 9 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Perfect simulation from the quicksort limit distribution |
scientific article |
Statements
Perfect simulation from the quicksort limit distribution (English)
0 references
27 July 2000
0 references
The authors consider the following problem. Let \(C_n\) denote the number of key comparisons needed to sort a list of \(n\) randomly permuted items by Quicksort. Let \(X_n ={C_n -EC_n\over n}.\) It is well known that \(X_n \to X\) as \(n\to\infty\) in distribution where \(X\) is a random variable, which distribution is the unique solution with zero mean and finite variance of the distributional fixed-point equation \(X=(D) UX^{(1)} +(1-U)X^{(2)} +c(U)\) where \(X^{(1)}\), \(X^{(2)}\), and \(U\) are independent; \(X^{(1)}\) and \(X^{(2)}\) are distributed as \(X\); \(U\) is uniform distributed in \([0, 1] \) \(e(u) = 1+2u\ln(u) +2(1-u)\ln(1-u)\) and \((D)\) denotes equality in distribution. The authors present an algorithm, which returns a perfect sample of the limit random variable \(X.\) This algorithm is based on a modified rejection method, where they use a convergent sequence of approximations for the density to decide the outcome of a rejection test.
0 references
random variate generation
0 references
sorting
0 references
quicksort algorithm
0 references
Monte Carlo method
0 references
fixed-point equation
0 references
rejection method
0 references