(Von Neumann dio un algoritmo que simula que una moneda justa tiene acceso a monedas sesgadas idénticas. El algoritmo potencialmente requiere un número infinito de monedas (aunque en expectativa, muchas son suficientes). Esta pregunta se refiere al caso cuando el número de lanzamientos de monedas permitidos es encerrado.)
Supongamos que tenemos monedas idénticas con sesgo . El objetivo es simular un solo lanzamiento de moneda mientras se minimiza el sesgo.
La simulación debe ser eficiente en el siguiente sentido: un algoritmo que se ejecuta en tiempo polinómico examina bits aleatorios y genera un solo bit. El sesgo del algoritmo se define como donde la expectativa se toma sobre la distribución definida por iid bits tal que .
¿Qué algoritmo ejecuta en tiempo polinómico tiene el menor sesgo ?
Esta pregunta me parece muy natural y es muy probable que se haya considerado antes.
¿Qué se sabe sobre este problema? ¿Se sabe algo cuando se considera una clase más débil (en , etc.) de algoritmos?
No dice si el sesgo es conocido o desconocido. La magia del algoritmo de von Neumann es que funciona en cualquier caso.
Supongamos que se sabe. La mejor respuesta depende entonces críticamente de las características teóricas numéricas del sesgo. Tomemos p = 2/3. Lanza la moneda dos veces y asigna HH a 0 y TH y HT a 1, repitiendo el experimento si el resultado es TT. Entonces 0 y 1 son igualmente probables y la posibilidad de una repetición es solo 1/9 en lugar de 5/9 con el algoritmo de von Neumann. O para ponerlo en sus términos, solo sesga uno de los resultados en 1/9 si su límite de iteración es 2.
Todo esto está estrechamente relacionado con la teoría de la información y la teoría de la codificación. Cuando p es una fracción con un numerador y un denominador más complicados, el mejor algoritmo requerirá una longitud de bloque más larga que 2. Puede usar un argumento de existencia al estilo de Shannon para mostrar que para un sesgo dado hay un procedimiento que es tan óptimo como desea, pero la longitud del bloque puede ser muy grande.
Peres en su artículo Iterating Von Neumann's Procedure for Extracting Random Bits demuestra que una versión del algoritmo de von Neumann puede acercarse al límite de Shannon arbitrariamente bien. Gran parte del trabajo en esta área parece haber sido realizado por teóricos de la información y estadísticos, por lo que no puedo pensar en ningún documento con una inclinación teórica de la complejidad que le dé una respuesta directa a su pregunta.
Hay un problema relacionado con la diversión que pregunta lo contrario: si tiene una fuente de bits justos, ¿cómo genera de manera eficiente una distribución uniforme en un conjunto sin potencia de dos? La versión del problema limitada por la iteración que es similar a su pregunta pide maximizar la entropía (es decir, hacer que la distribución sea lo más uniforme posible) con n lanzamientos de una moneda justa.
fuente
Prefiero pensar en la pregunta en la siguiente forma generalizada: tenemos un árbol binario completo de altura n, donde a cada nodo se le asigna un número. La suma de los números es 1. ¿Podemos dividir las hojas en dos conjuntos de las sumas de los números están cerca?
Si tenemos una moneda sesgada con el parámetro y q = 1 - p , los nodos tendrán valores p i q n - ipags q= 1 - p pagsyoqn - i .
EDITAR "Este es básicamente el problema de codificación de Shannon". (Gracias a Per Vognsen.) FIN de EDITAR
(Esta respuesta puede contener errores, no he verificado los detalles).
fuente
También puede obtener muchos bits aleatorios de monedas sesgadas, consulte los algoritmos de desrandomización en papel de Gabizon en Distribuciones de productos (http://sites.google.com/site/arielgabizon1/)
fuente
Pregunta relacionada, sitio diferente: blanquear una secuencia de bits aleatoria
fuente
Si desea que un número par de lanzamientos de monedas sea imparcial con una moneda sesgada, la forma fácil de eliminar el sesgo es revertir el resultado de cada otro lanzamiento.
fuente