Cómo probar cuál de las dos estrategias de programación funciona mejor a partir de datos con distribución desconocida

Question

Teniendo dos estrategias de programación, me gustaría probar cuál funciona mejor. Los datos de entrada (varios casos de prueba de problemas) para las estrategias se generan aleatoriamente. Las estrategias se utilizan para calcular una programación óptima factible. Durante la programación, se miden varias cosas: tiempo de programación, número de retrocesos realizados, número de nodos en el árbol de búsqueda y otros criterios. Me gustaría comparar las estrategias en cada uno de los criterios.

No puedo determinar ninguna distribución para los datos medidos. Además, los datos pueden ser muy diferentes en cada caso de prueba. Por ejemplo, los tiempos de programación podrían ser:

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

¿Existe algún estadístico de prueba que pueda utilizar para realizar una prueba de hipótesis como: "la estrategia nº 1 corre más que la estrategia nº 2"? ¿Cuál es la mejor manera de medir cuál de las dos estrategias funciona mejor según un criterio?

Answer 1

Si no puede seleccionar una distribución para los datos, puede asumir el peor de los casos y adoptar un enfoque minimax: http://en.wikipedia.org/wiki/Minimax_estimator

Si puede estudiar los datos para ver si puede aplicar una distribución paramétrica, puede utilizarla como prior para minimizar el riesgo de Bayes: http://en.wikipedia.org/wiki/Bayes_estimator

Answer 2

Como no sabes nada de la distribución a partir de la cual se generan (presumiblemente) los casos de prueba, lo único que tienes para decidir es qué algoritmo gana en cada caso de prueba. Ignora los casos de prueba (esperemos que no haya muchos) en los que los algoritmos estén empatados. Deje que $N$ es el número de casos de prueba en los que hay un ganador, y $X$ el número de éstas en las que gana el algoritmo A. Dado $N = n$ , $X$ debe ser binomial con parámetros $n$ et $p$ , $p$ que es la probabilidad (desconocida) de que el algoritmo A gane un caso de prueba. Si su hipótesis nula es que A no es mejor que B, puede rechazar la hipótesis nula al nivel $\alpha$ si $X \ge x(N)$ donde la distribución binomial con parámetros $N$ et $p=1/2$ haría $P(X \ge x(N)) < \alpha$ . Para grandes $n$ podrías usar la aproximación normal a la binomial.