A operação de votação majoritária ocorre com bastante frequência na tolerância a falhas (e sem dúvida em outros lugares), onde a função gera um bit igual ao valor sempre exibido com mais freqüência no valor dos bits de entrada. Por uma questão de simplicidade, vamos assumir que sempre que a entrada contém um número igual de bits no estado 0 e no estado 1, ela gera 0.
Isso pode ser generalizado para dits em que existem mais de 2 possibilidades para cada entrada retornando o valor que ocorre com mais freqüência na entrada e, no caso de um empate, retornando o valor mais frequente que vem primeiro lexicograficamente. Vamos chamar essa função de "voto da pluralidade".
Estou interessado na saída dessa função quando cada entrada possui uma distribuição de probabilidade fixa (e a distribuição é a mesma para cada dado na entrada). Eu me preocupo especificamente com a seguinte pergunta.
Dado um conjunto , se o conjunto for amostrado independentemente vezes, com probabilidade de escolher o elemento de cada vez, para uma escolha fixa de qual é a probabilidade de que o voto da pluralidade dessas saídas ?
Agora, é fácil calcular a resposta exata para a pergunta acima como uma soma das distribuições multinomiais. No entanto, para meus propósitos, isso é menos que o ideal e um fechamento para aproximação seria melhor. Então, minha pergunta é:
Que aproximação de forma fechada à probabilidade acima tem o limite mais estreito na distância máxima do valor exato?
fonte
Respostas:
Se para todos os i ≠ v , entãopv> pEu i ≠ v
onde é distribuição binomial e é um limite arbitrário. Conectando e usando os limites de Chernoff, pode-se limitar esta probabilidade como .B ( n , p ) T T= N( pv+ maxi ≠ vpv) / 2 e- Ω ( N)
Obviamente, se não for o máximo, você obtém a imagem oposta. Com probabilidade esmagadora, não é resultado.pv v
fonte