¿Es java.util.Random realmente tan aleatorio? ¿Cómo puedo generar 52! posibles secuencias (factoriales)?

He estado usando Random (java.util.Random)para barajar un mazo de 52 cartas. Hay 52! (8.0658175e + 67) posibilidades. Sin embargo, descubrí que la semilla para java.util.Randomes a long, que es mucho más pequeña en 2 ^ 64 (1.8446744e + 19).

Desde aquí, sospecho si java.util.Random es realmente tan aleatorio ; ¿es realmente capaz de generar los 52! posibilidades?

Si no, ¿cómo puedo generar de manera confiable una mejor secuencia aleatoria que pueda producir los 52! posibilidades?

Seleccionar una permutación aleatoria requiere simultáneamente más y menos aleatoriedad de lo que implica su pregunta. Dejame explicar.

La mala noticia: necesita más aleatoriedad.

La falla fundamental en su enfoque es que está tratando de elegir entre ~ 2 ²²⁶ posibilidades utilizando 64 bits de entropía (la semilla aleatoria). Para elegir de manera justa entre ~ 2 ²²⁶ posibilidades, tendrá que encontrar una manera de generar 226 bits de entropía en lugar de 64.

Hay varias formas de generar bits aleatorios: hardware dedicado , instrucciones de CPU , interfaces del sistema operativo , servicios en línea . Ya hay una suposición implícita en su pregunta de que de alguna manera puede generar 64 bits, así que solo haga lo que fuera a hacer, solo cuatro veces, y done el exceso de bits a la caridad. :)

La buena noticia: necesita menos aleatoriedad.

Una vez que tenga esos 226 bits aleatorios, el resto se puede hacer de manera determinista y, por lojava.util.Random tanto, las propiedades de pueden hacerse irrelevantes . Aquí es cómo.

¡Digamos que generamos los 52! permutaciones (tengan paciencia conmigo) y ordénelas lexicográficamente.

Para elegir una de las permutaciones, todo lo que necesitamos es un número entero aleatorio entre 0y 52!-1. Ese número entero son nuestros 226 bits de entropía. Lo usaremos como índice en nuestra lista ordenada de permutaciones. Si el índice aleatorio se distribuye de manera uniforme, no solo se garantiza que se puedan elegir todas las permutaciones, sino que se elegirán de manera equiprobable (lo cual es una garantía más sólida de lo que se plantea la pregunta).

Ahora, en realidad no necesitas generar todas esas permutaciones. Puede producir uno directamente, dada su posición elegida al azar en nuestra hipotética lista ordenada. Esto se puede hacer en tiempo O (n ² ) usando el código Lehmer ^[1] (también vea las permutaciones de numeración y el sistema de numeración factorial ). El n aquí es el tamaño de su mazo, es decir, 52.

Hay una implementación de C en esta respuesta de StackOverflow . Hay varias variables enteras allí que se desbordarían para n = 52, pero afortunadamente en Java puede usar java.math.BigInteger. El resto de los cálculos se pueden transcribir casi como están:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] No debe confundirse con Lehrer . :)

Su análisis es correcto: sembrar un generador de números pseudoaleatorio con cualquier semilla específica debe producir la misma secuencia después de una combinación aleatoria, lo que limita el número de permutaciones que puede obtener a 2 ⁶⁴ . Esta afirmación es fácil de verificar experimentalmente llamando Collection.shuffledos veces, pasando un Randomobjeto inicializado con la misma semilla y observando que las dos mezclas aleatorias son idénticas.

Una solución a esto, entonces, es usar un generador de números aleatorios que permita una semilla más grande. Java proporciona una SecureRandomclase que podría inicializarse con una byte[]matriz de tamaño prácticamente ilimitado. Luego puede pasar una instancia de SecureRandoma Collections.shufflepara completar la tarea:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

En general, un generador de números pseudoaleatorios (PRNG) no puede elegir entre todas las permutaciones de una lista de 52 elementos si su longitud de estado es inferior a 226 bits.

java.util.Randomimplementa un algoritmo con un módulo de 2 ⁴⁸ ; por lo tanto, su longitud de estado es de solo 48 bits, mucho menos que los 226 bits que mencioné. Deberá usar otro PRNG con una longitud de estado mayor, específicamente, uno con un período de 52 factorial o mayor.

Ver también "Barajar" en mi artículo sobre generadores de números aleatorios .

Esta consideración es independiente de la naturaleza del PRNG; se aplica igualmente a los PRNG criptográficos y no criptográficos (por supuesto, los PRNG no criptográficos son inapropiados siempre que se trate de seguridad de la información).

Aunque java.security.SecureRandompermite pasar semillas de longitud ilimitada, la SecureRandomimplementación podría usar un PRNG subyacente (por ejemplo, "SHA1PRNG" o "DRBG"). Y depende del período de ese PRNG (y en menor medida, la duración del estado) si es capaz de elegir entre 52 permutaciones factoriales. (Tenga en cuenta que defino "longitud de estado" como el "tamaño máximo de la semilla que un PRNG puede tomar para inicializar su estado sin acortar o comprimir esa semilla ").

Permítanme disculparme de antemano, porque esto es un poco difícil de entender ...

En primer lugar, ya sabes que java.util.Randomno es completamente aleatorio en absoluto. Genera secuencias de una manera perfectamente predecible a partir de la semilla. Tiene toda la razón en que, dado que la semilla tiene solo 64 bits de longitud, solo puede generar 2 ^ 64 secuencias diferentes. Si de alguna manera generara 64 bits aleatorios reales y los usara para seleccionar una semilla, no podría usar esa semilla para elegir aleatoriamente entre todos de los 52! posibles secuencias con igual probabilidad.

