The Distributional Tail of Worst-Case Quickselect
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918446981185536 |
|---|---|
| author | Płecha, Witold |
| author_facet | Płecha, Witold |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13149 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Distributional Tail of Worst-Case Quickselect Płecha, Witold Probability Data Structures and Algorithms 60C05 (Primary), 68W40, 68W20 F.2.2; G.3 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. |
| title | The Distributional Tail of Worst-Case Quickselect |
| topic | Probability Data Structures and Algorithms 60C05 (Primary), 68W40, 68W20 F.2.2; G.3 |
| url | https://arxiv.org/abs/2604.13149 |