Algoritmos randomizados: alta probabilidade vs. expectativa
-
29-09-2020 - |
Pergunta
Espero que esta questão não seja muito geral, mas eu estava me perguntando qual é o relacionamento entre algoritmos randomizados que funcionam bem com alta probabilidade e aqueles que executam bem na expectativa. Minha pergunta é motivada pela definição de uma classe randomizada
- Você pode sempre transformar um algoritmo que atinge uma $ \ alfa $ -adequação na expectativa para aquela que alcança isso com alta probabilidade e vice-versa? (Ostensivamente ao relacionar o algoritmo múltiplo [um número polinomial] dos tempos.)
- Se não, é mais difícil do que o outro para obter? (Eu acho que se você corrigir $ \ alfa $ , um algoritmo de alta probabilidade sempre seria mais difícil de encontrar / menos provável que existisse. Ou talvez você sempre possa encontrar um, mas a proporção de aproximação ficará pior.)
Obrigado pela ajuda!
Solução
Se você tem um algoritmo que é uma $ \ alfa $ -adequação na expectativa, então você pode construir um algoritmo que é uma matemática $ (1+ \ epsilon) \ Alfa $ -adequação com alta probabilidade, para qualquer $ \ epsilon> 0 $ . Em particular, pela desigualdade de Markov, se você executar o algoritmo, então com probabilidade pelo menos $ 1-1 / (1+ \ epsilon) $ ele irá produzir uma $ (1+ \ epsilon) \ Alfa $ -adequação. Então, se você executar o algoritmo sobre $ (c \ log n) / \ epsilon $ vezes e manter a melhor saída entre todos esses ensaios, com probabilidade sobre $ 1-1 / N ^ C $ Você encontrará uma $ (1+ \ epsilon) \ Alfa $ -Aproximação .
Se você tiver um algoritmo que é uma $ \ alfa $ -adequação com alta probabilidade, não há garantias sobre a expectativa. É possível que com probabilidade muito pequena (probabilidade $ 1 / n ^ c $ ), ele produz uma solução extremamente ruim (uma com fator de aproximação exponencialmente grande), e em todos os outros Casos Ele produz uma $ \ alfa $ -adequação. Neste caso, o valor esperado do fator de aproximação será muito grande, mesmo que tenha uma probabilidade muito pequena para produzir uma solução tão ruim.