{"id":"arxiv/2604.13149","url":"https://arxiv.org/abs/2604.13149","tags":["math.PR","cs.DS"],"score":0,"title":"The Distributional Tail of Worst-Case Quickselect","domain":"math.PR","source":"arxiv","authors":["Witold Płecha"],"reviews":0,"subject":"math.PR","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-14","reactions":{}}