Construcción de tablas de alias

01 · Punto de partida

Del algoritmo a las manos

El Tema 13 mostró el muestreo O(1); este tema abre el preproceso. Construir bien es entender el invariante: en todo momento, masa en pilas + masa en columnas cerradas = n. Cada paso cierra una columna de 1 exacto emparejando un chico con un grande.

Lo haremos con el dado cargado [0,10 · 0,20 · 0,30 · 0,25 · 0,10 · 0,05], q = 6·p, paso a paso y verificable.

• ¿Cómo se clasifican qᵢ en chicos (<1) y grandes (≥1)?
• ¿Qué se escribe en Prob/Alias en cada emparejamiento?
• ¿Cómo se actualiza el donante y se reclasifica?
• ¿Cómo se verifica que cada columna mide 1/n?

02 · Definición

Traza completa del ejemplo guía

q inicial: [0,60 · 1,20 · 1,80 · 1,50 · 0,60 · 0,30]. Chicos {1,5,6}, grandes {2,3,4}.

03 · Anatomía

Bordes que rompen implementaciones ingenuas

Tolerancia 1e−12

Clasificar con q < 1 − tol como chico. Sin tol, un 0,9999999999 por redondeo oscila de pila y el bucle no termina.

Probabilidades cero

pᵢ = 0 ⇒ qᵢ = 0 ⇒ columna vacía que solo aporta alias. Válido: Prob[i] = 0, Alias[i] = donante. Nunca sale i propio.

Normalización previa

Si Σp ≠ 1 por redondeo, dividir por la suma antes de escalar. Escalar sin normalizar reparte el error en todas las columnas.

Verificación por columnas

Para cada k: prob[k]/n + Σ_{j:alias[j]=k}(1−prob[j])/n debe dar pₖ. Test exacto, más fuerte que el histograma.

04 · Implementación que escala

De 6 a 10⁶ categorías

1. 1
   Estructuras.

   deque para small/large (popleft O(1)). Arreglos float[n] y int[n] contiguos para caché en muestreo.

2. 2
   Complejidad.

   O(n) tiempo, O(n) memoria. Para n = 10⁶, segundos de preproceso contra horas de bisect ahorradas.

3. 3
   Empíricas grandes.

   Histogramas de datos con miles de bines fijos: se construye una vez y se muestrea en cada réplica. (Temas 34–35)

4. 4
   Paralelismo.

   La construcción es secuencial; el muestreo es trivialmente paralelo (una semilla por hilo). No paralelizar pilas.

05 · Representación en Python

Constructor que imprime su traza

La misma construcción del Tema 13, ahora con registro de pasos y verificación por columnas.

from collections import deque

probs = [0.10, 0.20, 0.30, 0.25, 0.10, 0.05]
n = len(probs)
q = [p * n for p in probs]
prob = [0.0] * n
alias = [0] * n
small = deque([i for i, v in enumerate(q) if v < 1 - 1e-12])
large = deque([i for i, v in enumerate(q) if v >= 1 - 1e-12])
print("q0:", [round(v, 2) for v in q])

paso = 1
while small and large:
    s, g = small.popleft(), large.popleft()
    prob[s], alias[s] = q[s], g
    print(f"paso {paso}: s={s+1} g={g+1} Prob[{s+1}]={q[s]:.2f} Alias[{s+1}]={g+1}", end=" ")
    q[g] -= (1 - q[s])
    print(f"q[{g+1}] queda {q[g]:.2f}")
    (small if q[g] < 1 - 1e-12 else large).append(g)
    paso += 1
for i in list(small) + list(large):
    prob[i] = 1.0
    alias[i] = i
print("Prob:", [round(v, 2) for v in prob], "Alias:", [a + 1 for a in alias])

for k in range(n):
    pk = prob[k] / n + sum((1 - prob[j]) / n for j in range(n)
                           if alias[j] == k and prob[j] < 1 - 1e-12)
    print(k + 1, round(pk, 3), "ok" if abs(pk - probs[k]) < 1e-9 else "FALLA")

La verificación debe dar “ok” en las 6. Si alguna falla, el alias de esa columna apunta mal.

06 · Exploración

Laboratorio: ver llenarse las columnas

Avanzá el paso 0 → 6. Las barras son q (saldo vivo); la línea es 1. Al cerrar una columna su barra se congela en Prob y el donante baja. Leé la acción debajo.

Barras por categoría 1–6. Las cerradas se muestran en verde con su Prob; las vivas en celeste con su saldo q.

Preguntas para explorar

1. En el paso 1, ¿qué Prob/Alias se fija y cuánto le queda al donante 2?
2. ¿En qué paso el donante 2 pasa de grande a chico? ¿Qué lo provoca?
3. Al final, ¿qué columnas quedan puras (Prob = 1)?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: traza a mano y a código

Sin ejecutar: con q = [0,6 · 1,2 · 1,8 · 1,5 · 0,6 · 0,3], ¿qué se fija en el paso 1? Verificá con el bloque del Tema 13.

# Paso 1: s=1 (0.6), g=2 (1.2) -> Prob[1]=0.6 Alias[1]=2, q2=0.8
print("Prob[1]=0.6 Alias[1]=2 q2=0.8")

Ejercicio 2: columna con cero

Construí alias para p = [0,5 · 0,0 · 0,5] y verificá que la columna 2 queda Prob = 0 con alias válido y nunca sale como propia.

from collections import deque

probs = [0.5, 0.0, 0.5]
n = 3
q = [p * n for p in probs]
print("q:", q)
# q = [1.5, 0.0, 1.5]: el 0.0 es chico, se cierra con Prob=0 de inmediato.

Ejercicio 3: invariante auditado

Instrumentá el constructor para afirmar en cada paso que suma(q en pilas) + cerradas = n − cerradas·0… (formulá el invariante exacto) o al menos que toda columna cerrada mide 1.

from collections import deque

probs = [0.10, 0.20, 0.30, 0.25, 0.10, 0.05]
n = len(probs)
q = [p * n for p in probs]
prob = [None] * n
alias = [None] * n
small = deque([i for i, v in enumerate(q) if v < 1 - 1e-12])
large = deque([i for i, v in enumerate(q) if v >= 1 - 1e-12])
cerradas = 0
while small and large:
    s, g = small.popleft(), large.popleft()
    assert 0 <= q[s] < 1 + 1e-9, "s debe ser chico"
    prob[s], alias[s] = q[s], g
    q[g] -= (1 - q[s])
    cerradas += 1
    assert abs((prob[s] + (1 - prob[s])) - 1) < 1e-9
    (small if q[g] < 1 - 1e-12 else large).append(g)
print("cerradas:", cerradas, "OK")

09 · Síntesis

Ideas para recordar

En el próximo tema veremos otra familia discreta secuencial: los métodos de urna.