Una permutación aleatoria es una ordenación aleatoria de un conjunto de objetos, es decir, una variable aleatoria con valor de permutación . El uso de permutaciones aleatorias suele ser fundamental en campos que utilizan algoritmos aleatorios como la teoría de la codificación , la criptografía y la simulación . Un buen ejemplo de permutación aleatoria es barajar una baraja de cartas : idealmente se trata de una permutación aleatoria de las 52 cartas.
Un método para generar una permutación aleatoria de un conjunto de tamaño n uniformemente al azar (es decir, cada una de las n ! permutaciones tiene la misma probabilidad de aparecer) es generar una secuencia tomando un número aleatorio entre 1 y n secuencialmente, asegurando que haya no hay repetición, e interpretar esta secuencia ( x 1 , ..., x n ) como la permutación
se muestra aquí en notación de dos líneas .
Este método de fuerza bruta requerirá reintentos ocasionales siempre que el número aleatorio elegido sea una repetición de un número ya seleccionado. Esto se puede evitar si, en el i -ésimo paso (cuando ya se han elegido x 1 , ..., x i − 1 ), se elige un número j al azar entre 1 y n − i + 1 y se establece x i igual al jésimo mayor de los números no elegidos.
Un algoritmo simple para generar una permutación de n elementos de manera uniforme y aleatoria sin reintentos, conocido como combinación aleatoria de Fisher-Yates , consiste en comenzar con cualquier permutación (por ejemplo, la permutación de identidad ) y luego pasar por las posiciones 0 hasta n − 2. (Usamos una convención donde el primer elemento tiene el índice 0 y el último elemento tiene el índice n − 1), y para cada posición cambio el elemento que se encuentra actualmente allí con un elemento elegido al azar desde las posiciones i hasta n − 1 (el final) , inclusive. Es fácil verificar que cualquier permutación de n elementos será producida por este algoritmo con una probabilidad exactamente 1/ n !, produciendo así una distribución uniforme sobre todas esas permutaciones.
uniforme sin firmar ( m sin firmar ); /* Devuelve un entero aleatorio 0 <= uniforme(m) <= m-1 con distribución uniforme */ void inicialize_and_permute ( permutación sin signo [], n sin signo ) { i sin signo ; para ( i = 0 ; i <= n -2 ; i ++ ) { sin signo j = i + uniforme ( n - i ); /* Un entero aleatorio tal que i ≤ j < n */ swap ( permutación [ i ], permutación [ j ]); /* Intercambia el elemento elegido aleatoriamente con permutación[i] */ } } Tenga en cuenta que si la uniform()función se implementa simplemente como random() % (m)entonces se introduce un sesgo en los resultados si el número de valores de retorno de random()no es un múltiplo de m, pero esto se vuelve insignificante si el número de valores de retorno de random()es órdenes de magnitud mayores que m.
La distribución de probabilidad del número de puntos fijos en una permutación aleatoria distribuida uniformemente se aproxima a una distribución de Poisson con valor esperado 1 a medida que n crece. En particular, es una aplicación elegante del principio de inclusión-exclusión mostrar que la probabilidad de que no haya puntos fijos se aproxima a 1/ e . Cuando n es lo suficientemente grande, la distribución de probabilidad de los puntos fijos es casi la distribución de Poisson con valor esperado 1. [1] Los primeros n momentos de esta distribución son exactamente los de la distribución de Poisson.
Como ocurre con todos los procesos aleatorios, la calidad de la distribución resultante de una implementación de un algoritmo aleatorio como el aleatorio de Knuth (es decir, qué tan cerca está de la distribución uniforme deseada) depende de la calidad de la fuente subyacente de aleatoriedad, como un generador de números pseudoaleatorios . Hay muchas pruebas de aleatoriedad posibles para permutaciones aleatorias, como algunas de las pruebas Diehard . Un ejemplo típico de tal prueba es tomar alguna estadística de permutación cuya distribución se conoce y probar si la distribución de esta estadística en un conjunto de permutaciones generadas aleatoriamente se aproxima mucho a la distribución verdadera.