concentración de Sharp para la selección a través de la partición aleatoria?

Question

El algoritmo sencillo habitual para encontrar el elemento medio de una matriz $ A $ $ n de números es $:

• $ de la muestra n ^ {3/4} $ elementos de $ A $ con sustitución en $ B $
• Ordenar $ B $ y encontrar el rango $ | B | \ pm \ sqrt {n} $ elementos $ l $ y $ r $ de $ B $
• Compruebe que $ l $ y $ R $ están en lados opuestos del medio de $ A $ y que hay a lo sumo $ C \ sqrt {n} $ elementos en $ A $ entre $ l $ y $ r $ para alguna constante apropiada $ C> 0 $. Falla si esto no sucede.
• En caso contrario, encontrar la mediana de la clasificación de los elementos de $ A $ entre $ l $ y $ r $

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

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

También es fácil ver que éste ha lineal tiempo de ejecución esperado: decir que una "vuelta" es una secuencia de llamadas recursivas que termina cuando uno da un / 4-3 / 4 de división 1, y luego observar que la duración prevista de una ronda es como máximo 2. (en el primer sorteo de una ronda, la probabilidad de obtener una buena división es un medio y a continuación, después en realidad aumenta, como se describe el algoritmo de modo longitud ronda está dominado por una geométrico azar variable.)

Así que ahora la pregunta:

¿Es posible demostrar que las carreras de selección aleatorios en el tiempo lineal con una alta probabilidad?

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

Esto es un poco insatisfactorio, pero es en realidad la verdad?

Answer 1

It's not true that the algorithm runs in linear time with high probability. Considering only the first round, the running time is at least $\Theta(n)$ times a $G(1/2)$ random variable. Let $p(n) \longrightarrow 0$ be the allowed failure probability. Since $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$, the running time is at least $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$.

(There is some cheating involved, since the length of the first round isn't really $G(1/2)$. More careful analysis might or might not validate this answer.)

Edit: Grübel and Rosler proved that the expected number of comparisons divided by $n$ tends (in some sense) to some limit distribution, which is unbounded. See for example Grübel's paper "Hoare's selection algorithm: a Markov chain approach", which references their original paper.