Assisti à palestra do MIT sobre Lista de Pulos. No geral, eu entendo o material, mas uma coisa. O que é “com alta probabilidade”? Eu realmente não entendi. Eu vi as notas de aula , mas ainda não entendi.
Eles simplesmente disse, “O evento $ E $ ocorre com alta probabilidade (whp) se, para qualquer $ \ alpha \ geq1 $, houver uma escolha apropriada de constantes para as quais $ E $ ocorre com probabilidade de pelo menos $ 1 – O (1 / n ^ \ alpha) $ “.
Algo de algorithmist.com também não ajudou.
O que é $ \ alpha $ e o que é $ 1 – O (1 / n ^ \ alpha) $? Não entender isso me deixa confuso sobre a análise do porquê “Com alta probabilidade, cada pesquisa em uma lista de omissão de $ n $ -elemento custa $ O (\ lg n) $”.
Comentários
- Observe que algoritmos aleatórios e probabilísticos não são a mesma coisa .
Resposta
Um evento acontece com alta probabilidade em relação a um parâmetro $ n $ se acontecer com probabilidade $ p_n $ e $ \ lim_ {n \ to \ infty} p_n = 1 $. Normalmente, o parâmetro $ n $ é claro no contexto. Neste caso, por exemplo, é provavelmente o número de elementos na lista.
A definição de “com alta probabilidade” nas notas de aula é ainda mais específica, especificando a rapidez com que $ p_n $ deve convergir a $ 1 $: um evento acontece com alta probabilidade se acontecer com probabilidade $ p_n \ geq C / n ^ \ alpha $ para algum $ C, \ alpha > 0 $. Por exemplo, se você escolher um número aleatório de $ \ {0, \ ldots, n \} $, então ele é diferente de zero com alta probabilidade, pois a probabilidade de ser diferente de zero é $ 1-1 / (n + 1) \ geq 1-1 / n $ (então, neste caso $ C = \ alpha = 1 $).
Comentários
- O critério de limite é também chamado de " quase com certeza ". Eu vi " alta probabilidade " usada principalmente quando se refere a probabilidades que se aproximam de uma com taxa exponencial.
- Quando eu veja " whp " geralmente é sinônimo de " quase certamente ", e quando eu o uso (sem defini-lo) é sempre o significado a que me refiro. Porém, de maneira mais geral, " whp " pode significar se aproximando de 1, aproximando-se de 1 polinomialmente rápido ou se aproximando de 1 exponencialmente rápido. Se você usar este último sentido, certifique-se de defini-lo explicitamente.
- Na verdade, você ' d chama $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " com alta probabilidade "? 😉 Mas sim: para estar seguro, defina o que você quer dizer no seu contexto em qualquer caso.
- O que é uma referência padrão (por exemplo, livros didáticos) que define WHP formalmente? Tentei escrever um artigo sobre WHP na wikipedia en.wikipedia.org/wiki/With_high_probability , mas foi sugerido para exclusão porque não há fontes, então estou procurando fontes ..
- Você pode verificar a complexidade padrão e os livros didáticos de algoritmos. Mas mesmo se você encontrar uma referência, isso ' é apenas aquele livro-texto específico ' é o uso do termo. É ' provavelmente melhor apenas defini-lo explicitamente como uma definição comum sem qualquer " prova ".