Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Problem:

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.

Discussion:

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.

Thanks.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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).

share|improve this answer
    
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. –  Michael Hardy Feb 27 '13 at 0:57
    
Well, I would probably feel more comfortable with a more deterministic algorithm, but your answer does answer my question. Thanks! –  Anton Feb 27 '13 at 18:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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