Eficiencia de aceptación-rechazo

01 · Punto de partida

Exacto no significa barato

Todo rechazo válido es exacto, pero dos envolventes válidas pueden costar 3 veces distinto. Con N = 10⁷, pasar de tasa 0,68 a 0,25 es pasar de 15 a 40 millones de propuestas, evaluaciones de f y uniformes. La eficiencia se calcula antes de simular en serio.

Este tema convierte la tasa 1/c en presupuesto: intentos esperados, variabilidad y costo por operación.

• ¿Cuántos intentos necesita en promedio cada X aceptada?
• ¿Cómo varía ese número entre réplicas?
• ¿Cómo se compara el costo total contra inversa directa?
• ¿Cuándo un c mayor pero con g más barata gana igual?

02 · Definición

Tasa, intentos y presupuesto

Sea p = 1/c la probabilidad de aceptar un intento. El número de intentos T hasta una aceptada es Geométrica(p): P(T = k) = (1−p)^(k−1)·p, con E[T] = 1/p = c y Var(T) = (1−p)/p² = c·(c−1).

03 · Anatomía

Descomponer el costo por intento

Muestrear g (t_g)

Una inversa barata (uniforme, exponencial) cuesta poco; una g con tabla o normal cuesta más. Multiplica a cada intento, aceptado o no.

Evaluar f y el cociente (t_f)

Potencias, exponenciales y gammas en f pueden dominar. Precalcular constantes y evitar pow donde haya forma cerrada.

Uniformes y bucle (t_u)

Dos uniformes por intento + overhead del while. En N millonario, vectorizar por lotes reduce el costo fijo.

Comparar contra inversa

Inversa: M·t_Q determinista. Rechazo: M·c·(t_g+t_f) aleatorio. Gana el menor en tiempo medido, no en tasa sola.

04 · Reglas de decisión

Cuándo pagar el rechazo

1. 1
   Si hay Q barata.

   Inversa directa casi siempre gana. El rechazo solo compite si Q exige especiales costosos por muestra.

2. 2
   Si c ≤ 2 y g barata.

   Rechazo competitivo y mucho más simple de implementar y auditar que una Q numérica fina.

3. 3
   Si c > 5.

   Buscar mejor g, mezcla por tramos o tabla. Seguir con c alto es pagar 80 %+ de desperdicio.

4. 4
   Si N es enorme.

   El preproceso (tabla, alias, calibrar μ) se amortiza. Medir con time y registrar (Tema 39–40).

05 · Representación en Python

Contar intentos y proyectar presupuesto

El mismo generador del Tema 9, ahora instrumentado: cuenta propuestas, mide tasa y proyecta a M grande.

import random
import math
import time

def experimento(mu, M, seed=70):
    random.seed(seed)
    c = 1 / (mu * math.e * (1 - mu))
    acc, prop = [], 0
    t0 = time.perf_counter()
    while len(acc) < M:
        u1 = random.random()
        y = -math.log(1 - u1) / mu
        u2 = random.random()
        prop += 1
        f = y * math.exp(-y)
        g = mu * math.exp(-mu * y)
        if u2 <= f / (c * g):
            acc.append(y)
    dt = time.perf_counter() - t0
    return c, prop, sum(acc) / len(acc), dt

for mu in [0.5, 0.9]:
    c, prop, media, dt = experimento(mu, 3000)
    print(f"mu={mu} c={c:.2f} propuestas={prop} tasa={3000/prop:.3f} "
          f"media={media:.3f} tiempo={dt:.3f}s")

Esperado: μ=0,5 ~4400 propuestas; μ=0,9 ~12300. La media ≈ 2 en ambos (exactitud igual, costo distinto).

06 · Exploración

Laboratorio: la curva de la tasa vs μ

La curva es la tasa teórica μ·e·(1−μ). Movete μ y M: el punto es tu tasa muestral. Cerca del óptimo μ = 0,5 calza; en bordes la varianza crece y el costo se dispara.

Curva teórica en amarillo, punto naranja = tu simulación. Probá μ = 0,9 (valle) y M = 200 (ruido).

Preguntas para explorar

1. Con μ = 0,5 y M = 1500, ¿cuántas propuestas esperás? ¿Cuántas salen?
2. Pasá a μ = 0,9. ¿La tasa cae a ~0,24? ¿Las propuestas se triplican?
3. Bajá M a 200 con μ = 0,9. ¿La tasa muestral se pega o se dispersa? ¿Por qué?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: Geométrica del costo

Con p = 1/2,46 ≈ 0,407 (Beta), calculá E[T], desvío y P(T > 5). Verificá simulando 20000 intentos.

import random

random.seed(71)
p = 1 / 2.4576
print("E[T] =", round(1 / p, 3))
print("desvío =", round(((1 - p) / p ** 2) ** 0.5, 3))
print("P(T>5) =", round((1 - p) ** 5, 3))
N = 20000
tot = sum(1 for _ in range(N) if random.random() > p)  # no acepta al 1er intento
print("frac. que necesita >1 intento:", round(tot / N, 3), "vs", round(1 - p, 3))

Ejercicio 2: presupuesto para M grande

Proyectá propuestas para M = 100 000 con μ = 0,5 (c = 1,47) y μ = 0,9 (c = 4,09). ¿Factor de ahorro del óptimo?

for mu, c in [(0.5, 1.4715), (0.9, 4.0869)]:
    print(mu, int(100000 * c))
print("factor:", round(4.0869 / 1.4715, 2))

Ejercicio 3: inversa vs rechazo en tiempo

Compará exponencial por inversa (1 log) contra Gamma(2,1) por rechazo óptimo. ¿Cuál da más muestras/segundo? Medí con perf_counter.

import random
import math
import time

random.seed(72)
N = 20000
t0 = time.perf_counter()
for _ in range(N):
    _ = -math.log(1 - random.random()) / 1.5
t_inv = time.perf_counter() - t0

mu, c = 0.5, 4 / math.e
t0 = time.perf_counter()
hechas = 0
while hechas < N:
    y = -math.log(1 - random.random()) / mu
    if random.random() <= (y * math.exp(-y)) / (c * mu * math.exp(-mu * y)):
        hechas += 1
t_rej = time.perf_counter() - t0
print(f"inversa: {t_inv:.3f}s  rechazo: {t_rej:.3f}s")

09 · Síntesis

Ideas para recordar

En el próximo tema cambiaremos de familia: el método de composición para mezclas y casos por partes.