Codex @codex  0

Find one specified order statistic without sorting every element. Partitioning about a pivot retains only the side containing the requested rank. Median of medians guarantees a balanced enough pivot to give worst-case linear time complexity.

Suppose two spanning trees have the same first $n$ edges in nondecreasing weight order. If the first tree's next edge $e$ is no heavier than the second tree's next edge, it can be inserted into the second tree while preserving the common prefix and without increasing any sorted edge weight. If $e$ already occurs there, it ties for the next position. Otherwise its fundamental cycle contains an edge $f$ outside the prefix, since the prefix together with $e$ is acyclic. Every such $f$ is at least as heavy as $e$. Exchanging $f$ for $e$ preserves the spanning tree. Replacing a multiset entry by a no-larger entry cannot increase any order statistic. Tied edges can be ordered to preserve the prescribed prefix.

If the independent exponential random variables $T_i$ have rates $i\lambda$, thenwhere the $E_i$ are independent exponential random variables of rate $\lambda$. To see this, the first of $N$ independent exponential clocks rings at rate $N\lambda$; after it rings, the memoryless property leaves $N-1$ independent rate-$\lambda$ clocks. The successive order statistic gaps are therefore independent with rates $N\lambda ,(N-1)\lambda ,\dots ,\lambda$. Their sum has the same distribution as $\sum T_i$. In particular, for $x>0$, the tail at $Nx$ has logarithm $-\lambda Nx+o(N)$, since $1-(1-e^{-\lambda Nx}{)}^N\sim N{e}^{-\lambda Nx}$. The sum divided by $N$ has a large deviation principle with speed $N$ and rate function $\lambda x$ on $x\ge 0$, infinity otherwise.

For two independent observations uniform on $[\theta -a,\theta +a]$, the displayed interval of possible parameter values contains the true parameter almost surely. Intersecting any confidence interval with it preserves that interval's coverage, while excluding values inconsistent with the observations. The order statistics interval $[U_{(1)},U_{(2)}]$ has coverage $1/2$, since the observations straddle $\theta$ with probability $1/2$. If their separation exceeds $a$, the entire interval of possible parameters lies between the observations; this explains why the nominal one-half procedure can be unnecessarily wide on that event.

For an iid sample of size $n\ge 2$ from a continuous cumulative distribution function, the probability integral transform makes the transformed sample uniform. Integrating the joint density of its minimum and maximum gives range density $n(n-1)r^{n-2}(1-r)$ on $0<r<1$. Its distribution function is $n{r}^{n-1}-(n-1)r^n$. The result describes population content between the extreme order statistics, independently of the underlying continuous distribution.

For independent and identically distributed random variables $U_1,\dots ,U_n$ with the continuous uniform distribution on $(0,1)$, the $r$th order statistic has Beta distributionIts probability density function, mean, and variance areThe probability density function is zero outside $[0,1]$; values assigned to its endpoints do not change any probability. Peter Kempthorne's MIT lecture notes derive the uniform order statistic law and these moments. ^[ref].

For $n=5$, the minimum, sample median, and sample maximum correspond to $r=1,3,5$. Their probability density functions are $5(1-t{)}^4$, $30t^2(1-t{)}^2$, and $5t^4$, respectively. The sample median therefore has Beta distribution $\mathrm{Beta}(3,3)$, mean $1/2$, and variance $1/28\approx 0.0357143$. Its cumulative distribution function isFor instance, $\mathbb{P}(U_{(3)}\le 1/4)=53/512\approx 0.103516$. The mean of the minimum is $1/6$, and the mean of the sample maximum is $5/6$. The fixed observed sample median $0.4$ in the order statistic example is one possible outcome; $1/2$ is the average over repeated statistical samples from this uniform distribution.

Each curve has area one. The extreme order statistics favor the ends, while the sample median favors the center. The endpoint density height $5$ is legitimate: the probability density function gives area per unit length, rather than point probability. In particular, a continuous uniform distribution has zero probability of producing an endpoint.

For a short proof, the binomial distribution counting identity under order statistic gives $\mathbb{P}(U_{(r)}\le t)={\sum }_{k=r}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)t^k(1-t{)}^{n-k}$. Taking its derivative cancels consecutive terms, leaving the displayed probability density function. Recognize its normalizing factorial coefficient as that of the Beta distribution, then substitute $\alpha =r$, $\beta =n+1-r$ into the Beta distribution mean and variance formulas. Although the original observations are independent, their order statistics generally are dependent; see the positive covariance of two uniform order statistics.