1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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