@BOOK{b2012,
AUTHOR = {Billingsley, Patrick},
TITLE = {Probability and Measure},
PUBLISHER = {John Wiley \& Sons},
YEAR = {2012},
address = {Hoboken},
edition = {4th},
}
@article {s1947,
AUTHOR = {Scheff{\'e}, Henry},
TITLE = {A useful convergence theorem for probability distributions},
JOURNAL = {Ann. Math. Statistics},
FJOURNAL = {Annals of Mathematical Statistics},
VOLUME = {18},
YEAR = {1947},
PAGES = {434--438},
ISSN = {0003-4851},
MRCLASS = {27.2X},
MRNUMBER = {0021585 (9,83h)},
MRREVIEWER = {R. Fortet},
}
@ARTICLE{s2015,
author = {{Sulzbach}, H.},
title = "{On martingale tail sums for the path length in random trees}",
journal = {ArXiv e-prints},
archivePrefix = "arXiv",
eprint = {1412.3508},
primaryClass = "math.PR",
keywords = {Mathematics - Probability, Computer Science - Data Structures and Algorithms, Primary 60F15, 68P05, secondary 60F05, 60G42},
year = 2014,
month = dec,
}
@book {a1965,
AUTHOR = {Akhiezer, N. I.},
TITLE = {The classical moment problem and some related questions in
analysis},
SERIES = {Translated by N. Kemmer},
PUBLISHER = {Hafner Publishing Co., New York},
YEAR = {1965},
PAGES = {x+253},
MRCLASS = {44.60},
MRNUMBER = {0184042 (32 \#1518)},
}
@article{kp1998,
author = {Kirschenhofer, P. and Prodinger, H.},
title = {Comparisons in Hoareās Find algorithm.},
journal={Combinatorics, Probability and Computing},
volume={7},
pages={111-120},
year={1998}
}
@article {n2013,
author = {Neininger, Ralph},
title = {Refined quicksort asymptotics},
journal = {Random Structures \& Algorithms},
volume = {46},
number = {2},
issn = {1098-2418},
url = {http://dx.doi.org/10.1002/rsa.20497},
doi = {10.1002/rsa.20497},
pages = {346--361},
keywords = {quicksort, complexity, key comparisons, central limit theorem, strong limit theorem, rate of convergence, Zolotarev metric, contraction method},
year = {2015},
}
@article {f2015,
AUTHOR = {Fuchs, Michael},
TITLE = {A note on the {Q}uicksort asymptotics},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {46},
YEAR = {2015},
NUMBER = {4},
PAGES = {677--687},
ISSN = {1042-9832},
MRCLASS = {68P10 (60G42)},
MRNUMBER = {3346462},
DOI = {10.1002/rsa.20524},
URL = {http://dx.doi.org/10.1002/rsa.20524},
}
@article{gk2014,
author = {{Gr{\"u}bel}, R. and {Kabluchko}, Z.},
title = "{A functional central limit theorem for branching random walks, almost sure weak convergence, and applications to random trees}",
journal = {ArXiv e-prints},
note = {Available at http://arxiv.org/abs/1410.0469},
archivePrefix = "arXiv",
eprint = {1410.0469},
primaryClass = "math.PR",
keywords = {Mathematics - Probability, Primary, 60J80, secondary, 60F05, 60F17, 60B10, 68P10, 60G42},
year = 2014,
month = oct,
adsurl = {http://adsabs.harvard.edu/abs/2014arXiv1410.0469G},
adsnote = {Provided by the SAO/NASA Astrophysics Data System}
}
@article{b1992,
author = "Biggins, J. D.",
doi = "10.1214/aop/1176989921",
fjournal = "The Annals of Probability",
journal = "Ann. Probab.",
month = "01",
number = "1",
pages = "137--151",
publisher = "The Institute of Mathematical Statistics",
title = "Uniform Convergence of Martingales in the Branching Random Walk",
url = "http://dx.doi.org/10.1214/aop/1176989921",
volume = "20",
year = "1992"
}
@article {r1970,
AUTHOR = {Rosenthal, Haskell P.},
TITLE = {On the subspaces of {$L\sp{p}$} {$(p>2)$} spanned by
sequences of independent random variables},
JOURNAL = {Israel J. Math.},
FJOURNAL = {Israel Journal of Mathematics},
VOLUME = {8},
YEAR = {1970},
PAGES = {273--303},
ISSN = {0021-2172},
MRCLASS = {46.35},
MRNUMBER = {0271721 (42 \#6602)},
MRREVIEWER = {A. Pietsch},
}
@book {MitzenmacherUpfal2005,
AUTHOR = {Mitzenmacher, Michael and Upfal, Eli},
TITLE = {Probability and computing},
NOTE = {Randomized algorithms and probabilistic analysis},
PUBLISHER = {Cambridge University Press},
ADDRESS = {Cambridge},
YEAR = {2005},
PAGES = {xvi+352},
ISBN = {0-521-83540-2},
MRCLASS = {68-01 (60C05 60G42 60J10 60J25 60K25 68W20 68W40)},
MRNUMBER = {2144605 (2006d:68002)},
MRREVIEWER = {Mark R. Jerrum},
}
@book {Williams1991,
AUTHOR = {Williams, David},
TITLE = {Probability with martingales},
SERIES = {Cambridge Mathematical Textbooks},
PUBLISHER = {Cambridge University Press},
ADDRESS = {Cambridge},
YEAR = {1991},
PAGES = {xvi+251},
ISBN = {0-521-40455-X; 0-521-40605-6},
MRCLASS = {60-01 (60G42)},
MRNUMBER = {1155402 (93d:60002)},
MRREVIEWER = {Jia Gang Wang},
}
@article {cfv2001,
AUTHOR = {Cl{\'e}ment, J. and Flajolet, P. and Vall{\'e}e, B.},
TITLE = {Dynamical sources in information theory: a general analysis of
trie structures},
NOTE = {Average-case analysis of algorithms (Princeton, NJ, 1998)},
JOURNAL = {Algorithmica},
FJOURNAL = {Algorithmica. An International Journal in Computer Science},
VOLUME = {29},
YEAR = {2001},
NUMBER = {1-2},
PAGES = {307--369},
ISSN = {0178-4617},
CODEN = {ALGOEJ},
MRCLASS = {68P05 (37A35 37B10)},
MRNUMBER = {MR1887308 (2003b:68033)},
MRREVIEWER = {Robert P. Dobrow},
DOI = {10.1007/BF02679623},
URL = {http://dx.doi.org/10.1007/BF02679623},
}
@incollection {bf2012,
AUTHOR = {Bindjeme, Patrick and Fill, James Allen},
TITLE = {Exact {$L^2$}-distance from the limit for {Q}uick{S}ort key
comparisons (extended abstract)},
BOOKTITLE = {23rd {I}ntern. {M}eeting on {P}robabilistic, {C}ombinatorial,
and {A}symptotic {M}ethods for the {A}nalysis of {A}lgorithms
({A}of{A}'12)},
SERIES = {Discrete Math. Theor. Comput. Sci. Proc., AQ},
PAGES = {339--348},
PUBLISHER = {Assoc. Discrete Math. Theor. Comput. Sci., Nancy},
YEAR = {2012},
MRCLASS = {68P10},
MRNUMBER = {2957340},
}
@article {Fil2013,
AUTHOR = {James Allen Fill},
TITLE = {Distributional convergence for the number of symbol comparisons used by QuickSort},
JOURNAL = {Ann. Appl. Probab.},
FJOURNAL = {Annals of Applied Probability},
YEAR = {2013},
VOLUME = {23},
NUMBER = {3},
PAGES = {1129-1147},
ISSN = {1050-5164},
DOI = {10.1214/12-AAP866},
ARXIV = {1202.2601},
SICI = {1050-5164(2013)23:3<1129:DCFTNO>2.0.CO;2-J},
}
@BOOK{c2001,
AUTHOR = "K. L. Chung",
TITLE = "A Course in Probability Theory",
PUBLISHER = "Academic Press",
YEAR = "2001",
address = "London",
edition = "3rd",
file = F
}
@ARTICLE{d1984,
AUTHOR = "L. Devroye",
TITLE = "Exponential Bounds for the Running Time of a Selection Algorithm",
JOURNAL = "Journal of Computer and System Sciences",
YEAR = "1984",
volume = "29",
pages = "1--7",
file = F
}
@ARTICLE{d2001,
AUTHOR = "L. Devroye",
TITLE = "On the Probablistic Worst-Case Time of ``{F}ind''",
JOURNAL = "Algorithmica",
YEAR = "2001",
volume = "31",
pages = "291--303",
file = F
}
@ARTICLE{fgkpt1994,
AUTHOR = "P. Flajolet and P. Grabner and
P. Kirschenhofer and H. Prodinger and R. F.
Tichy",
TITLE = "Mellin transforms and asymptotics: digital sums",
JOURNAL = "Theoretical Computer Science",
YEAR = "1994",
volume = "123",
pages = "291--314",
file = F
}
@article{fj2002,
author = {J. A. Fill and S. Janson},
title = {Quicksort asymptotics},
journal = {Journal of Algorithms},
volume = {44},
year = {2002},
issn = {0196-6774},
pages = {4--28},
doi = {http://dx.doi.org/10.1016/S0196-6774(02)00216-X},
publisher = {Academic Press, Inc.},
address = {Duluth, MN, USA},
}
@ARTICLE{fj2004,
AUTHOR = "J. A. Fill and S. Janson",
TITLE = "The Number of Bit Comparisons
Used by {Q}uicksort: An Average-case Analysis",
journal={Electronic Journal of Probability},
volume={17, article 43 (electronic)},
YEAR = "2012",
pages = "1--22",
file = F
}
@ARTICLE{fn2009,
AUTHOR = "J. A. Fill and T. Nakama",
TITLE = "Analysis of the Expected Number
of Bit Comparisons Required by {Q}uickselect",
JOURNAL = "Algorithmica",
volume = "58",
YEAR = "2010",
pages = "730--769",
file = F
}
@ARTICLE{fn2013,
AUTHOR = "J. A. Fill and T. Nakama",
TITLE = "Distributional convergence for the number of symbol comparisons Used by {Q}uick{S}elect",
JOURNAL = "Advances in Applied Probability",
volume = "45",
number = "2",
YEAR = "2013",
pages = "425-450",
file = F
}
@ARTICLE{fs1995,
AUTHOR = "P. Flajolet and R. Sedgewick",
TITLE = "Mellin Transforms and
Asymptotics: Finite Differences and {R}ice's
integrals",
JOURNAL = "Theoretical Computer Science",
YEAR = "1995",
pages = "101--124",
file = F
}
@ARTICLE{gr1996,
AUTHOR = "R. Gr{\"{u}}bel and U. R{\"{o}}sler",
TITLE = "Asymptotic Distribution Theory
for {H}oare's Selection Algorithm",
JOURNAL = "Advances in Applied Probability",
YEAR = "1996",
volume = "28",
pages = "252--269",
file = F
}
@ARTICLE{gp2007,
AUTHOR = "P. J. Grabner and H. Prodinger",
TITLE = "On a Constant Arising in the
Analysis of Bit Comparisons in {Q}uickselect",
JOURNAL = "Quaestiones Mathematicae",
YEAR = "to appear",
file = F
}
@ARTICLE{h1961,
AUTHOR = "C. A. R. Hoare",
TITLE = "Find (algorithm 65)",
JOURNAL = "Communications of the ACM",
YEAR = "1961",
volume = "4",
pages = "321--322",
file = F
}
@ARTICLE{ht2002,
AUTHOR = "H. Hwang and T. Tsai",
TITLE = "Quickselect and the {D}ickman Function",
JOURNAL = "Combinatorics, Probability and Computing",
YEAR = "2002",
volume = "11",
pages = "353--371",
file = F
}
@INPROCEEDINGS{k1972,
AUTHOR = "D. E. Knuth",
TITLE = "Mathematical Analysis of Algorithms",
BOOKTITLE = "Information Processing 71
(Proceedings of IFIP Congress, Ljubljana, 1971)",
YEAR = "1972",
pages = "19--27",
publisher = "North-Holland, Amsterdam",
file = F
}
@BOOK{k2002v3,
AUTHOR = "D. E. Knuth",
TITLE = "The Art of Computer
Programming. Volume 3: Sorting and Searching",
PUBLISHER = "Addison-Wesley",
YEAR = "1998",
address = "Reading, Massachusetts",
file = F
}
@BOOK{k2002v1,
AUTHOR = "D. E. Knuth",
TITLE = "The Art of Computer
Programming. Volume 1: Fundamental Algorithms",
PUBLISHER = "Addison-Wesley",
YEAR = "1998",
address = "Reading, Massachusetts",
file = F
}
@article{ks1999,
AUTHOR = "C. Knessl and W. Szpankowski",
TITLE = "Quicksort Algorithm Again Revisited",
JOURNAL = "Discrete Mathematics and Theoretical Computer Science",
YEAR = "1999",
volume = "3",
pages = "43--64",
file = F
}
@ARTICLE{lm1996,
AUTHOR = "J. Lent and H. M. Mahmoud",
TITLE = "Average-case Analysis of
Multiple {Q}uickselect: An Algorithm for Finding
Order Statistics",
JOURNAL = "Statistics and Probability Letters",
YEAR = "1996",
volume = "28",
pages = "299-310",
file = F
}
@ARTICLE{mms1995,
AUTHOR = "H. M. Mahmoud and R. Modarres and R. T. Smythe",
TITLE = "Analysis of {Q}uickselect: An
Algorithm for Order Statistics",
JOURNAL = "RAIRO Informatique Th\'{e}orique et Applications",
YEAR = "1995",
volume = "29",
pages = "255-276",
file = F
}
@ARTICLE{ms1998,
AUTHOR = "H. M. Mahmoud and R. T. Smythe",
TITLE = "Probabilistic Analysis of Multiple {Q}uickselect",
JOURNAL = "Algorithmica",
YEAR = "1998",
volume = "22",
pages = "569-584",
file = F
}
@ARTICLE{nr2002,
AUTHOR = "R. Neininger and L. R{\"{u}}schendorf",
TITLE = "Rates of Convergence for {Q}uickselect",
JOURNAL = "Journal of Algorithms",
YEAR = "2002",
volume = "44",
pages = "51-62",
file = F
}
@ARTICLE{p1995,
AUTHOR = "H. Prodinger",
TITLE = "Multiple
{Q}uickselect---{H}oare's {F}ind algorithm for
several elements",
JOURNAL = "Information Processing Letters",
YEAR = "1995",
volume = "56",
pages = "123--129",
file = F
}
@ARTICLE{r1989,
AUTHOR = "M. R{\'{e}}gnier",
TITLE = "A limiting distribution of {Q}uicksort",
JOURNAL = "RAIRO Informatique Th\'{e}orique et Applications",
YEAR = "1989",
volume = "23",
pages = "335-343",
file = F
}
@ARTICLE{r1991,
AUTHOR = "U. R{\"{o}}sler",
TITLE = "A limit theorem for {Q}uicksort",
JOURNAL = "RAIRO Informatique Th\'{e}orique et Applications",
YEAR = "1991",
volume = "25",
pages = "85-100",
file = F
}
@article{rr2001,
author = "U. R{\"{o}}sler and L. R{\"{u}}schendorf",
title = "The Contraction Method for Recursive Algorithms",
journal = "Algorithmica",
volume = "29",
number = "1",
pages = "3-33",
year = "2001",
file = F
}
@BOOK{r2002,
AUTHOR = "S. Ross",
TITLE = "A First Course in Probability",
PUBLISHER = "Prentice Hall",
YEAR = "2002",
address = "Upper Saddle River, NJ",
edition = "6th",
file = F
}
@inproceedings {vcff2009,
AUTHOR = "B. Vall\'{e}e and J. Cl\'{e}ment and J. A. Fill and P. Flajolet",
TITLE = "The number of symbol comparisons in {Q}uicksort and {Q}uickselect",
BOOKTITLE = {36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I, LNCS 5555},
PAGES = {750--763},
PUBLISHER = {Springer--Verlag},
EDITOR = {S. Albers et al.},
YEAR = {2009},
}
@ARTICLE{g1998,
author = "R. Gr{\"{u}}bel",
title = "Hoare's selection algorithm:\ A {M}arkov chain approach",
journal = "Journal of Applied Probability",
volume = "35",
pages = "36-45",
year = "1998",
file = F
}
@article {pa1995,
AUTHOR = {Paulsen, Volkert},
TITLE = {The moments of {FIND}},
JOURNAL = {J. Appl. Probab.},
FJOURNAL = {Journal of Applied Probability},
VOLUME = {34},
YEAR = {1997},
NUMBER = {4},
PAGES = {1079--1082},
ISSN = {0021-9002},
CODEN = {JPRBAM},
MRCLASS = {68P10 (60E99 68Q25)},
MRNUMBER = {MR1484039 (98k:68043)},
}
@article {df2010,
AUTHOR = {Devroye, Luc and Fawzi, Omar},
TITLE = {Simulating the {D}ickman distribution},
JOURNAL = {Statist. Probab. Lett.},
FJOURNAL = {Statistics \& Probability Letters},
VOLUME = {80},
YEAR = {2010},
NUMBER = {3-4},
PAGES = {242--247},
ISSN = {0167-7152},
CODEN = {SPLTDC},
MRCLASS = {Database Expansion Item},
MRNUMBER = {2575452},
DOI = {10.1016/j.spl.2009.10.013},
URL = {http://dx.doi.org/10.1016/j.spl.2009.10.013},
}
@article {fh2010,
AUTHOR = {Fill, James Allen and Huber, Mark Lawrence},
TITLE = {Perfect simulation of {V}ervaat perpetuities},
JOURNAL = {Electron. J. Probab.},
FJOURNAL = {Electronic Journal of Probability},
VOLUME = {15},
YEAR = {2010},
PAGES = {no. 4, 96--109},
ISSN = {1083-6489},
MRCLASS = {60J10 (60E05 60E15 65C05 68U20)},
MRNUMBER = {2587562 (2011a:60261)},
MRREVIEWER = {David J. Galvin},
DOI = {10.1214/EJP.v15-734},
URL = {http://dx.doi.org/10.1214/EJP.v15-734},
}
@article {MR1454110,
AUTHOR = {Kodaj, B. and M{\'o}ri, T. F.},
TITLE = {On the number of comparisons in {H}oare's algorithm
``{FIND}''},
JOURNAL = {Studia Sci. Math. Hungar.},
FJOURNAL = {Studia Scientiarum Mathematicarum Hungarica. A Quarterly of
the Hungarian Academy of Sciences},
VOLUME = {33},
YEAR = {1997},
NUMBER = {1-3},
PAGES = {185--207},
ISSN = {0081-6906},
CODEN = {SSMHAX},
MRCLASS = {68P10 (60F99 68Q25)},
MRNUMBER = {1454110 (98a:68041)},
}
@book {lc1998,
AUTHOR = {Lehmann, E. L. and Casella, George},
TITLE = {Theory of point estimation},
SERIES = {Springer Texts in Statistics},
EDITION = {Second},
PUBLISHER = {Springer-Verlag, New York},
YEAR = {1998},
PAGES = {xxvi+589},
ISBN = {0-387-98502-6},
MRCLASS = {62F10 (62-01)},
MRNUMBER = {1639875 (99g:62025)},
MRREVIEWER = {Xuming He},
}
@article {f1999,
AUTHOR = {Flajolet, Philippe},
TITLE = {Singularity analysis and asymptotics of {B}ernoulli sums},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {215},
YEAR = {1999},
NUMBER = {1-2},
PAGES = {371--381},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {05A16 (05A15 68Q25)},
MRNUMBER = {1678788 (2000a:05015)},
MRREVIEWER = {Yong Gao Chen},
DOI = {10.1016/S0304-3975(98)00220-5},
URL = {http://dx.doi.org/10.1016/S0304-3975(98)00220-5},
}
@article {h1962,
AUTHOR = {Hoare, C. A. R.},
TITLE = {Quicksort},
JOURNAL = {Comput. J.},
FJOURNAL = {The Computer Journal},
VOLUME = {5},
YEAR = {1962},
PAGES = {10--15},
ISSN = {0010-4620},
MRCLASS = {68.00},
MRNUMBER = {MR0142216 (25 \#5609)},
MRREVIEWER = {C. C. Gotlieb},
}
@book{clrs2009,
author = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
title = {Introduction to Algorithms, Third Edition},
year = {2009},
isbn = {0262033844, 9780262033848},
edition = {3rd},
publisher = {The MIT Press},
}
@book{bd2001,
title={Mathematical Statistics: Basic Ideas and Selected Topics},
author={Bickel, P.J. and Doksum, K.A.},
number={v. 1},
isbn={9780138503635},
lccn={00031377},
series={Holden-Day series in probability and statistics},
year={2001},
publisher={Prentice Hall}
}