Permutaciones aleatorias

01 · Punto de partida

Mezclar sin favoritismos

¿El orden de las preguntas de un examen? ¿El mazo antes de repartir? ¿La fila de atención al azar? Mezclar es elegir una de las n! permutaciones con igual probabilidad: si alguna ordenación sale más que otras, el sorteo está sesgado aunque cada carta “parezca” moverse.

Es el caso m = n del Tema 31 llevado al orden completo: el motor es Fisher-Yates (Tema 33) y la auditoría mira posiciones y puntos fijos, no solo “si se movió”.

• ¿Qué significa P(π) = 1/n! y cómo se testea con n = 52?
• ¿Por qué cada elemento cae en cada posición con prob. 1/n?
• ¿Cuántos puntos fijos esperar y con qué ley?
• ¿Qué mezclas populares no son uniformes?

02 · Definición

Uniformidad global y marginales planas

P(π) = 1/n! para toda π. Por simetría, P(elemento i en posición j) = 1/n y P(i antes que k) = 1/2. Los puntos fijos (i queda en i) suman media 1 con ley C(n,k)·D(n−k)/n!, donde D cuenta desarreglos.

03 · Anatomía

Fisher-Yates, sort y Sattolo

Fisher-Yates O(n) exacto

Recorrer i de n−1 a 1 sorteando j ∈ {0,…,i} e intercambiando. Cada permutación sale con 1/n!: el método de referencia (Tema 33).

Sort por clave aleatoria

Asignar U a cada elemento y ordenar: uniforme pero O(n log n) y con empates que hay que romper. Útil si ya hay un sort a mano, nunca la vía rápida.

Sattolo: un solo ciclo

Variante con j ∈ {0,…,i−1} que genera solo ciclos largos: ningún punto fijo jamás. Sirve para “amigo invisible”, no como mezcla justa.

Ingenuo con rango fijo

Sortear j ∈ {0,…,n−1} en cada paso repite salidas y sesga (algunas π salen más). Es el bug más famoso del muestreo.

04 · Dónde se mezcla

Del mazo al experimento

1. 1
   Juegos y sorteos.

   Mazos, bolilleros, turnos: justicia = uniformidad sobre n!.

2. 2
   Diseño experimental.

   Orden de tratamientos y preguntas para anular efectos de posición y aprendizaje.

3. 3
   Tests por permutación.

   Reasignar etiquetas al azar miles de veces: la nula se construye mezclando.

4. 4
   Puente a Fisher-Yates.

   El algoritmo que lo hace perfecto en O(n), paso a paso. (Tema 33)

05 · Representación en Python

Mezcla y matriz de posiciones

Fisher-Yates a mano más la matriz n×n de frecuencias: cada casilla debe rondar 1/n.

import random

random.seed(280)
n, B = 6, 6000

def fisher_yates(xs):
    xs = list(xs)
    for i in range(len(xs) - 1, 0, -1):
        j = int((i + 1) * random.random())
        xs[i], xs[j] = xs[j], xs[i]
    return xs

mat = [[0]*n for _ in range(n)]
fijos = 0
for _ in range(B):
    p = fisher_yates(range(n))
    fijos += sum(1 for i, v in enumerate(p) if i == v) / B
    for j, v in enumerate(p):
        mat[v][j] += 1
print("casilla (0,0):", round(mat[0][0]/B, 3), "vs", round(1/n, 3))
print("fijos medios:", round(fijos, 3), "vs 1.0")

Casillas ≈ 0,167 y fijos ≈ 1,0. Si una diagonal queda alta, el rango del sorteo está mal.

06 · Exploración

Laboratorio: fijos que tienden a Poisson(1)

Movete n y B. Las barras cuentan puntos fijos 0…n en B mezclas; los rombos son C(n,k)·D(n−k)/n!. Desde n = 5 la forma ya es Poisson(1) con P(0) ≈ 0,368.

Barras 0…n vs rombos exactos. Probá n = 3 (todavía no Poisson) y n = 10 (clavado).

Preguntas para explorar

1. Con n = 6, ¿fijos medios y P(0) teóricos?
2. Bajá a n = 3. ¿P(0) = 0,333 se despega de 1/e?
3. Subí a n = 10 con B = 500. ¿Las barras altas (k ≥ 4) quedan vacías por sesgo o por rareza?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: matriz plana n = 5

n = 5, B = 10000 (semilla 281): cada casilla debe rondar 0,20 con error máx. < 0,02.

import random

random.seed(281)
n, B = 5, 10000
mat = [[0]*n for _ in range(n)]
for _ in range(B):
    xs = list(range(n))
    for i in range(n-1, 0, -1):
        j = int((i+1)*random.random())
        xs[i], xs[j] = xs[j], xs[i]
    for j, v in enumerate(xs):
        mat[v][j] += 1
f = [c/B for fila in mat for c in fila]
print(round(min(f), 3), round(max(f), 3), "vs 0.2")

Ejercicio 2: desarreglo del mazo chico

n = 6, B = 8000: estimá P(0 fijos) ≈ 0,368 y compará con 1/e.

import random
import math

random.seed(282)
n, B = 6, 8000
cero = 0
for _ in range(B):
    xs = list(range(n))
    for i in range(n-1, 0, -1):
        j = int((i+1)*random.random())
        xs[i], xs[j] = xs[j], xs[i]
    if all(i != v for i, v in enumerate(xs)):
        cero += 1
print(round(cero/B, 3), "vs", round(1/math.e, 3))

Ejercicio 3: cazar el rango fijo

Compará Fisher-Yates (j ≤ i) contra ingenuo (j en todo n) con n = 4 y B = 20000: mirá la casilla (0,0).

import random

random.seed(283)
n, B = 4, 20000
for nombre, bien in [("FY", True), ("ingenuo", False)]:
    c00 = 0
    for _ in range(B):
        xs = list(range(n))
        for i in range(n-1, 0, -1):
            j = int((i+1)*random.random()) if bien else int(n*random.random())
            xs[i], xs[j] = xs[j], xs[i]
        c00 += (xs[0] == 0)
    print(nombre, round(c00/B, 3), "vs 0.25")

09 · Síntesis

Ideas para recordar

En el próximo tema el algoritmo estrella: Fisher-Yates paso a paso.