Simulación de Monte Carlo exacta de un histograma de muestra grande

Question

(Preguntado esto en MathOverflow, consiguió redirige aquí)

Supongamos que queremos crear un histograma de $N$ muestras de algunos simple compacta compatible distribución en $\mathbb{R}$ donde $N$ es muy grande, decir $N = 10^{30}$. El histograma ha $K$ distintos depósitos, donde $K$ es más razonable número como $10$ o $1000$. Obviamente, no es viable para mí directamente dibujar $N$ Monte Carlo muestras de mi distribución y reciclaje de ellos en forma de histograma. Sin embargo, a mí me parece que podría haber algún método correcto que funciona mediante el muestreo, el número de cuentas en cada contenedor, de una en una, para un total de sólo $K$ de las muestras. Estoy buscando algo de ayuda para encontrar un método de este tipo.

El número de cuentas en cada bin es una variable aleatoria binomial con parámetros que pueden ser fácilmente calculado mediante la integración de la distribución en la papelera de intervalo. Así que si tengo una buena manera de simular variables aleatorias binomiales con grandes medios, puedo simular que el número de cuentas en cada bin usando sólo $K$ Monte Carlo atrae de una variable aleatoria binomial.

El problema es que el total de la cuenta en los contenedores están correlacionados por la restricción que se debe agregar a a $N$. Mi método se producen un número al azar del total de la cuenta que casi seguro que no ser $N$.

No puedo pensar en un par de métodos más sofisticados que evite este problema, pero en la que crean más espinoso - y la línea de fondo es, no sé cómo probar que cualquiera de estos métodos heurísticos son correctos.

¿Alguien puede pensar en un $O(K)$ algoritmo que genera un modo demostrable correcto (o seguramente casi lo correcto) histograma de la muestra para este tipo de problema? Más formalmente, un método correcto para el muestreo aleatorio vector $H \in \mathbb{Z}^K$ cuyas entradas son el histograma cuenta? Si no, ¿qué es lo mejor que puedo esperar?

Answer 1

Simulación (Sheldon Ross) le da un algoritmo en la sección 4.6 señalando que un resultado $X_1,\ldots,X_K$ puede ser generado en la secuencia debido a $X_1$ tiene una distribución binomial y cada uno de los condicional distribución $X_i | X_{i-1}, \ldots, X_1$ también es binomial.

Específicamente, si el $K$ bin probabilidades se $p_1, p_2, \ldots, p_K$, dibujar $x_1$ a partir de un binomio$(N,p_1)$ de distribución, a continuación, dibuje $x_2$ a partir de un binomio$(N-x_1, p_2/(1-p_1))$ distribución, ..., $x_{i+1}$ a partir de un binomio$(N-x_1-\cdots-x_i, p_{i+1}/(1-p_1-\cdots-p_i))$ distribución, etc.

Aquí es un (recursivo) Mathematica aplicación.

ClearAll[f];
f[n_, p_] /; Length[p] >= 2 := 
  With[{x = RandomInteger[BinomialDistribution[n, First[p]]]},
   {x, f[n - x, Rest[p] / (Plus @@ Rest[p])]}];
f[0, p_] := 0 p;
f[n_, p_] /; Length[p] == 1 := n;

Ejemplo de uso:

x = Block[{p = 1/Range[500], $RecursionLimit = 2000},
   f[10^30, p/(Plus @@ p)] // Flatten
];

(4.7 segundos).

Cuando las expectativas son todos mayores de 10 o así que usted puede hacer esto mucho más rápido mediante la aproximación de la multinomial como (degenerado) distribución normal multivariante.