You are given a sample of size $m$ from $n$ independent normally distributed random variables. Expectations and standard deviations of the random variables are unknown. Estimate, which random variable has the largest expectation.


The interesting case is when $n > 2$ and the expectations of the random variables are close to each other compared to the standard deviations divided by $\sqrt{m}$. In this case just comparing the sample means may not give the best results. For example, with 3 random variables $X_1, X_2, X_3$, with $X_i \sim N(\mu_i, \sigma_i^2)$, with $$ \mu_1 = 0, \; \mu_2, \mu_3 \in [-1, 1] $$ $$ \sigma_1 = \sqrt{m}, \; \sigma_2, \sigma_3 = 10 \sqrt{m} $$ there is only a roughly $1/4$ chance for $X_1$ to have the largest sample mean, whether any of $\mu_2, \mu_3$ are positive or not. For a good test I would expect this probability to be around $1/3$. Hence the question.



For the case of $3$ random variables, choose two of them (at random) and compare the sample means of the first half of the samples. Then compare the sample means of the second half of the samples for the winner of the first round and the third random variable. You'll have probability greater than $1/3$ of the result being correct. The random choice of the initial pair to compare is, of course, necessary for this.

Similarly, with $n$ random variables, conduct a "knockout tournament" such that at each level a different set of samples is used (so that you maintain independence of the pairwise comparisons).

  • 1
    $\begingroup$ It seems to me that this method uses less information than what's available, so I'd expect to do better with some method that uses all of it. $\endgroup$ – Michael Hardy Feb 27 '13 at 0:57
  • $\begingroup$ Well, I would probably feel more comfortable with a more deterministic algorithm, but your answer does answer my question. Thanks! $\endgroup$ – Anton Feb 27 '13 at 18:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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