How many samples to be confident?

I have an evaluation, where i'd like to compare two probability distributions. The easiest ways seems to compare the average. However, the standard deviation is quite high, so often the "worse" distribution is "better" in specific cases. So what would be an appropriate way to compare these results.

More concretely, i have heuristic optimization algorithms and a set of tests. Since they algorithms are heuristic and the tests contain noise, there is a lot of variance. The core question is, which algorithm is the best?

The usual formulas for confidence analysis assume that there is some "population", of which a certain percentage is polled. However, in my case there is no percentage, as the algorithms could be executed arbitrarily often.

-

First, you need some function to quantify "best." How could you assign a number to how well an algorithm performs? Is the outcome simply right or wrong, or is the outcome continuous with degrees of goodness? Imagine selling the results and attaching a dollar value depending on the quality.

Once you have a way to measure the utility of the outcome, you could look at the average of both algorithms. Even though you say your variance is high, you also say you could run your algorithms as often as you like, so you could generate outcomes until the averages settle down. (Assuming you're variance, though large, is finite. Not something like a Cauchy distribution.) That would tell you which algorithm has a higher average.

But maybe you're interested in a different way of comparing the two algorithms. You could ask how often one group is better than the other by making repeated pairwise comparisons. That won't tell you the average performance of either algorithm, but it will give you an idea how often one is better.

-

If I understand correctly, each of your algorithm has a certain score for each test, and the score varies between each test. Each algorithm has a distribution of scores.

If this distribution has finite variance, then the central limit theorem tells you that in the long run, the sample average $\hat{\mu}$ will be normally distributed around the true average $\mu$. Specifically, if your algorithm outputs score $s_1,s_2,\ldots,s_N$, then let $$\hat{\mu} = \frac{1}{N}\sum_{i=1}^N s_i$$ and $$\hat{\sigma} = \sqrt{\frac{\left(\frac{1}{N}\sum_{i=1}^N s_i^2\right) - \hat{\mu}^2}{N}}$$

Then $\mu \sim \mathcal{N}(\hat{\mu},\hat{\sigma})$. In practice, run algorithm $a$ and algorithm $b$ in a loop, and accumulate the sum of the $s^a_i$, of the $s^b_i$, of the $(s^a_i)^2$ and of the $(s^b_i)^2$...

Run at least 20 iterations, and stop when $\frac{(\mu_a - \mu_b)^2}{\sigma_a^2+\sigma_b^2} > 9$, you can be fairly sure that the algorithm with the highest average has a better true average.

Why 20 and 9? 20 in practice means that the student law which describes the behavior of the sample average is close to a normal law, 9 means you're looking for 3 standard deviation, a p-value of 0.135% (which roughly means that if you had ran the same algorithm, with the same performance, you would have gotten a difference as strong as this 0.135% of the time)

http://en.wikipedia.org/wiki/Analysis_of_variance

-

If you have probability distributions $p_0, p_1$, then the proper statistic is the bayes factor $p_0(\vec x)/p_1(\vec x)$ where $\vec x$ is the vector of observations. This yields the most powerful test (in the Neymann-Pearson sense) to distinguish between the two hypotheses.

-