The Distributional Tail of Worst-Case Quickselect

We study the almost surely finite random variable $S$ defined by the distributional fixed-point equation $$S1+\max \{U{S}^{\mathrm{\prime }},(1-U)S^{\mathrm{\prime }\mathrm{\prime }}\},U\sim \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{f}(0,1),$$ where $S^{\mathrm{\prime }}$ and $S^{\mathrm{\prime }\mathrm{\prime }}$ 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),t\to \mathrm{\infty }\mathrm{.}$$ 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.