Fisher-Yates

01 · Punto de partida

El algoritmo que sí reparte 1/n!

El Tema 32 definió la mezcla justa; este tema la construye: Fisher-Yates recorre el arreglo de atrás hacia adelante, sortea j ∈ {0,…,i} e intercambia. Con n−1 sorteos produce las n! permutaciones equiprobables en O(n) y O(1) extra.

Todo el tema cabe en una línea —el rango—: achicarlo da perfección, congelarlo da el sesgo más famoso del muestreo.

• ¿Por qué j ∈ {0…i} y no en todo el arreglo?
• ¿Cómo prueba la inducción que cada π sale con 1/n!?
• ¿Qué es la variante inside-out y cuándo sirve?
• ¿Cómo se ve el sesgo del rango fijo en la matriz?

02 · Definición

Rango menguante e inducción

En el paso i hay i+1 candidatos para la posición i, cada uno con 1/(i+1). Fijada esa posición, el resto es una mezcla justa de i elementos por hipótesis inductiva: 1/(i+1)·1/i! = 1/(i+1)!. Base: con i = 0 no hay nada que sortear.

03 · Anatomía

Variantes, enteros y base uniforme

Inside-out O(n)

a[0] = fuente[0]; para i ≥ 1: j ∈ {0,…,i}; a[i] = a[j]; a[j] = fuente[i]. Misma ley 1/n!, útil si la mezcla se consume en orden o la fuente es un iterador.

Entero sin módulo

j = int((i+1)·U) es exacto en la práctica (Tema 17); randbits % (i+1) sesga salvo que el rango base sea múltiplo. Con i grande, rechazo de Lemire.

Parcial gratis

Frenar en i = n−m da el subconjunto ordenado del Tema 31: Fisher-Yates contiene al sin reemplazo como prefijo.

Fuente base honesta

El algoritmo no crea azar: con PRNG pobre o semilla repetida, la mezcla “perfecta” repite el mismo π. Semilla fresca por experimento.

04 · Dónde mezcla Yates

Del algoritmo al ecosistema

1. 1
   shuffle de librería.

   random.shuffle es Fisher-Yates: este tema explica lo que ya usás.

2. 2
   Subconjuntos.

   Frenar antes de tiempo da el Tema 31 sin código extra.

3. 3
   Streaming.

   Inside-out mezcla lo que llega sin guardarlo todo primero.

4. 4
   Tests por permutación.

   Miles de mezclas justas por segundo para la nula empírica.

05 · Representación en Python

Clásico e inside-out frente a frente

Ambas variantes con la misma semilla conceptual: idéntica ley, distinto recorrido. Auditoría por matriz plana.

import random

random.seed(290)
n, B = 8, 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

def inside_out(fuente):
    a = [fuente[0]]
    for i in range(1, len(fuente)):
        j = int((i+1)*random.random())
        a.append(fuente[i])
        a[i], a[j] = a[j], a[i]
    return a

c00 = sum(1 for _ in range(B) if fisher_yates(range(n))[0] == 0)
random.seed(290)
c00b = sum(1 for _ in range(B) if inside_out(list(range(n)))[0] == 0)
print("clásico (0,0):", round(c00/B, 3), "vs", round(1/n, 3))
print("inside-out (0,0):", round(c00b/B, 3), "vs", round(1/n, 3))

Ambas ≈ 0,125. Si alguna casilla se despega con B = 6000, el rango está mal puesto.

06 · Exploración

Laboratorio: el rango fijo deja manchas

La matriz n×n resume B mezclas: cada casilla debe rondar 1/n. Con el rango correcto la peor mancha es ruido; activá el modo ingenuo y mirá cómo el chi-cuadrado explota.

Barras = peores 25 casillas vs línea 1/n; el número es el chi total. Probá el ingenuo con n = 8.

Preguntas para explorar

1. Con n = 8 correcto, ¿chi ≈ n²−1 = 63? ¿Mancha pequeña?
2. Activá el ingenuo. ¿El chi se multiplica? ¿La (0,0) se dispara hacia 0,39?
3. Con B = 500 correcto, ¿el chi baila aunque el método sea justo?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: chi de la matriz n = 6

n = 6, B = 12000 (semilla 291): el chi debe rondar 35 ± 12. El ingenuo da > 200.

import random

random.seed(291)
n, B = 6, 12000
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
e = B/n
print("chi:", round(sum((c-e)**2/e for f in mat for c in f), 1), "vs ~35")

Ejercicio 2: inside-out en streaming

Mezclá un iterador que no existe como lista (semilla 292) y verificá casilla (0,0) ≈ 1/8.

import random

random.seed(292)
n, B = 8, 8000
c00 = 0
for _ in range(B):
    a = [0]
    for i in range(1, n):
        j = int((i+1)*random.random())
        a.append(i)
        a[i], a[j] = a[j], a[i]
    c00 += (a[0] == 0)
print(round(c00/B, 3), "vs 0.125")

Ejercicio 3: el módulo que mancha

Generá j con int(100·U) % (i+1) vs int((i+1)·U) con n = 7, B = 15000: compará el chi.

import random

def chi(mal, seed):
    random.seed(seed)
    n, B = 7, 15000
    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(100*random.random()) % (i+1) if mal else int((i+1)*random.random())
            xs[i], xs[j] = xs[j], xs[i]
        for j, v in enumerate(xs):
            mat[v][j] += 1
    e = B/n
    return sum((c-e)**2/e for f in mat for c in f)

print("bien:", round(chi(False, 293), 1), "vs ~48")
print("mal: ", round(chi(True, 294), 1))

09 · Síntesis

Ideas para recordar

En el próximo tema los datos mandan: distribuciones empíricas.