pith. sign in

arxiv: 2604.13149 · v1 · submitted 2026-04-14 · 🧮 math.PR · cs.DS

The Distributional Tail of Worst-Case Quickselect

Witold P{\l}echa (Mathematical Institute , University of Wroc{\l}aw) This is my paper

Pith reviewed 2026-05-10 14:05 UTC · model grok-4.3

classification 🧮 math.PR cs.DS
keywords Quickselectworst-case analysisdistributional fixed pointtail asymptoticsrate functionChernoff boundsecond moment methodbinary search tree
0
0 comments X

The pith

The right tail of the worst-case Quickselect limit S satisfies -log P(S>t) = t log t + O(t log log t) as t tends to infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper analyzes the right tail of the limiting distribution for the worst-case number of comparisons in Quickselect under uniform random pivots. It proves explicit one-sided bounds on the large deviation rate function and pins down its leading asymptotic behavior as t log t plus a lower order term. A reader would care because this quantifies how rare extreme worst-cases are in a core sorting algorithm, with potential implications for understanding the probabilistic complexity of similar recursive procedures. The bounds are obtained by embedding into binary search trees and applying a second-moment method combined with moment-generating function comparisons. As a secondary result, the paper provides a computational scheme to bound the expectation of S from above.

Core claim

The almost surely finite random variable S defined by the fixed-point equation S equal in distribution to 1 plus the maximum of U times S prime and (1-U) times S double prime, where U is uniform on (0,1), has a right tail whose rate function satisfies minus log of the probability that S exceeds t equals t times log t plus order t log log t as t goes to infinity. This is established by embedding the process into a binary search tree and applying a one-level second-moment method together with a moment-generating-function comparison. The work also develops a distribution-function-based iteration to produce explicit upper bounds on the expectation of S.

What carries the argument

