Una permutación aleatoria es una ordenación aleatoria de un conjunto de objetos, es decir, una variable aleatoria valorada por permutación . El uso de permutaciones aleatorias suele ser fundamental para los campos que utilizan algoritmos aleatorizados como la teoría de codificación , la criptografía y la simulación . Un buen ejemplo de una permutación aleatoria es el barajado de una baraja de cartas : lo ideal es una permutación aleatoria de las 52 cartas.
Generando permutaciones aleatorias
Método de fuerza bruta entrada por entrada
Un método para generar una permutación aleatoria de un conjunto de longitud 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, asegurándose de que haya no es una 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 elegido al azar 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 iguala x i al j- ésimo número más grande de los no elegidos.
Fisher-Yates baraja
Un algoritmo simple para generar una permutación de n elementos uniformemente al azar sin reintentos, conocido como el shuffle de Fisher-Yates , es comenzar con cualquier permutación (por ejemplo, la permutación de identidad ) y luego pasar por las posiciones 0 a n - 2 (que utilizar una convención de que el primer elemento tiene índice 0, y el último elemento tiene índice n - 1), y para cada posición i intercambiar el elemento actualmente allí con un elemento elegido al azar de las posiciones i a través de n - 1 (el extremo) , inclusive. Es fácil verificar que cualquier permutación de n elementos será producida por este algoritmo con 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 initialize_and_permute ( permutación sin firmar [], n sin firmar ) { i sin firmar ; para ( i = 0 ; i <= n -2 ; i ++ ) { sin signo j = i + uniforme ( n - i ); / * Un número entero aleatorio tal que i ≤ j swap ( permutación [ i ], permutación [ j ]); / * Intercambiar el elemento seleccionado al azar con permutación [i] * / } }
Tenga en cuenta que si la uniform()
función se implementa simplemente como random() % (m)
, se introduce un sesgo en los resultados si el número de valores devueltos de random()
no es un múltiplo de m, pero esto se vuelve insignificante si el número de valores devueltos de random()
es órdenes de magnitud mayor que m.
Estadísticas sobre permutaciones aleatorias
Puntos fijos
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 elegante aplicación del principio de inclusión-exclusión para mostrar que la probabilidad de que no haya puntos fijos se acerca 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.
Prueba de aleatoriedad
Al igual que con todos los procesos aleatorios, la calidad de la distribución resultante de una implementación de un algoritmo aleatorio como el Shuffle 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 para la que se conoce la distribución y probar si la distribución de esta estadística en un conjunto de permutaciones generadas al azar se aproxima mucho a la distribución verdadera.
Ver también
- Fórmula de muestreo de Ewens : una conexión con la genética de poblaciones
- Faro aleatorio
- Constante de Golomb-Dickman
- Estadísticas de permutación aleatoria
- Algoritmos de barajado : método de ordenación aleatoria, método de intercambio iterativo
Referencias
- ↑ Durstenfeld, Richard (1 de julio de 1964). "Algoritmo 235: permutación aleatoria" . Comunicaciones de la ACM . 7 (7): 420. doi : 10.1145 / 364520.364540 .
enlaces externos
- Permutación aleatoria en MathWorld
- Generación de permutación aleatoria : explicación detallada y práctica del algoritmo shuffle de Knuth y sus variantes para generar k -permutaciones (permutaciones de k elementos elegidos de una lista) y k -subconjuntos (generando un subconjunto de los elementos en la lista sin reemplazo) con pseudocódigo