Mejora de la solución de la moneda injusta de Von Neumann

Question

Si un tramposo ha alterado una moneda para preferir una cara sobre otra (una moneda sesgada), la moneda puede seguir utilizándose para obtener resultados justos cambiando el juego ligeramente. John von Neumann dio el siguiente procedimiento:

Lanza la moneda dos veces. Si los resultados coinciden, vuelve a empezar, olvidando ambos resultados. Si los resultados difieren, utiliza el primer resultado, olvidando el segundo.

¿Hay formas de hacer esto (podemos modificar este procedimiento) para reducir el número de lanzamientos esperados necesarios (para una realización de cara o cruz)?

Answer 1

Creo que depende de conocer el sesgo exacto de la moneda. En un ejemplo sencillo, si se sabe que la moneda sale cara exactamente un tercio de las veces (a largo plazo), entonces se puede lanzar la moneda dos veces, llamarla cara si sale cara una vez, cruz si sale cruz dos veces, repetir si sale cara dos veces. Se obtiene una decisión 8 de cada 9 veces, lo que lleva a un número menor de lanzamientos esperados que para la solución de von Neumann.

EDIT: Hay una muy buena discusión del problema, especialmente el caso en el que no se conoce el sesgo de la moneda, en http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf [enlace actualizado el 19/07/12]

MÁS EDIT: Hay bastante literatura sobre este problema. Aquí hay una muestra de lo que hay:

MR0723740 (85f:60020) Stout, Quentin F.; Warren, Bette; Algoritmos de árbol para el lanzamiento insesgado de monedas con una moneda sesgada, Ann. Probab. 12 (1984), no. 1, 212-222.

MR1763468 (2001f:65009) Juels, Ari; Jakobsson, Markus; Shriver, Elizabeth; Hillyer, Bruce K.; Cómo convertir dados cargados en monedas justas, IEEE Trans. Inform. Theory 46 (2000), no. 3, 911-921. 65C10 (94A60)

MR1763481 (2001a:65006) Ryabko, Boris Ya.; Matchikina, Elena; Construcción rápida y eficiente de una secuencia aleatoria insesgada, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1090-1093. 65C10 (65C05)

MR1763482 (2001d:68177) Näslund, Mats; Russell, Alexander; Extracción de bits óptimamente insesgados de una fuente sesgada, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1093-1103. 68Q99

MR2245123 (2007d:94019) Cicalese, Ferdinando; Gargano, Luisa; Vaccaro, Ugo; Una nota sobre la aproximación de distribuciones uniformes de códigos de longitud variable a fija, IEEE Trans. Inform. Theory 52 (2006), no. 8, 3772-3777. 94A29 (94A45)

MR2300366 (2008b:65010) Pae, Sung-il; Loui, Michael C.; Funciones de aleatorización: simulación de una distribución de probabilidad discreta utilizando una fuente de distribución desconocida, IEEE Trans. Inform. Theory 52 (2006), no. 11, 4965-4976. 65C10 (68W20)

Answer 2

Sí.

Si la moneda tiene un sesgo $0<p<1$ entonces la información que se obtiene al lanzar la moneda es

$$ \operatorname{E}(p):=-p\log_2(p) - (1-p)\log_2(1-p). $$

Por cada lanzamiento de moneda como entrada se recibe $\operatorname{E}(p)$ la entropía, pero sólo devuelven en promedio $p(1-p)$ entropía en la salida por lo que debe estar perdiendo algo.