Probando la Aleatoriedad con Monedas Correspondiendo

En el juego de Monedas Correspondientes, Alice y Bob cada uno sostiene una moneda, y en cada tic del reloj muestran simultáneamente el lado de cara o de cruz de sus monedas. Si ambos muestran el mismo lado, Alice gana la moneda de Bob; si muestran lados diferentes, Bob gana la moneda de Alice. Para evitar darle al oponente una oportunidad de ganar, parece que ambos jugadores no tienen más opciones que jugar aleatoriamente cara y cruz con frecuencias iguales. Sin embargo, no perder en este juego es fácil, no perder una oportunidad para ganar no lo es. Aleatorizar sus propios movimientos puede ser fácil. Reconocer cuándo los movimientos del oponente no son aleatorios puede ser arbitrariamente difícil. La noción de aleatoriedad es central en la teoría de juegos, pero generalmente se da por sentada. La noción de ser más astuto no es central en la teoría de juegos, pero sí lo es en la práctica de jugar. Perseguimos la idea de que estas dos nociones pueden ser vistas útilmente como dos caras de la misma moneda. El análisis resultante sugiere que los métodos para elaborar estrategias en juegos y seguridad, y para aleatorizar en computación, pueden ser aprovechados mutuamente. Clasificación Matemática del 2010. 03D32, 91A26, 91A26, 68Q32.