El truco de la mediana es un enfoque genérico que aumenta las posibilidades de que un algoritmo probabilístico tenga éxito. [1] Aparentemente utilizado por primera vez en 1986 [2] por Jerrum et al. [3] para algoritmos de conteo aproximado , la técnica se aplicó más tarde a una amplia selección de problemas de clasificación y regresión . [2]
La idea del truco de la mediana es muy simple: ejecutar el algoritmo aleatorio con salida numérica varias veces y usar la mediana de los resultados obtenidos como respuesta final. Por ejemplo, para algoritmos sublineales en el tiempo, el mismo algoritmo se puede ejecutar repetidamente (o en paralelo) sobre subconjuntos aleatorios de datos de entrada y, según la desigualdad de Chernoff , la mediana de los resultados convergerá a la solución muy rápido. [4] Para los algoritmos que son sublineales en el espacio (por ejemplo, contar los elementos distintos de una secuencia), se deben usar diferentes aleatorizaciones del algoritmo (por ejemplo, con diferentes funciones hash ) para ejecuciones repetidas sobre los mismos datos. [5]