Permutación aleatoria

Una permutación aleatoria  es una ordenación aleatoria de un conjunto de objetos, es decir, una variable aleatoria cuyos eventos elementales son permutaciones . El uso de permutaciones aleatorias suele ser la base en campos que utilizan algoritmos aleatorios . Dichos campos incluyen la teoría de la codificación , la criptografía y el modelado . Un buen ejemplo de una permutación aleatoria es barajar una baraja de cartas .

Generando permutaciones aleatorias

Método directo (elemento por elemento)

Un método para generar una permutación aleatoria de un conjunto de n elementos es utilizar una distribución uniforme , que selecciona secuencialmente números aleatorios entre 1 y n , al tiempo que garantiza que no haya repeticiones. La sucesión resultante ( x 1 , …, x n ) se interpreta como una permutación

El método de generación directa requiere repetir la selección de un número aleatorio si el número sorteado ya está en la secuencia. Esto se puede evitar si, en el i -ésimo paso (cuando ya están elegidos x 1 , …, x i - 1 ), se elige un número aleatorio j entre 1 y n - i + 1 y, luego, se elige x i igual a el j -ésimo número no elegido.

Whip Shuffleing

Un algoritmo simple para generar permutaciones aleatorias de n elementos (distribuidos uniformemente) sin repeticiones, conocido como barajado de Knuth , comienza con una permutación arbitraria (por ejemplo, la permutación idéntica sin permutar los elementos) y va desde la posición 1 hasta la posición n − 1, permutar el elemento por las posiciones i con un elemento seleccionado aleatoriamente en las posiciones i a n inclusive. Es fácil demostrar que de esta manera obtenemos todas las permutaciones de n elementos con una probabilidad de exactamente 1/ n !.

Estadísticas sobre permutaciones aleatorias

Puntos fijos

La distribución de probabilidad del número de puntos fijos en permutaciones aleatorias uniformemente distribuidas en n elementos se aproxima a la ley de Poisson a medida que n crece . Contar el número de puntos fijos es un ejemplo clásico del uso de la fórmula de inclusión-exclusión , que muestra que la probabilidad de que no haya puntos fijos se aproxima a 1/ e . En este caso, la expectativa matemática del número de puntos fijos es igual a 1 para cualquier tamaño de permutación. [una]

Prueba de aleatoriedad

Como ocurre con todos los procesos aleatorios, la calidad de un algoritmo de generación de permutaciones, en particular el algoritmo de barajado de Knuth, depende del generador de números aleatorios subyacente, como el generador de números pseudoaleatorios . Hay un gran número de posibles pruebas de aleatoriedad , como las pruebas intransigentes . Un ejemplo típico de tal prueba es elegir alguna estadística para la cual se conoce la distribución y verificar si la distribución de esta estadística en el conjunto de permutaciones obtenidas es lo suficientemente cercana a la distribución real.

Véase también

Notas

  1. ↑ D. Knuth, R. Graham, O. Patashnik. matemáticas concretas. - Mundo, 1998.

Literatura

Enlaces