Sin embargo, este hecho no tiene ninguna consecuencia , siempre y cuando no vayas a generar más de 2 ^ 64 secuencias, siempre que no haya nada 'especial' o 'notablemente especial' sobre las secuencias 2 ^ 64 que pueda generar .

Digamos que tenía un PRNG mucho mejor que utilizaba semillas de 1000 bits. Imagine que tiene dos formas de inicializarlo: una forma lo inicializaría utilizando toda la semilla, y una forma la reduciría a 64 bits antes de inicializarla.

Si no sabía qué inicializador era cuál, ¿podría escribir algún tipo de prueba para distinguirlos? A menos que haya tenido la (des) suerte de terminar inicializando al malo con el mismo 64 bits dos veces, la respuesta es no. No podría distinguir entre los dos inicializadores sin un conocimiento detallado de alguna debilidad en la implementación específica de PRNG.

Alternativamente, imagine que el Random clase tenía una matriz de 2 ^ 64 secuencias que se seleccionaron completamente y al azar en algún momento en el pasado distante, y que la semilla era solo un índice en esta matriz.

Entonces, el hecho de que Randomuse solo 64 bits para su semilla no es necesariamente un problema estadístico, siempre que no haya una posibilidad significativa de que use la misma semilla dos veces.

Por supuesto, para propósitos criptográficos , una semilla de 64 bits simplemente no es suficiente, porque hacer que un sistema use la misma semilla dos veces es computacionalmente factible.

EDITAR:

Debo agregar que, a pesar de que todo lo anterior es correcto, la implementación real java.util.Randomno es asombrosa. Si está escribiendo un juego de cartas, tal vez use la MessageDigestAPI para generar el hash SHA-256 "MyGameName"+System.currentTimeMillis()y use esos bits para barajar el mazo. Según el argumento anterior, siempre y cuando sus usuarios no estén jugando realmente, no tiene que preocuparse porque eso currentTimeMillisregrese mucho tiempo. Si los usuarios están realmente el juego, a continuación, utilizar SecureRandomsin semilla.

Voy a tomar un poco de una táctica diferente en esto. Está en lo cierto: ¡su PRNG no podrá alcanzar los 52! posibilidades

La pregunta es: ¿cuál es la escala de su juego de cartas?

Si estás haciendo un juego simple al estilo klondike? ¡Entonces definitivamente no necesitas los 52! posibilidades En cambio, míralo así: un jugador tendrá 18 quintillones de juegos distintos. Incluso teniendo en cuenta el "Problema del cumpleaños", tendrían que jugar miles de millones de manos antes de encontrarse con el primer juego duplicado.

Si estás haciendo una simulación monte-carlo? Entonces probablemente estés bien. Es posible que tenga que lidiar con artefactos debido a la 'P' en PRNG, pero probablemente no se encontrará con problemas simplemente debido a un espacio de semilla bajo (nuevamente, está viendo quintillones de posibilidades únicas). Por otro lado, si está trabajando con un gran recuento de iteraciones, entonces, su bajo espacio inicial puede ser un factor decisivo.

Si estás haciendo un juego de cartas multijugador, especialmente si hay dinero en juego? Luego, tendrás que buscar en Google cómo los sitios de póker en línea manejaron el mismo problema que estás preguntando. Porque si bien el problema de poco espacio inicial no es perceptible para el jugador promedio, es explotable si vale la pena invertir tiempo. (Todos los sitios de póker pasaron por una fase en la que sus PRNG fueron 'pirateados', dejando que alguien vea las cartas ocultas de todos los demás jugadores, simplemente deduciendo la semilla de las cartas expuestas). Si esta es la situación en la que se encuentra, no 't simplemente encontrar un mejor PRNG - que necesita para tratarlo tan seriamente como un problema Crypto.

Solución corta que es esencialmente la misma de dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

No necesita preocuparse por el estado interno. Larga explicación de por qué:

Cuando creas un SecureRandom instancia de esta manera, accede a un generador de números aleatorios verdaderos específicos del sistema operativo. Este es un grupo de entropía donde se accede a valores que contienen bits aleatorios (por ejemplo, para un temporizador de nanosegundos, la precisión de nanosegundos es esencialmente aleatoria) o un generador interno de números de hardware.

Esta entrada (!) Que aún puede contener rastros espurios se alimenta a un hash criptográficamente fuerte que elimina esos rastros. ¡Esa es la razón por la que se usan esos CSPRNG, no para crear esos números ellos mismos! El SecureRandomtiene un contador que traza la cantidad de bits utilizado ( getBytes(), getLong()etc.) y recargas de la SecureRandomcon los bits de entropía cuando sea necesario .

En resumen: simplemente olvide las objeciones y úselas SecureRandomcomo un verdadero generador de números aleatorios.

Si considera el número solo como una matriz de bits (o bytes), entonces tal vez podría usar las Random.nextBytessoluciones (seguras) sugeridas en esta pregunta de desbordamiento de pila y luego mapear la matriz en a new BigInteger(byte[]).

Un algoritmo muy simple es aplicar SHA-256 a una secuencia de enteros que incrementen de 0 en adelante. (Se puede agregar una sal si se desea para "obtener una secuencia diferente"). Si suponemos que la salida de SHA-256 es "tan buena como" enteros distribuidos uniformemente entre 0 y 2 ²⁵⁶ - 1, entonces tenemos suficiente entropía para el tarea.

Para obtener una permutación de la salida de SHA256 (cuando se expresa como un número entero) uno simplemente necesita reducirlo en los módulos 52, 51, 50 ... como en este pseudocódigo:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]