What is the estimation bias of the top estimate in a list sorted by value? Let's make the problem as simple as possible. Assume two related random variables, $X_1$ and $X_2$. On the basis of some data we estimate their true means $\mu_{X_1}$ and $\mu_{X_2}$ by sample means $\hat\mu_{X_1}$ and $\hat\mu_{X_2}$. These estimates are unbiased.
But now let's sort our two random variables by their sample means and look at the variable with the highest sample mean. Now for this top-of-the-list random variable the sample mean is now a biased estimator of its true mean (under some reasonable assumptions, e.g. that the means of these random variables are themselves distributed in a certain way and that distribution has a mean) -- that's easy to verify by Monte-Carlo. For obviousness, take not two but a thousand random variables and make their true means similar.
The question is what is this bias and how do I analytically calculate it? I'd also appreciate some conceptual discussion on how does estimation bias arise out of sorting by estimated values.
 A: Let $X_{in}$ be i.i.d. copies of $X_i$ and let $Y_i$ denote the $i^{th}$ sample mean
$$
Y_i = \frac{1}{N_i} \sum_{n=1}^{N_i} X_{in} \enspace,
$$
and let $F_i$ denote its cumulative distribution function (CDF). Note that $Y_i$ and $F_i$ are fully defined when we have the distribution of the random variable $X_i$ and the number of samples for this variable. Then, the probability that the highest sample mean is smaller then some value $x$ is equal to the probability that all sample means are smaller than $x$, and therefore its distribution is defined by:
$$
F_{\max}(x) = P( \max_i Y_i < x ) = \prod_{i=1}^M P( Y_i < x ) = \prod_{i=1}^M F_i(x) \enspace,
$$
where $N_i$ is the number of samples for the $i^{th}$ random variable, and $M$ is the number of random variables.
Some work has been done to determine the bias of the maximum sample average to the actual maximum mean:
$$
E\left\{ \max_i Y_i \right\} - \max_i E \{ X_i \} \enspace.\tag{1}
$$
See, for instance, this paper for some bounds. So why does this bias occur? The intuitive reason is that when you select the highest sample mean, you are more likely to select an overestimated mean than you are to select an underestimated mean. More formally, it is a direct consequence of Jensen's inequality, that states $E f(X) > f( E X )$ for any strictly convex $f$ (note that $\max$ is a convex operator).
You ask about a different, but related, bias: the difference between the maximum sample mean and the true mean of the corresponding random variable that has yielded the maximum sample average. This corresponds to:
$$
\sum_{i=1}^M P\left( Y_i = \max_j Y_j \right) E \left\{ Y_i - E \left\{ X_i \right\} \middle| Y_i = \max_j Y_j \right\} \enspace,
$$
which can be rewritten as
$$
E \left\{ \max_i Y_i \right\} - \sum_{i=1}^M P\left( Y_i = \max_j Y_j \right) E \left\{ X_i \right\} \enspace.
$$
I don't know of previous work on this particular bias, but it is easy to show that this bias is lower bounded by the bias in $(1)$ (since a weighted sum is always smaller than the maximum).
In general, the resulting bias may not have a very 'pleasant' analytical form, but it is easy enough to approximate numerically.
