Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Having two scheduling strategies, I'd like to test which one performs better. The input data (several problem test cases) for the strategies are randomly generated. The strategies are used to compute an optimal feasible schedule. During the scheduling, several things are measured: scheduling time, number of backtracks performed, number of nodes in the search tree, and other criteria. I'd like to compare the strategies at each of the criteria.

I can't determine any distribution for the measured data. Moreover, the data might strongly differ for each test case. For example, the scheduling times might be:

| test case  | strategy #1 | strategy #2 |
|------------|-------------|-------------|
| #1         |         300 |         500 |
| #2         |        1200 |        3300 |
| #3         |         150 |         140 |
| #4         |        2340 |        6872 |
| #5         |        4354 |        9335 |
| #6         |         972 |         869 |

Is there a test statistic I can use to perform a hypothesis test such as: "strategy #1 runs faster than strategy #2"? What is the best way to measure which of the two strategies performs better at a criterion?

share|improve this question

2 Answers 2

If you can't select a distribution for the data, you can assume the worse case and take a minimax approach: http://en.wikipedia.org/wiki/Minimax_estimator

If you can study the data to see if you can apply a parametric distribution, you can use it as a prior to minimize the Bayes risk: http://en.wikipedia.org/wiki/Bayes_estimator

share|improve this answer

Since you don't know anything about the distribution the test cases are (presumably) generated from, all you really have to go on is which algorithm wins in each test case. Ignore any test cases (hopefully there won't be many) where the algorithms are tied. Let $N$ be the number of test cases where there is a winner, and $X$ the number of these where algorithm A wins. Given $N = n$, $X$ should be binomial with parameters $n$ and $p$, $p$ being the (unknown) probability of algorithm A winning a test case. If your null hypothesis is that A is no better than B, you can reject the null hypothesis at level $\alpha$ if $X \ge x(N)$ where the binomial distribution with parameters $N$ and $p=1/2$ would make $P(X \ge x(N)) < \alpha$. For large $n$ you could use the normal approximation to the binomial.

share|improve this answer

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.