Muestreo de distribución categórica cuando la clasificación de paso se omite

Question

La que comúnmente se utiliza el algoritmo de muestreo de categórico de distribución es

1. ordenar el vector de probabilidades acumuladas $\boldsymbol{p} = (p_1,p_2,\dots,p_n)$ en orden decreciente a partir de las categorías que aparecen con mayor, a la que aparecen con menores probabilidades de obtener el permutada vector de $\boldsymbol{p}_{\pi}$,
2. ejemplo de $u$ a partir de una distribución uniforme en $(0,1)$,
3. aceptar el menor $k$ tal que $p_{\pi(k)} \ge u$ $X$ (donde $\pi(k)$ es la posición de $k$ en permutada vector $\boldsymbol{p}_{\pi}$).

Lo de la clasificación (es decir, que comienza en el modo) no hace que el número de comparaciones a realizar antes de detenerse menor, por lo que debe ser más eficiente* a continuación, el "ingenuo" algoritmo usando sin clasificar probabilidades (ordinario inversa de la transformación).

Sin embargo, mi pregunta es: ¿ignorando la clasificación de paso tiene ningún otro efecto en el algoritmo además de reducir el rendimiento del algoritmo (supongo que no, pero estoy buscando la justificación)? Por otra parte, ¿cuánto (cuando) no es en realidad el cambio en términos de rendimiento?

_{* - He hecho algunas pruebas de referencia sobre esto, pero lo hicieron no se dan ninguna de resultados concluyentes.}

Answer 1

El orden de la distribución acumulativa no es necesario, pero la hay de forma automática.

Deje $(\phi_1,\ldots,\phi_n)$ ser de la categoría de distribución y $p_i=\sum_{k=1}^i\phi_k$ las entradas de la distribución acumulativa. Ahora, desde la $p_1\le \ldots \le p_i\le p_{i+1}\le \ldots p_n$, la probabilidad de que un uniforme dibujado $u\in (0,1)$ $(p_i,p_{i+1})$ es exactamente $p_{i+1}-p_i=\phi_i$.

Incluso si el acumulado de pedidos no está ordenado, es decir que se tiene $(p_{\pi(1)},\ldots,p_{\pi(n)})$, tendría que determinar el $\pi(k)$ tal que $p_{\pi(k)}=\max\{p_{\pi(i)}: p_{\pi(i)}\le u\}$ (max, porque yo ordenados incresingly). Desde la posición de $p_{\pi(k)}$ en los no ordenados de distribución acumulativa es $k$, escoja $\phi_k$.