Com alta probabilidade - With high probability

Em matemática , um evento que ocorre com alta probabilidade (muitas vezes abreviado para whp ou WHP ) é aquele cuja probabilidade depende de um certo número n e vai para 1 quando n vai para o infinito, ou seja, a probabilidade de o evento ocorrer pode ser tão próxima para 1 conforme desejado, tornando n grande o suficiente.

Formulários

O termo WHP é especialmente utilizado em ciência da computação , na análise de algoritmos probabilísticos . Por exemplo, considere um certo algoritmo probabilístico em um gráfico com n nós. Se a probabilidade de que o algoritmo retorne a resposta correta for , então, quando o número de nós for muito grande, o algoritmo está correto com uma probabilidade muito próxima de 1. Esse fato é expresso brevemente dizendo que o algoritmo é WHP correto.

Alguns exemplos onde este termo é usado são:

  • Teste de primalidade de Miller-Rabin : um algoritmo probabilístico para testar se um determinado número n é primo ou composto. Se n for composto, o teste detectará n como WHP composto. Há uma pequena chance de termos azar e o teste achar que n é primo. Porém, a probabilidade de erro pode ser reduzida indefinidamente executando o teste muitas vezes com diferentes randomizações.
  • Algoritmo de Freivalds : um algoritmo aleatório para verificar a multiplicação de matrizes. Ele é executado mais rápido do que os algoritmos determinísticos WHP.
  • Treap : uma árvore de pesquisa binária aleatória. Sua altura é WHP logarítmica. A árvore de fusão é uma estrutura de dados relacionada.
  • Códigos online : códigos aleatórios que permitem ao usuário recuperar a mensagem original WHP.
  • BQP : uma classe de complexidade de problemas para a qual existem algoritmos quânticos de tempo polinomial que são WHP corretos.
  • Aprendizagem provavelmente correta : Um processo de aprendizagem de máquina em que a função aprendida tem baixo erro de generalização WHP.
  • Protocolos Gossip : um protocolo de comunicação usado em sistemas distribuídos para entregar mensagens de forma confiável para todo o cluster, usando uma quantidade constante de recursos de rede em cada nó e garantindo nenhum ponto único de falha.

Veja também

Referências

  • Métivier, Y .; Robson, JM; Saheb-Djahromi, N .; Zemmari, A. (2010). "Um algoritmo MIS distribuído aleatório de complexidade de bits ideal". Computação Distribuída . 23 (5–6): 331. doi : 10.1007 / s00446-010-0121-5 .
  • "Princípios de Computação Distribuída (aula 7)" (PDF) . ETH Zurich . Retirado em 21 de fevereiro de 2015 .
Ícone de esboço

Este artigo é um esboço sobre ciência . Você pode ajudar a Wikipedia expandindo-a .