La operación de votación mayoritaria aparece con bastante frecuencia en la tolerancia a fallas (y sin duda en otros lugares), donde la función genera un bit igual al valor que aparece con mayor frecuencia en el valor de los bits de entrada. Para simplificar, supongamos que cada vez que la entrada contiene un número igual de bits en el estado 0 y el estado 1, genera 0.
Esto se puede generalizar a dits donde hay más de 2 posibilidades para cada entrada devolviendo el valor que ocurre con mayor frecuencia en la entrada y, en el caso de un empate, devolviendo el valor más frecuente que viene primero lexicográficamente. Llamemos a esta función "voto de pluralidad".
Estoy interesado en la salida de dicha función cuando cada entrada tiene una distribución de probabilidad fija (y la distribución es la misma para cada dit en la entrada). Específicamente me importa la siguiente pregunta.
Dado un conjunto , si el conjunto se muestrea aleatoriamente independientemente veces, con probabilidad de elegir el elemento de cada vez, para una elección fija de ¿cuál es la probabilidad de que la pluralidad vote de estas salidas ?
Ahora, es sencillo calcular la respuesta exacta a la pregunta anterior como una suma sobre distribuciones multinomiales. Sin embargo, para mis propósitos, esto es menos que ideal, y una aproximación cerrada sería mejor. Entonces mi pregunta es:
¿Qué aproximación de forma cerrada a la probabilidad anterior tiene el límite más estrecho en la distancia máxima desde el valor exacto?
fuente
Respuestas:
Si para todo i ≠ v , entoncespagv> pyo i ≠ v
donde es la distribución binomial y T es un umbral arbitrario. Al conectar T = N ( p v + max i ≠ v p v ) / 2 y usar los límites de Chernoff, se puede limitar esta probabilidad como e - Ω ( N ) .B ( n , p ) T T= N( pv+ maxi ≠ vpagv) / 2 mi- Ω ( N)
Por supuesto, si no es máximo, entonces obtienes la imagen opuesta. Con una probabilidad abrumadora v no es el resultado.pagv v
fuente