{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:09:37Z","timestamp":1763543377534,"version":"3.45.0"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T00:00:00Z","timestamp":1754870400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,11]]},"abstract":"Abstract<\/jats:title>\n \n QuickSelect<\/jats:monospace>\n (also known as\n Find<\/jats:monospace>\n ), introduced by Hoare ((1961)\n Commun. ACM<\/jats:italic>\n 4<\/jats:bold>\n 321\u2013322.), is a randomized algorithm for selecting a specified order statistic from an input sequence of\n \n \n \n $n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n objects, or rather their identifying labels usually known as\n keys<\/jats:italic>\n . The keys can be numeric or symbol strings, or indeed any labels drawn from a given linearly ordered set. We discuss various ways in which the cost of comparing two keys can be measured, and we can measure the efficiency of the algorithm by the total cost of such comparisons.\n <\/jats:p>\n \n We define and discuss a closely related algorithm known as\n QuickVal<\/jats:monospace>\n and a natural probabilistic model for the input to this algorithm;\n QuickVal<\/jats:monospace>\n searches (almost surely unsuccessfully) for a specified\n population<\/jats:italic>\n quantile\n \n \n \n $\\alpha \\in [0, 1]$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in an input sample of size\n \n \n \n $n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Call the total cost of comparisons for this algorithm\n \n \n \n $S_n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We discuss a natural way to define the random variables\n \n \n \n $S_1, S_2, \\ldots$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n on a common probability space. For a general class of cost functions, Fill and Nakama ((2013)\n Adv. Appl. Probab.<\/jats:italic>\n 45<\/jats:bold>\n 425\u2013450.) proved under mild assumptions that the scaled cost\n \n \n \n $S_n \/ n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of\n QuickVal<\/jats:monospace>\n converges in\n \n \n \n $L^p$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and almost surely to a limit random variable\n \n \n \n $S$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . For a general cost function, we consider what we term the\n QuickVal<\/jats:monospace>\n residual:\n \n \n \n \\begin{equation*} \\rho _n \\,{:\\!=}\\, \\frac {S_n}n - S. \\end{equation*}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n <\/jats:p>\n \n The residual is of natural interest, especially in light of the previous analogous work on the sorting algorithm\n QuickSort<\/jats:monospace>\n (Bindjeme and Fill (2012)\n 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), Discrete Mathematics, and Theoretical Computer Science Proceedings, AQ<\/jats:italic>\n , Association: Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 339\u2013348; Neininger (2015)\n Random Struct. Algorithms<\/jats:italic>\n 46<\/jats:bold>\n 346\u2013361;\u00a0Fuchs (2015)\n Random Struct. Algorithms<\/jats:italic>\n 46<\/jats:bold>\n 677\u2013687; Gr\u00fcbel and Kabluchko (2016)\n Ann. Appl. Probab.<\/jats:italic>\n 26<\/jats:bold>\n 3659\u20133698; Sulzbach (2017)\n Random Struct. Algorithms<\/jats:italic>\n 50<\/jats:bold>\n 493\u2013508). In the case\n \n \n \n $\\alpha = 0$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of\n QuickMin<\/jats:monospace>\n with unit cost per key-comparison, we are able to calculate\u2013\u00e0la Bindjeme and Fill for\n QuickSort<\/jats:monospace>\n (Bindjeme and Fill (2012)\n 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), Discrete Mathematics and Theoretical Computer Science Proceedings<\/jats:italic>\n , AQ, Association: Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 339\u2013348.)\u2013the exact (and asymptotic)\n \n \n \n $L^2$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -norm of the residual. We take the result as motivation for the scaling factor\n \n \n \n $\\sqrt {n}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for the\n QuickVal<\/jats:monospace>\n residual for\n general<\/jats:italic>\n population quantiles and for\n general<\/jats:italic>\n cost. We then prove\n in general<\/jats:italic>\n (under mild conditions on the cost function) that\n \n \n \n $\\sqrt {n}\\,\\rho _n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n converges in law to a scale mixture of centered Gaussians, and we also prove convergence of moments.\n <\/jats:p>","DOI":"10.1017\/s0963548325100102","type":"journal-article","created":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T05:43:32Z","timestamp":1754891012000},"page":"780-802","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Convergence of the\n QuickVal<\/tt>\n residual"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1023-0398","authenticated-orcid":false,"given":"James Allen","family":"Fill","sequence":"first","affiliation":[{"name":"The Johns Hopkins University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9281-6857","authenticated-orcid":false,"given":"Jason","family":"Matterer","sequence":"additional","affiliation":[{"name":"Systems & Technology Research LLC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,8,11]]},"reference":[{"key":"S0963548325100102_ref24","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1995290402551"},{"key":"S0963548325100102_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90009-6"},{"key":"S0963548325100102_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771562"},{"key":"S0963548325100102_ref23","first-page":"185","article-title":"On the number of comparisons in Hoare\u2019s algorithm \u201cFIND\"","volume":"33","author":"Kodaj","year":"1997","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548325100102_ref17","first-page":"321","article-title":"Find (algorithm 65)","volume":"4","author":"Hoare","year":"1961","journal-title":"Commun. ACM"},{"key":"S0963548325100102_ref20","first-page":"9:1","volume-title":"35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)","volume":"302","author":"Ischebeck","year":"2024"},{"key":"S0963548325100102_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/12-AAP866"},{"volume-title":"A Course in Probability Theory","year":"2001","author":"Chung","key":"S0963548325100102_ref2"},{"key":"S0963548325100102_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000121"},{"key":"S0963548325100102_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9294-3"},{"key":"S0963548325100102_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1188"},{"key":"S0963548325100102_ref18","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"volume-title":"PhD dissertation","year":"2015","author":"Matterer","key":"S0963548325100102_ref25"},{"key":"S0963548325100102_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20524"},{"key":"S0963548325100102_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00220-5"},{"key":"S0963548325100102_ref15","doi-asserted-by":"publisher","DOI":"10.2307\/1427920"},{"key":"S0963548325100102_ref1","first-page":"339","volume-title":"23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA\u201912), Discrete Mathematics and Theoretical Computer Science Proceedings, AQ","author":"Bindjeme","year":"2012"},{"key":"S0963548325100102_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v15-734"},{"key":"S0963548325100102_ref22","first-page":"19","volume-title":"Information Processing 71 (Proceedings of IFIP Congress, Ljubljana, 1971)","author":"Knuth","year":"1972"},{"key":"S0963548325100102_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005138"},{"key":"S0963548325100102_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_62"},{"key":"S0963548325100102_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20497"},{"key":"S0963548325100102_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2009.10.013"},{"key":"S0963548325100102_ref7","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1370870125"},{"key":"S0963548325100102_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003325"},{"key":"S0963548325100102_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/22-EJP899"},{"key":"S0963548325100102_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20674"},{"key":"S0963548325100102_ref14","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032192549"},{"key":"S0963548325100102_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0046-2"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325100102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:04:47Z","timestamp":1763543087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325100102\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,11]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["S0963548325100102"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325100102","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2025,8,11]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}