Vi una conferencia del MIT sobre Skip List. En general, entiendo el material, pero una cosa. ¿Qué es «con alta probabilidad»? Realmente no lo entiendo en absoluto. He visto las notas de la conferencia , pero aún así no lo entiendo.
Simplemente dijo, «El evento $ E $ ocurre con alta probabilidad (whp) si, para cualquier $ \ alpha \ geq1 $, hay una elección apropiada de constantes para las cuales $ E $ ocurre con una probabilidad de al menos $ 1 – O (1 / n ^ \ alpha) $ «.
Algo de algorítmist.com tampoco ayudó.
¿Qué es $ \ alpha $ y ¿cuál es $ 1 – O (1 / n ^ \ alpha) $? No entender esto me confunde el análisis de por qué «Con alta probabilidad, cada búsqueda en una lista de omisión de $ n $ -element cuesta $ O (\ lg n) $».
Comentarios
- Tenga en cuenta que los algoritmos aleatorios y probabilísticos no son lo mismo .
Respuesta
Un evento ocurre con alta probabilidad con respecto a un parámetro $ n $ si ocurre con probabilidad $ p_n $ y $ \ lim_ {n \ to \ infty} p_n = 1 $. Por lo general, el parámetro $ n $ está claro en el contexto. En este caso, por ejemplo, probablemente sea el número de elementos en la lista.
La definición de «con alta probabilidad» en las notas de la clase es aún más específica, especificando qué tan rápido debe converger $ p_n $ a $ 1 $: un evento ocurre con alta probabilidad si ocurre con probabilidad $ p_n \ geq C / n ^ \ alpha $ para algunos $ C, \ alpha > 0 $. Por ejemplo, si elige un número aleatorio de $ \ {0, \ ldots, n \} $, entonces es distinto de cero con alta probabilidad, ya que la probabilidad de que sea distinto de cero es $ 1-1 / (n + 1) \ geq 1-1 / n $ (en este caso $ C = \ alpha = 1 $).
Comentarios
- El criterio de límite es también llamado " casi seguramente ". He visto " alta probabilidad " que se usa principalmente cuando se hace referencia a probabilidades que se acercan a uno con tasa exponencial.
- Cuando yo ver " whp " normalmente es sinónimo de " casi con seguridad ", y cuando lo uso (sin definirlo) este es siempre el significado al que me refiero. Pero, de manera más general, " whp " podría significar acercarse a 1, acercarse a 1 polinomialmente rápido o acercarse a 1 exponencialmente rápido. Si lo usa en cualquiera de los últimos sentidos, asegúrese de definirlo explícitamente.
- Realmente, ' llamaría $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " con alta probabilidad "? 😉 Pero sí: para estar seguro, defina lo que quiere decir en su contexto en cualquier caso.
- ¿Qué es una referencia estándar (por ejemplo, libros de texto) que define a WHP formalmente? Intenté escribir un artículo sobre WHP en wikipedia en.wikipedia.org/wiki/With_high_probability pero se sugirió eliminarlo porque no hay fuentes, así que estoy buscando fuentes ..
- Puede comprobar la complejidad estándar y los libros de texto de algoritmos. Pero incluso si encuentra una referencia, ese ' es solo el uso del término en ese libro de texto en particular '. Probablemente sea ' mejor definirlo explícitamente como una definición común sin ninguna " prueba ".