Método de alias
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En informática , el método de alias es una familia de algoritmos eficientes para el muestreo de una distribución de probabilidad discreta , publicado en 1974 por AJ Walker. [1] [2] Es decir, devuelve valores enteros 1 ≤ i ≤ n de acuerdo con alguna distribución de probabilidad arbitraria p i . Los algoritmos suelen utilizar un tiempo de preprocesamiento O ( n log n ) u O ( n ) , después del cual se pueden extraer valores aleatorios de la distribución en O (1)tiempo. [3]

Operación

Internamente, el algoritmo consulta dos tablas, una tabla de probabilidad U i y una tabla de alias K i (para 1 ≤ i ≤ n ). Para generar un resultado aleatorio, se tira un dado justo para determinar un índice en las dos tablas. Sobre la base de la probabilidad almacenada en ese índice, una moneda sesgada a continuación, se da la vuelta, y el resultado de la tapa se utiliza para elegir entre un resultado de i y K i . [4]

Más concretamente, el algoritmo funciona de la siguiente manera:

  1. Genere una variable aleatoria uniforme 0 ≤ x <1 .
  2. Sea i = ⌊ nx ⌋ + 1 e y = nx + 1 - i . (Esto hace i uniformemente distribuida sobre {1, 2, ..., n } y y distribuidos de manera uniforme en [0, 1) ).
  3. Si y < U i , devuelve i . Este es el lanzamiento de moneda sesgado.
  4. De lo contrario, devuelva K i .

Una formulación alternativa de la tabla de probabilidad, propuesta por Marsaglia et. Alabama. [5] como método de "histograma cuadrado", utiliza la condición x < V i en el tercer paso (donde V i = ( U i + i - 1) / n ) en lugar de calcular y .

Generación de tablas

La distribución puede rellenarse con probabilidades adicionales p i = 0 para aumentar n a un valor conveniente, como una potencia de dos.

Para generar la tabla, primero inicialice U i = np i . Mientras hace esto, divida las entradas de la tabla en tres categorías:

  • El grupo "overfull", donde U i > 1 ,
  • El grupo "insuficiente", donde U i <1 y K i no se ha inicializado, y
  • El grupo "exactamente completo", donde U i = 1 o K i se ha inicializado.

Si U i = 1 , el valor correspondiente K i nunca será consultado y no es importante, pero un valor de K i = i es sensato.

Siempre que no todas las entradas de la tabla estén exactamente llenas, repita los siguientes pasos:

  1. Elija arbitrariamente una entrada demasiado completa U i > 1 y una entrada insuficiente U j <1 . (Si uno de estos existe, el otro también debe).
  2. Asigne el espacio no utilizado en la entrada j al resultado i , estableciendo K j = i .
  3. Elimine el espacio asignado de la entrada i cambiando U i = U i - (1 - U j ) = U i + U j - 1 .
  4. La entrada j ahora está exactamente llena.
  5. Asigne la entrada i a la categoría apropiada según el nuevo valor de U i .

Cada iteración mueve al menos una entrada a la categoría "exactamente completa" (y la última mueve dos), por lo que se garantiza que el procedimiento terminará después de n −1 iteraciones como máximo . Cada iteración se puede realizar en O (1) tiempo, por lo que la tabla se puede configurar en O ( n ) tiempo.

Vose [3] : 974  señala que los errores de redondeo de coma flotante pueden hacer que se viole la garantía mencionada en el paso 1. Si una categoría se vacía antes que la otra, las entradas restantes pueden tener U i establecida en 1 con un error insignificante. La solución que tiene en cuenta el punto flotante a veces se denomina método de Walker-Vose o método de alias de Vose .

La estructura de Alias ​​no es única.

A medida que el procedimiento de búsqueda es un poco más rápido si y < T i (porque K i no es necesario que se consulte), uno de los objetivos durante la generación de la tabla es maximizar la suma de la U i . Hacer esto de manera óptima resulta ser NP difícil , [5] : 6  pero un algoritmo codicioso se acerca razonablemente: robar a los más ricos y dar a los más pobres. Es decir, en cada paso elija la mayor U i y la menor U j . Debido a que esto requiere ordenar la U i , requiere O ( n logn ) tiempo.

Eficiencia

Aunque el método de alias es muy eficiente si generar un desvío uniforme es en sí mismo rápido, hay casos en los que está lejos de ser óptimo en términos de uso de bits aleatorios. Esto se debe a que utiliza una variable aleatoria x de precisión total cada vez, incluso cuando solo se necesitan unos pocos bits aleatorios.

Un caso surge cuando las probabilidades están particularmente bien equilibrados, por lo que muchos U i = 1 y K i no es necesario. Generar y es una pérdida de tiempo. Por ejemplo, si p 1 = p 2 = 1 ⁄ 2 , entonces se podría usar una variable aleatoria x de 32 bits para hacer 32 elecciones, pero el método de alias solo generará una.

Otro caso surge cuando las probabilidades están fuertemente desequilibradas, por lo que U i ≈ 0 . Por ejemplo, si p 1 = 0,999 y p 2 = 0,001 , entonces la gran mayoría de las veces, solo se requieren unos pocos bits aleatorios para determinar que se aplica el caso 1. En tales casos, el método de tabla descrito por Marsaglia et al. [5] : 1–4  es más eficiente. Si hacemos muchas elecciones con la misma probabilidad, en promedio podemos requerir mucho menos de un bit aleatorio insesgado. Usando técnicas de codificación aritmética aritmética podemos acercarnos al límite dado por la función de entropía binaria .

Literatura

Implementaciones

Referencias

  1. ^ Walker, AJ (abril de 1974). "Nuevo método rápido para generar números aleatorios discretos con distribuciones de frecuencia arbitrarias". Cartas de electrónica . 10 (8): 127. doi : 10.1049 / el: 19740097 .
  2. ^ Walker, AJ (septiembre de 1977). "Un método eficiente para generar variables aleatorias discretas con distribuciones generales". Transacciones ACM en software matemático . 3 (3): 253–256. doi : 10.1145 / 355744.355749 .
  3. ↑ a b Vose, Michael D. (septiembre de 1991). "Un algoritmo lineal para generar números aleatorios con una distribución determinada" (PDF) . Transacciones IEEE sobre ingeniería de software . 17 (9): 972–975. CiteSeerX 10.1.1.398.3339 . doi : 10.1109 / 32.92917 . Archivado desde el original (PDF) el 29 de octubre de 2013.  
  4. ^ "Dardos, dados y monedas: muestreo de una distribución discreta" . KeithSchwarz.com . 29 de diciembre de 2011 . Consultado el 27 de diciembre de 2011 .
  5. ^ a b c Marsaglia, George ; Tsang, Wai Wan; Wang, Jingbo (12 de julio de 2004), "Generación rápida de variables aleatorias discretas", Journal of Statistical Software , 11 (3): 1–11, doi : 10.18637 / jss.v011.i03
Obtenido de " https://en.wikipedia.org/w/index.php?title=Alias_method&oldid=1046298320 "
Contribute a better translation