¿Cuál es la mejor manera de obtener un lanzamiento de moneda casi justo de monedas sesgadas idénticas?

21

(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 n monedas idénticas con sesgo δ=P[Head]P[Tail] . 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 n bits aleatorios y genera un solo bit. El sesgo del algoritmo se define como Bias(A)=|E[A=0]E[A=1]|donde la expectativa se toma sobre la distribución definida por n iid bits x1,,xn tal que Prob[xi=1]Prob[xi=0]=δ .

¿Qué algoritmo A ejecuta en tiempo polinómico tiene el menor sesgo Bias(A) ?

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 AC0 , etc.) de algoritmos?

Hrushikesh
fuente

Respuestas:

15

Lanzar n monedas sesgadas y tomar la paridad de cabezas se acerca exponencialmente a 12 .

[Para una prueba, considere una variable aleatoria que es -1 cuando sale cara y 1 cuando sale cruz, entonces la probabilidad de que haya un número impar de caras es solo mi[12+12yoXyo]=12+12δnorte]

Quizás esto también sea óptimo por la siguiente razón. Sea cualquier función de composición de estos bits. A continuación, el Bias ( f ) = Σ S f (Fy la mejor f parece ser la función de paridad (¿no es así?).Parcialidad(F)=SF^(S)δEl |SEl |F

Si está interesado en funciones de composición de menor complejidad, entonces quizás un artículo de Ryan O'Donnell sobre 'Amplificación de dureza dentro de NP' sería muy relevante. Allí utiliza funciones de composición monótona para amplificaciones de dureza y las funciones que funcionan se caracterizan por su sensibilidad al ruido.

Ramprasad
fuente
¿Podría explicar amablemente por qué la paridad debería ser la mejor función? (Además, no es que importe mucho asintóticamente, pero ¿no debería ser eso en la expansión de Fourier ya que E [ x i ] = δ ?). Gracias por el puntero al papel! delta|S|E[xi]=δ
Hrushikesh
Oh lo siento, tienes razón. La expresión era incorrecta y ahora la he corregido. Yo no tengo una prueba de la optimalidad (tal vez no es óptimo), pero la razón por lo que supuse era que sería cierto si la expresión era lugar ya que esta es una combinación convexa. Sf^(S)2δ|S|
Ramprasad
Quizás esto podría arrojar algo de luz. Por Cauchy-Schwarz, sabemos que . Una forma de optimización sería minimizar el límite superior tanto como sea posible y eso sucede cuando la funciónfes la función de paridad y, en ese caso, la cantidad que nos interesa también coincide con el límite superior. Sin embargo, podría darse el caso de que el vector de coeficientes de Fourier sea completamente ortogonal alvectorδ,en cuyo caso el LHS es simplemente cero. ¿Existen valores especiales deδpara los cuales conocemos tales ejemplos? Sf^(S)S:F^(S)0 0δ2El |SEl |Fδδ
Ramprasad
En realidad, si uno tomara una función monótona no trivial , entonces en δ = - 1 la expectativa de que la probabilidad de f ( x 1 , , x n ) = 1 sea ​​0 y en δ = 1 sea 1 . Por lo tanto, para algunos δ intermedios , debe tomar el valor 1Fδ=-1F(X1,,Xnorte)=1δ=11δ . Por lo tanto, no es justo esperar que para cadaδ, la función de paridad sea óptima. 12δ
Ramprasad
¿Puedes explicar el último comentario con más detalle? Sin tener en cuenta las cuestiones de complejidad de f, no es su conclusión cierto sólo si para un delta 1mi[F]=1/ /2 ya que la paridad tiene un sesgo deδaδn? δ121/ /norteδδnorte
Hrushikesh
12

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.

Por Vognsen
fuente
1
Se me ocurrió que la optimización del tiempo de ejecución no está sujeta a sesgos (lo que hace el trabajo) es doble para Lagrange con respecto a la optimización del sesgo sujeto al tiempo de ejecución. Entonces, ¡creo que ese documento realmente responde a tu pregunta!
Según Vognsen el
5

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 - ipagsq=1-pagspagsyoqnorte-yo .

yo(norteyo)pagsunaryoty(X)pagsyoqnorte-yo=yo(norteyo)(-pags)yoqnorte-yo=(q-pags)norte

PAGSSpagsunadomi

EDITAR "Este es básicamente el problema de codificación de Shannon". (Gracias a Per Vognsen.) FIN de EDITAR

UNAdo0 0

(Esta respuesta puede contener errores, no he verificado los detalles).

Kaveh
fuente
2
"¿Podemos dividir las hojas en dos conjuntos de las sumas de números que están cerca?" Este es básicamente el problema de codificación de Shannon. El algoritmo de Shannon-Fano es de arriba hacia abajo y comienza con un conjunto de elementos ponderados por probabilidad y pide una bipartición lo más uniforme posible. La aplicación recursiva da un código integral sin prefijo. El algoritmo de Huffman es de abajo hacia arriba: comienza con árboles singleton y combina repetidamente pares con la probabilidad más cercana. Si conoce la codificación aritmética, esto también sugiere acertadamente que es mejor generar múltiples bits justos a la vez en lugar de uno a la vez.
Per Vognsen
4

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
1

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.

Dean J
fuente
1
Por supuesto, esto no dará como resultado una secuencia aleatoria uniforme. Imagine el caso limitante a medida que el sesgo de la moneda llega a 1: solo obtiene una secuencia de bits alterna determinista.
Aaron Roth
Cualquier estrategia que reasigne biológicamente los resultados conservará la entropía, por lo que no puede cambiar la distribución de entropía no máxima (sesgada) a entropía máxima (imparcial).
Según Vognsen el