(Von Neumann deu um algoritmo que simula uma moeda justa, tendo acesso a moedas tendenciosas idênticas. O algoritmo potencialmente requer um número infinito de moedas (embora, na expectativa, finitas sejam suficientes). Essa questão diz respeito ao caso em que o número permitido de lançamentos limitado.)
Suponha que tenhamos moedas idênticas com viés δ = P [ H e a d ] - P [ T a i l ] . O objetivo é simular um único sorteio, minimizando o viés.
A simulação deve ser eficiente no seguinte sentido: Um algoritmo em execução no tempo polinomial analisa bits aleatórios e gera um único bit. O viés do algoritmo é definido como B i a s ( A ) = | E [ A = 0 ] - E [ A = 1 ] | onde a expectativa é assumida sobre a distribuição definida por n iid bits x 1 , … , x n de modo que P r o b [ .
Qual algoritmo em execução no tempo polinomial tem o menor viés B i a s ( A ) ?
Esta pergunta me parece muito natural e é muito provável que já tenha sido considerada antes.
O que se sabe sobre esse problema? Existe algo conhecido quando uma classe mais fraca (em , etc.) de algoritmos é considerada?
Você não diz se o viés é conhecido ou desconhecido. A mágica do algoritmo de von Neumann é que ele funciona nos dois casos.
Suponha que seja conhecido. A melhor resposta depende então criticamente das características teóricas dos números do viés. Vamos considerar p = 2/3. Jogue a moeda duas vezes e mapeie HH para 0 e TH e HT para 1, repetindo o experimento se o resultado for TT. Então 0 e 1 são igualmente prováveis e a chance de repetição é de apenas 1/9 em vez de 5/9 com o algoritmo de von Neumann. Ou, para colocá-lo nos seus termos, você apenas altera um dos resultados em 1/9 se o seu limite de iteração for 2.
Tudo isso está intimamente relacionado à teoria da informação e à teoria da codificação. Quando p é uma fração com um numerador e denominador mais complicado, o melhor algoritmo exigirá um comprimento de bloco maior que 2. Você pode usar um argumento de existência no estilo de Shannon para mostrar que, para um determinado viés, existe um procedimento o mais otimizado possível. você deseja, mas o comprimento do bloco pode ficar muito grande.
Peres, em seu artigo, Iterando o procedimento de extração de bits aleatórios de Von Neumann prova que uma versão do algoritmo de von Neumann pode abordar arbitrariamente bem o limite de Shannon. Muito do trabalho nesta área parece ter sido feito por teóricos e estatísticos da informação, então não consigo pensar em nenhum artigo com uma inclinação teórica da complexidade que lhe desse uma resposta direta à sua pergunta.
Há um problema divertido que pergunta o oposto: se você tem uma fonte de bits justos, como gera com eficiência uma distribuição uniforme em um conjunto que não é de dois em dois? A versão limitada ao problema da iteração, semelhante à sua pergunta, pede para maximizar a entropia (ou seja, tornar a distribuição o mais uniforme possível) com n arremessos de uma moeda justa.
fonte
Prefiro pensar na questão da seguinte forma generalizada: temos uma árvore binária completa de hight n, em que cada nó é atribuído com um número e a soma dos números é 1. Podemos dividir as folhas em dois conjuntos com a soma de números eles estão perto?
Em geral, se tivermos recursos computacionais suficientes (por exemplo,PSp a c e em número de bits aleatórios), podemos particionar os nós da melhor maneira possível.
EDIT "Este é basicamente o problema de codificação de Shannon." (Agradecimentos a Per Vognsen.) FIM de EDIT
Por outro lado, se tivermos permissão para usar apenasA C0 0 , então não é difícil mostrar que não podemos alcançar muito por causa da troca de lema. O circuito será aproximado exponencialmente bem por uma CNF e não é difícil mostrar que uma CNF não pode calcular uma resposta com um bom viés.
(Esta resposta pode conter erros, não verifiquei os detalhes.)
fonte
Você também pode obter muitos bits aleatórios de moedas tendenciosas. Consulte o artigo Gabizon, Algoritmos de des randomização em Distribuições de produtos (http://sites.google.com/site/arielgabizon1/)
fonte
Pergunta relacionada, site diferente: branqueando uma sequência de bits aleatória
fonte
Se você deseja que um número par de lançamentos de moedas seja imparcial com uma moeda tendenciosa, a maneira mais fácil de remover o viés é reverter o resultado de todos os outros lançamentos.
fonte