The distributional fixed-point equation S ≐ 1 + max{US', (1-U)S''} for independent copies S', S'' of S and U uniform on (0,1); it encodes the recursive structure of worst-case Quickselect and enables recursive tail analysis via embedding in binary search trees.

If this is right

  • Explicit one-sided bounds on the rate function -log P(S>t) are derived for all large t.
  • A pointwise Chernoff majorant for the tail probability is obtained as a byproduct.
  • The first-order asymptotic growth of the rate function is identified as t log t.
  • An order-preserving lower iteration scheme with mesh discretization yields computer-assisted upper bounds on E[S].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This tail asymptotic may extend to other related distributional equations arising in divide-and-conquer algorithms.
  • The numerical bounding method could be refined for rigorous certified upper bounds on the mean rather than floating-point estimates.
  • Similar techniques might apply to the analysis of worst-case behavior in other pivot-based selection algorithms.

Load-bearing premise

The almost surely finite random variable S satisfying the given distributional fixed-point equation exists and arises as the limit of the normalized worst-case comparisons in the Devroye model of Quickselect.

What would settle it

A direct computation or simulation of the tail probabilities for increasingly large t that shows the ratio of -log P(S>t) to t log t deviating from 1 or the error term exceeding O(t log log t) would falsify the claimed asymptotic.

Figures

Figures reproduced from arXiv: 2604.13149 by University of Wroc{\l}aw), Witold P{\l}echa (Mathematical Institute.

Figure 1
Figure 1. Figure 1: A random realization of the labelled binary tree from [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Upper bounds Um produced by the mesh scheme as a function of the iteration number. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Selected mesh iterates produced by the conservative mesh scheme for two floating-point [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
read the original abstract

We study the almost surely finite random variable $S$ defined by the distributional fixed-point equation \[ S \stackrel{d}{=} 1 + \max\{US', (1-U)S''\}, \qquad U \sim \mathrm{Unif}(0,1), \] where $S'$ and $S''$ are independent copies of $S$, independent of $U$. This random variable arises as the almost sure limit of the normalized worst-case number of key comparisons used by classical Quickselect with uniformly chosen pivots in the model of Devroye. Our first contribution concerns the right tail of $S$. We prove explicit one-sided bounds for the rate function $-\log \mathbb{P}(S>t)$ and, in particular, identify its first-order asymptotic growth: \[ -\log \mathbb{P}(S>t) = t \log t + O(t \log \log t), \qquad t \to \infty. \] The argument combines a binary-search-tree embedding and a one-level second-moment method with a moment-generating-function comparison inspired by ideas of Alsmeyer and Dyszewski for the nonhomogeneous smoothing transform. As a byproduct, we obtain an explicit pointwise Chernoff majorant for the tail. Our second contribution is a distribution-function scheme for deriving explicit upper bounds on $\mathbb{E}[S]$. Starting from the fixed-point equation at the level of the distribution function, we construct an order-preserving lower iteration and a conservative mesh discretization suited to computer-assisted upper bounds on the mean. We illustrate the latter numerically in floating-point arithmetic, but do not pursue a certified numerical proof here.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript studies the almost surely finite random variable S satisfying the distributional fixed-point equation S =_d 1 + max{US', (1-U)S''} with U ~ Unif(0,1) and independent copies S', S''. This S arises as the limit of the normalized worst-case number of comparisons in Devroye's model of Quickselect. The central result is the first-order asymptotic -log P(S > t) = t log t + O(t log log t) as t → ∞, proved via a binary-search-tree embedding combined with a one-level second-moment method on a suitable non-negative random variable Z and an MGF comparison inspired by Alsmeyer-Dyszewski. A secondary contribution is an order-preserving lower iteration on the distribution function together with a conservative mesh discretization that yields explicit (numerically illustrated) upper bounds on E[S].

Significance. If the claimed asymptotic holds with the stated error term, the work supplies a sharp large-deviation rate for the tail of a canonical recursive distributional equation arising in the analysis of algorithms. The BST embedding plus one-level second-moment technique, together with the explicit Chernoff majorant obtained as a byproduct, offers a concrete template that may extend to other non-homogeneous smoothing transforms. The distribution-function iteration scheme provides a practical, order-preserving route to rigorous upper bounds on the mean without requiring closed-form solutions.

major comments (1)
  1. [Proof of the lower tail bound (the section containing the second-moment calculation on the BST embedding)] The lower bound -log P(S > t) ≥ t log t + Ω(t log log t) rests on the one-level second-moment method applied to the embedded process. For the ratio E[Z]^2 / E[Z^2] to produce an error no larger than O(t log log t), the relative second moment of the (truncated or weighted) path-count random variable Z must itself be bounded by exp(O(t log log t)). The manuscript should supply an explicit estimate showing that the dependence between the two subtrees does not inflate Var(Z) beyond this threshold; without such a bound the lower bound may degrade to t log t + o(t log t) or weaker.
minor comments (2)
  1. [Section on the distribution-function iteration and numerical results] The numerical illustration of the mean upper bounds is performed in ordinary floating-point arithmetic; a brief discussion of rounding-error control or a note that the bounds are not certified would clarify the status of the reported numbers.
  2. [Section introducing the BST embedding] The statement of the fixed-point equation and the definition of the auxiliary random variable Z used in the second-moment argument would benefit from an explicit display of the truncation or weighting function applied to the path count.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on the manuscript. We address the single major comment below and will revise the paper to incorporate the requested explicit estimate on the relative second moment.

read point-by-point responses

  1. Referee: The lower bound -log P(S > t) ≥ t log t + Ω(t log log t) rests on the one-level second-moment method applied to the embedded process. For the ratio E[Z]^2 / E[Z^2] to produce an error no larger than O(t log log t), the relative second moment of the (truncated or weighted) path-count random variable Z must itself be bounded by exp(O(t log log t)). The manuscript should supply an explicit estimate showing that the dependence between the two subtrees does not inflate Var(Z) beyond this threshold; without such a bound the lower bound may degrade to t log t + o(t log t) or weaker.

    Authors: We agree that an explicit bound on E[Z²]/E[Z]² is required to confirm the Ω(t log log t) error term. In the BST embedding the left and right sub-processes are conditionally independent given the pivot U. We will add a dedicated lemma that expands E[Z²] using this conditional independence, bounds the variance contribution of each subtree recursively via the MGF majorant already developed for the smoothing transform, and shows that the cross-covariance terms contribute at most a factor exp(O(t log log t)). The resulting estimate will be inserted into the proof of the lower tail bound, ensuring the Paley–Zygmund application yields the claimed error without degradation. This addition will appear in the revised Section on the second-moment argument. revision: yes

Circularity Check

0 steps flagged

No circularity: tail bounds derived from fixed-point definition via external-inspired methods

full rationale

The paper defines S explicitly via the given distributional fixed-point equation and derives the claimed one-sided bounds on -log P(S>t) by combining a binary-search-tree embedding, a one-level second-moment method, and an MGF comparison drawn from external work of Alsmeyer-Dyszewski. No parameters are fitted to data and then relabeled as predictions; no self-citations are load-bearing for the central claims; the fixed-point is an input definition rather than a self-referential output; and the asymptotic is obtained as a theorem rather than by renaming or smuggling an ansatz. The derivation chain is therefore independent of its own conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the existence of the a.s.-finite fixed-point solution S to the given distributional equation in the Devroye Quickselect model; this is a standard domain assumption taken from prior work rather than re-derived here.

axioms (1)
  • domain assumption There exists an almost surely finite random variable S satisfying S =_d 1 + max{U S', (1-U) S''} with U uniform on (0,1) and S', S'' independent copies of S.
    This is the defining property of S invoked throughout the abstract as the starting point for both the tail analysis and the mean-bound scheme.

pith-pipeline@v0.9.0 · 5603 in / 1304 out tokens · 48707 ms · 2026-05-10T14:05:12.112201+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    Thin tails of fixed points of the nonhomogeneous smoothing transform

    [AD17] G. Alsmeyer and P. Dyszewski. “Thin tails of fixed points of the nonhomogeneous smoothing transform”. In:Stochastic Processes and their Applications127.9 (2017), pp. 3014–3041.doi: 10.1016/j.spa.2017.01.008. [Dev01] L. Devroye. “On the Probabilistic Worst-Case Time of FIND”. In:Algorithmica 31.3 (2001), pp. 291–303.doi: 10.1007/s00453-001-0046-2. [...

    work page doi:10.1016/j.spa.2017.01.008 2017

  2. [2]

    Hoare’s Selection Algorithm: A Markov Chain Approach

    2307/1427920. [Grü98] R. Grübel. “Hoare’s Selection Algorithm: A Markov Chain Approach”. In:Journal of Applied Probability35.1 (1998), pp. 36–45.doi: 10.1239/jap/1032192549. [Hoa61] C. A. R. Hoare. “Find (Algorithm 65)”. In:Communications of the ACM4.7 (1961), pp. 321–322.doi: 10.1145/366622.366647. [HT02] H.-K. Hwang and T.-H. Tsai. “Quickselect and the ...

    work page doi:10.1239/jap/1032192549 1998

  3. [3]

    Exponential Tail Bounds for Max-Recursive Sequences

    Amsterdam: North-Holland, 1972, pp. 19–27. [RS06] L. Rüschendorf and E.-M. Schopp. “Exponential Tail Bounds for Max-Recursive Sequences”. In:Electronic Communications in Probability11 (2006), pp. 266–277. doi: 10.1214/ECP.v11-1227. [Val+09] B. Vallée, J. Clément, J. A. Fill, and P. Flajolet. “The Number of Symbol Comparisons in QuickSort and QuickSelect”....

    work page doi:10.1214/ecp.v11-1227 1972

  4. [4]

    Berlin: Springer, 2009, pp

    Lecture Notes in Computer Science. Berlin: Springer, 2009, pp. 750–763.doi: 10.1007/978-3-642-02927-1_62. 27

    work page doi:10.1007/978-3-642-02927-1_62 2009