Mediana de distribución con restricción de memoria.

Question

Tarea

Yo quiero aproximar la mediana de una distribución dada $D$ del que puedo tomar muestras.

Un algoritmo simple para esto, usando $n$ muestras, es:

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

Sin embargo, estoy buscando un algoritmo que requiere menos de $O(n)$ espacio.

Ideas

He analizado estos algoritmos:

• Mediana de medianas:Necesidades $O(n)$ espacio, por lo que no me funciona.
• Mediana aleatoria:Parece que esto podría generalizarse fácilmente a un algoritmo que utiliza $O(n^{3/4})$ espacio.

¿Existen otros algoritmos que utilicen menos $O(n)$ ¿Espacio que podría solucionar mi problema?En particular, estaba pensando que puede haber un algoritmo que utilice $O(m)$ espacio generando lotes de muestras de $D$ de tamaño $m$...

Detalles

• Idealmente, busco una referencia a un algoritmo que también incluya análisis (probabilidad de éxito, tiempo de ejecución esperado, etc.).
• En realidad, necesito un algoritmo para estimar $D$'s $p$-ésimo percentil para un determinado $p$, pero espero que la mayoría de los algoritmos de búsqueda de medianas puedan generalizarse a eso.
• Me gustaría lograr la misma precisión que el algoritmo simple que se muestra arriba.Una forma de lograr esto es mediante el uso de un algoritmo cuya distribución de salida sea la misma que la del algoritmo de muestra (pero tal vez el nuevo algoritmo falle en casos excepcionales).

Answer 1

Claro, definitivamente puedes lograr esto usando un poco más de tiempo de ejecución.Aquí hay un enfoque conceptualmente simple, que puede no ser óptimo, pero lo ayudará a comenzar y probablemente sea bastante bueno:

Utilice la búsqueda binaria para encontrar una mediana aproximada $m$.¿Cómo saber si es candidato? $m$ ¿Es demasiado grande o demasiado pequeño?Muestra $n'$ veces de la distribución, cuente cuántas veces las muestras son $\ge m$, y comparar ese recuento con $n'/2$.Esto se puede hacer con $O(1)$ espacio.

Entonces la pregunta clave es:¿Cómo elegimos? $n'$, para controlar la probabilidad de error?Un enfoque simple es elegir $n'$ ser suficientemente mayor que $n$ que la probabilidad de error en cada iteración de la búsqueda binaria es $t$ menor que la probabilidad de error al utilizar $n$ muestras, donde $t$ es el número de iteraciones de búsqueda binaria necesarias para lograr la precisión deseada.Luego, un sindicato garantiza que esto cumplirá con sus condiciones de precisión.

Desafortunadamente, es un poco difícil trabajar con su condición de precisión cuando no sabemos nada sobre la distribución de los datos, ya que la precisión de la mediana de la muestra puede ser arbitrariamente mala.Por ejemplo, considere una distribución que genera $0$ con probabilidad $(1-\épsilon)/2$ y $100$ con probabilidad $(1+\épsilon)/2$.Entonces la mediana de la muestra es aproximadamente igualmente probable que sea 0 o 100, mientras que la mediana de distribución es 100, por lo que el error promedio de la mediana de la muestra es de aproximadamente 50 (a menos que esté dibujando $\gg 1/\épsilon^2$ muestras).Esa es una distribución particularmente desagradable y será difícil trabajar con ella.Pero si se supone que la distribución es aproximadamente gaussiana (digamos) con desviación estándar $\sigma$, entonces el error de la mediana muestral, con $n$ muestras, es aproximadamente $1.25 \sigma/\sqrt{n}$.Por lo tanto, el algoritmo anterior se puede utilizar donde configuramos $t \aprox \lg (\sqrt{n}/1.25)$ y nos fijamos $n' \aprox n t^2$.

Ése es un enfoque simple.Probablemente puedas hacerlo mejor.Es posible que desee buscar algoritmos de transmisión para calcular la mediana, ya que abordan el problema con el que está trabajando:Dado un número ilimitado de muestras de la distribución, pero solo una cantidad limitada de espacio, ¿cuál es la mejor estimación que podemos obtener para la mediana?Por ejemplo, aquí hay un algoritmo simple:la primera capa toma repetidamente tres muestras y genera la mediana de esas tres;la segunda capa toma repetidamente tres números de la primera capa y genera la mediana de esos tres;etcétera.Después del número logarítmico de capas, se obtiene una aproximación razonable a la mediana.Existe toda una literatura sobre este tema y debería poder encontrar mucha más.