4
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ I don't follow the procedure. In the simple case, when you "sort ... by their sample means" you merely identify which of $X_1$ and $X_2$ has the higher sample mean. This does not change either $\mu_{X_1}$ nor $\mu_{X_2}$, whence they must remain unbiased. I sounds like you're doing something additional which is not clearly described in the question. $\endgroup$
    – whuber ♦
    Commented Sep 5, 2012 at 18:12
  • 1
    $\begingroup$ Try a Monte-Carlo :-) Take a thousand random variables with their means ~N(0,1), generate sample data (say, 100 data points per variable), calculate sample means, sort the variables by sample means, take the top variable and see whether its sample mean is an unbiased estimator of its true mean. Intuitively, realizations with large positive estimation errors will gravitate towards the top of the sorted list. $\endgroup$
    – Baloo
    Commented Sep 5, 2012 at 18:22
  • $\begingroup$ A paper you may be interested in is P. Hall and H. Miller, Modeling the variability of rankings, Ann. Statist., vol. 38, no. 5 (2010), 2652-2677. There the question is a bit different; instead of asking about bias, they are interested in the number of entities which are correctly sorted based on noisy observations. The model is quite similar to the one you propose, except that they allow dependence in the noise between the entities observed. At any rate, the focus is different, but may be a useful connection to the literature. $\endgroup$
    – cardinal
    Commented Sep 5, 2012 at 18:43
  • $\begingroup$ The language in your question is a bit fast and loose, which I suspect is what led @whuber to interpret your question differently than you intended. $\endgroup$
    – cardinal
    Commented Sep 5, 2012 at 18:45
  • $\begingroup$ @cardinal Thank you, connections to the literature are very useful. I am sure I am not the first one to concern myself with this issue. $\endgroup$
    – Baloo
    Commented Sep 5, 2012 at 18:59

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi MLS, This is a good start. A couple notes: (a) Though I see this rather often for these kinds of arguments, there is no need to appeal to (a generalized form of) Jensen's inequality in the first part. Note that monotonicity of expectation is already enough. (b) I don't believe you can drop the conditioning in the second term of your last equation. For example, if the latent $X_i$ are iid, your second term just reduces to the unconditional mean, which can't be correct. :-) $\endgroup$
    – cardinal
    Commented Sep 6, 2012 at 14:29
  • $\begingroup$ Also, just a minor typo, but the first equation should use a double index, i.e., $X_{in}$. $\endgroup$
    – cardinal
    Commented Sep 6, 2012 at 14:45
  • $\begingroup$ @cardinal Thanks for the comments! (a) Is monotonicity really enough? I may be missing the point, but $\log$ is strictly monotonic, but $\log \max_i x_i = \max_i \log x_i$, for any $x_i$. To get an inequality, I thought we would need to use the convexity of $\max$ and Jensen's inequality. What are your thoughts on this? (b) I changed the equation before the last, since I believe this is what the question is asking about. The last equation can then stay as is was, I think. I indeed see no problems with it reducing to the unconditional mean when all $X_i$ are i.i.d. $\endgroup$
    – MLS
    Commented Sep 6, 2012 at 14:56
  • $\begingroup$ Hi, MLS. For (a), note that $Y_i \leq \max_j Y_j$ for each $i$, so clearly from monotonicity of expectation $\max_i \mathbb E Y_i \leq \mathbb E \max_j Y_j$; this works if we replace $\max$ with $\sup$ of an infinite set, as well, without modification. For (b), I agree that your last equation now (after your edit) follows from the penultimate one, but I don't think that's the quantity of interest. (Relating your notation back to the question of the OP, $F_i$ is a random distribution function, not a fixed one, so I think $\mathbb E X_i$ is really a random variable, in spite of the notation.) $\endgroup$
    – cardinal
    Commented Sep 6, 2012 at 16:50
  • 1
    $\begingroup$ If you are doing this for some concrete data set, you should think about bootstrapping the bias. $\endgroup$
    – kjetil b halvorsen ♦
    Commented Dec 5, 2012 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.