Probabilidad de encontrar la mediana con espacio finito

Question

Este es un spin-off de este StackOverflow question.

Supongamos que tiene un número fijo k de ubicaciones de almacenamiento y espacio para dos contadores. Recibirá n elementos en orden aleatorio (todas las permutaciones de n elementos son igualmente probables). Después de recibir cada elemento, puede almacenarlo en una de las ubicaciones k (descartando uno de los valores almacenados previamente) o desechar el artículo. También puede aumentar o disminuir cualquiera de los contadores. No se puede recuperar ningún artículo descartado.

Las preguntas son

1. ¿Cuál es la estrategia que maximiza su probabilidad de encontrar la mediana exacta?
2. ¿Cuál es esa probabilidad?

Obviamente, si k> n/2, podemos encontrar la mediana. En general, parece que la misma estrategia de tratar de mantener el número de valores altos desechados igual al número de valores bajos descartados debería ser óptima, pero no estoy seguro de cómo demostrarlo, ni de cómo averiguar la probabilidad de que encuentre la mediana

También de interés es el caso en el que no sabemos n pero conocemos la distribución de probabilidad de n.

Edit: Supongamos por ahora que los valores son distintos (sin duplicados). Sin embargo, si puede resolver el caso no distinto también, entonces eso sería impresionante.

Answer 1

Munro y Paterson estudiaron esencialmente este problema en su documento Selection and sorting with limited storage. Muestran que su algoritmo requiere k = Ω (√n) para tener éxito con probabilidad constante y que esto es asintóticamente óptimo al apelar a los resultados básicos sobre caminatas aleatorias unidimensionales.

Si quería demostrar optimalidad absoluta, lo primero que me gustaría probar sería considerar un algoritmo arbitrario A y luego par su ejecución con un algoritmo A' que, la primera vez que una se desvía de su algoritmo, hace su algoritmo lo haría en su lugar y luego intenta seguir a A tan de cerca como le sea posible.

Answer 2

Una conjetura descabellada: descartar el elemento que está más alejado de significa de los valores almacenados actualmente.

La comparación con la mediana actual no funciona si la distribución de valores es multimodal y primero obtenemos valores de un modo no dominante.