¿Concentración aguda para la selección mediante partición aleatoria?

El algoritmo simple habitual para encontrar el elemento mediano en una matriz de números es: $A$ $n$

Muestra de elementos de con reemplazo en $n^{3/4}$ $A$ $B$
Ordene y encuentre el rango elementos y de $B$ $|B|\pm \sqrt{n}$ $l$ $r$ $B$
Verifique que y estén en lados opuestos de la mediana de y que haya a lo sumo elementos en entre y para alguna constante constante . Falla si esto no sucede. $l$ $r$ $A$ $C\sqrt{n}$ $A$ $l$ $r$ $C > 0$
De lo contrario, encuentre la mediana ordenando los elementos de entre y $A$ $l$ $r$

No es difícil ver que esto se ejecuta en tiempo lineal y que tiene éxito con alta probabilidad. (Todos los eventos negativos son grandes desviaciones de la expectativa de un binomio).

Un algoritmo alternativo para el mismo problema, que es más natural enseñar a los estudiantes que han visto una clasificación rápida, es el que se describe aquí: Selección aleatoria

También es fácil ver que este tiene un tiempo de ejecución lineal esperado: digamos que una "ronda" es una secuencia de llamadas recursivas que finaliza cuando uno da una división de 1 / 4-3 / 4, y luego observe que la longitud esperada de una ronda es como máximo 2. (En el primer sorteo de una ronda, la probabilidad de obtener una buena división es 1/2 y luego aumenta, ya que el algoritmo se describió de modo que la longitud de la ronda está dominada por una variable aleatoria geométrica).

Entonces ahora la pregunta:

¿Es posible mostrar que la selección aleatoria se ejecuta en tiempo lineal con alta probabilidad?

Tenemos rondas , y cada ronda tiene una longitud de al menos con una probabilidad máxima de , por lo que un límite de unión da que el tiempo de ejecución es con probabilidad . $O(\log n)$ $k$ $2^{-k+1}$ $O(n\log\log n)$ $1-1/O(\log n)$

Esto es un poco insatisfactorio, pero ¿es realmente la verdad?

algorithms algorithm-analysis randomized-algorithms Louis
fuente

Aclare a qué algoritmo se refieren sus preguntas.

Raphael

¿Está preguntando si aplicó su límite de unión correctamente, o si hay un límite mejor y más satisfactorio?

Joe

@ Joe El último. El punto es que las rondas son un artefacto para lograr que la longitud de la ronda esté dominada por una geometría. Luego, el análisis "olvida" si el algoritmo está adelante o atrás del que siempre obtiene una división de 1 / 4-3 / 4 en la nariz para hacer que la geometría sea independiente. Estoy preguntando si este "engaño", como Yuval lo puso a continuación, sigue siendo estricto.

Louis

Respuestas:

No es cierto que el algoritmo se ejecute en tiempo lineal con alta probabilidad. Considerando solo la primera ronda, el tiempo de ejecución es al menos veces una variable aleatoria . Sea la probabilidad de falla permitida. Como , el tiempo de ejecución es al menos . $\Theta(n)$ $G(1/2)$ $p(n) \longrightarrow 0$ $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$ $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

(Hay algunas trampas involucradas, ya que la duración de la primera ronda no es realmente . Un análisis más cuidadoso podría o no validar esta respuesta). $G(1/2)$

Editar: Grübel y Rosler demostraron que el número esperado de comparaciones divididas por tiende (en cierto sentido) a cierta distribución límite, que no tiene límites. Véase, por ejemplo, el artículo de Grübel "Algoritmo de selección de Hoare: un enfoque de cadena de Markov", que hace referencia a su artículo original. $n$

Yuval Filmus
fuente

Aquí está lo que me molesta. Como dije en mi comentario anterior, las rondas son solo una forma de analizar una versión "más lenta" del algoritmo que espera hasta que obtenga un pivote lo suficientemente bueno para continuar. Lo que está mostrando es que para cualquier fijo, la probabilidad de que la primera ronda necesite más que pivotes es . Pero, en principio, una primera ronda larga podría ser compensada por una segunda ronda vacía, en el sentido de que al final, el algoritmo "no ralentizado" alcanza al que siempre se divide 1 / 4-3 / 4 .

C > 0

$C>0$

C

$C$

> 0

$>0$

Louis

Eso no es cierto, si la primera ronda es larga, entonces todo el tiempo de ejecución es largo, ya que las rondas posteriores no pueden disminuir el tiempo de ejecución. El punto es que para cualquier , la primera ronda lleva tiempo al menos con alguna probabilidad constante .

C

$C$

C n

$Cn$

p_{C} > 0

$p_C > 0$

Yuval Filmus

Ahora estoy más feliz, ya que la longitud de la ronda no es mucho más pequeña que la geométrica utilizada para el límite superior. Supongo que esto es lo que G&R está haciendo rigerous. Buena respuesta.

Louis