Algoritmos randomizados: alta probabilidade vs. expectativa

Question

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 $ \ Alfa $ - Algoritmo de Aproximação Dado Aqui , nomeadamente que é um algoritmo de tempo polinomial que produz uma solução dentro de $ \ alfa $ de optar na expectativa ou com alta probabilidade. Eu também descobri que as primeiras páginas de Esta fonte fornece alguma boa visão sobre as abordagens de alta probabilidade vs. Expectativa, mas ainda tenho dúvidas.

• 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!

Answer 1

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.