Escogiendo al azar de $n$ opciones aproximadamente $n$ veces. ¿Lo que ' s la resultante distribución de frecuencia de llamada?

Question

No estoy seguro de que la mejor manera de redactar esta pregunta, pero voy a darle una oportunidad.

Si tuviera que elegir al azar los números enteros entre 1 y $n$ un número significativo de veces con respecto a la $n$ (es decir, $m$ donde $m$ es algo así como el 70% de % de$n$) y, a continuación, miró a la distribución de frecuencias de los resultados, creo que podría tener una distribución que no era plana. I. e. un número muy pequeño de los resultados vendrían >1 veces, la mayoría vienen de hasta 1 hora, y algunos de los resultados que habría de venir hasta 0 veces. Obviamente, esto sería afectada por el tamaño relativo de $m$$n$: Si yo tuviera que elegir un sólo 10 números entre 0 y 1,000,000 ($m$=10, $n$=1,000,000), yo esperaría que la gran mayoría de los números que tienen una frecuencia de 0, con el resto 1.

Tengo preguntas:

1. Es esto correcto?
2. ¿Cómo calcular la frecuencia esperada de los más frecuentes número elegido?
3. Si usted se para ordenar los resultados según la frecuencia y, a continuación, gráfico de barras de la frecuencia, hace que la curva resultante tiene un nombre, o cualquier interesantes propiedades?

Espero que esto tiene algún tipo de sentido. Si no, hágamelo saber y voy a tratar de pensar en una mejor manera de explicarlo. Todo esto viene de una pregunta original que fue algo como esto: "Si tengo una lotería de la máquina con 15 millones de diferente número de la lotería resultado de combinaciones, dado que ya he hecho 10 millones de sorteos, ¿cuál es la probabilidad de que el 10,000,001 th sorteo ya ha sido dibujada?"

Editar:

Corrí algunas simulaciones monte-carlo para $2<n<650$, con $m$=$n$ y el número total de experimentos para cada una de las $n$ 10.000 veces y un promedio de los resultados. En que se registra la máxima frecuencia, el número de veces que un número salió el 1 de tiempo, y el número de veces que un número salga 0 veces. Dos cosas interesantes: El número de números que vienen 1 vez coincide con el calculado $n p(k)$, y esto también está cerca de la cantidad de veces que un número salga 0 veces. No estoy seguro de que es obvio que estos dos debe ser el mismo, como $p(k)$ no parece tener sentido para $k=0$ (se Puede hacer $m$ elija $0$?). También, curiosamente, en una parcela de $m$ contra el promedio de la frecuencia máxima da una curva que se parece a esto:

Obviamente algún tipo de registro de relación.

El próximo paso es modificar los $m$ como porcentaje de $n$.

Answer 1

El proceso que se describe genera una distribución multinomial en el set $\{1,\ldots,n\}$. Deje $p = <p_1, \ldots, p_n>$ describir la distribución de probabilidad para cada sorteo, así que para $i=1,\ldots,n$, $p_i$ es la probabilidad de sacar un $i$, $p_i \geq 0$ todos los $i$$\sum p_i = 1$. Deje $X_i$ ser el número de veces que $i$ se dibuja. Entonces el vector aleatorio $X = <X_1, \ldots, X_n >$ tiene una distribución multinomial con parámetros de $m$$p$. La probabilidad de que $X$ toma un determinado valor de $<x_1, \ldots, x_n>$ está dado por

$\Pr[X = x_1, \ldots, x_n>]=\frac{m!}{x_1!\cdots x_n!} p_1^{x_1} \cdots p_n^{x_n}$.

El uso de esta expresión, se podría calcular el orden de las estadísticas de la distribución multinomial. El valor de la más frecuentemente elegido el número es llamado el primer fin de estadística de $X$.

Yo no estoy familiarizado con las propiedades de la distribución de la primera orden de estadística de multinomial variable aleatoria. Sin embargo, creo que este artículo de la Wikipedia puede dar la orientación que necesita para calcular la distribución de la primera orden de la estadística, lo que permite que usted investigue usted mismo.

Answer 2

Se puede calcular la probabilidad de $p(k)$ que un número en particular fue elegido exactamente $k$ veces: $$p(k)={m\choose k}\frac{(n-1)^{(m-k)}}{n^m}.$$

A partir de esto, se puede calcular la esperada recuento de los números que se producen exactamente $k$ veces $n~p(k)$.

Al $n$ es grande y $n p(k)$ es pequeño, entonces los eventos que los números particulares ocurrir exactamente $k$ veces están cerca de independiente. Así, la distribución de la cuenta de los acontecimientos que se producen exactamente $k$ veces está cerca de Poisson. La varianza es un poco más pequeño, similar a una distribución hipergeométrica.

Esto le permite aproximar la probabilidad de que haya al menos un valor con multiplicidad de, al menos,$k$. La suma de estas probabilidades es el valor esperado del número más alto. Algunos cálculos exactos son posibles para las pequeñas $k$ pero las expresiones son cada vez más complicado como $k$ aumenta al $n \gg k$.

La comprensión de esta distribución no es necesario resolver el problema que usted dice motivado el estudio de esta distribución. La probabilidad de que la primera $m$ sorteos son diferentes de las $m+1$st dibujar es simplemente

$$\bigg(\frac{n-1}{n}\bigg)^m .$$