Probabilidad de encontrar un suceso doblemente probable

Question

Repetición de un experimento con $n$ posibles resultados $t$ veces independientemente, donde todos los resultados menos uno tienen probabilidad $\frac{1}{n+1}$ y el otro resultado tiene la doble probabilidad $\frac{2}{n+1}$ ¿existe una buena fórmula aproximada para la probabilidad de que el resultado con la probabilidad más alta ocurra más a menudo que cualquier otro?

Para mí, $n$ suele ser de unos cientos, y $t$ se elige en función de $n$ tal que la probabilidad de que el resultado más probable se produzca con mayor frecuencia esté comprendida entre el 10% y el 99,999%.

Por el momento utilizo un pequeño programa que calcula una aproximación grosera suponiendo que los recuentos de la frecuencia con la que cada resultado aparece en $t$ son independientes y aproximan los recuentos mediante la distribución de Poisson. ¿Cómo puedo mejorar esto?

EDITAR: Agradecería encarecidamente comentarios/votos sobre las dos (quizá pronto más) respuestas dadas.

EDITAR 2: Como ninguna de las dos respuestas me convence, pero como no quiero dejar que se esfume la recompensa de 100 puntos (y como nadie ha votado a favor/en contra de una de las dos respuestas), elegiré una de las respuestas. Aún así agradecería otras respuestas.

Answer 1

Partición de los resultados por frecuencia de aparición $x$ del "doble resultado", $0 \le x \le t$ . Condicionada a este número, la distribución de los restantes $t-x$ resultados es multinomial a través de $n-1$ equiprobable contenedores. Sea $p(t-x, n-1, x)$ ser la posibilidad de que ninguna papelera de $n-1$ igualmente probables recibe más de $x$ resultados. Por tanto, la probabilidad buscada es igual a

$$\sum_{x=0}^{t} \binom{t}{x}\left(\frac{2}{n+1}\right)^x \left(\frac{n-1}{n+1}\right)^{t-x} p(t-x,n-1,x).$$

En Probabilidades exactas de cola y percentiles del máximo multinomial Anirban DasGupta señala (tras corregir errores tipográficos) que $p(n,K,x)K^n/n!$ es igual al coeficiente de $\lambda^n$ en la expansión de $\left(\sum_{j=0}^{x}\lambda^j/j!\right)^K$ (utilizando su notación). Para los valores de $t$ y $n$ este coeficiente puede calcularse en unos pocos segundos como máximo (asegurándose de descartar todos los $O(\lambda^{n+1})$ términos mientras se realizan las convoluciones sucesivas necesarias para obtener el $K^{\text{th}}$ potencia). (He comprobado la sincronización y corregido las erratas reproduciendo la Tabla 4 de DasGupta, que muestra las probabilidades complementarias $1 - p(n,K,x)$ y ampliándolo a valores en los que $n$ y $K$ se cuentan por cientos).

Citando un teorema de Kolchin et al. DasGupta proporciona una aproximación para el caso computacionalmente intensivo en el que $t$ es sustancialmente mayor que $n$ . Entre el cálculo exacto y la aproximación, parece que se cubren todas las posibilidades.

Answer 2

Sólo unas palabras de explicación: En parte por curiosidad, en parte por falta de un método mejor y más teórico, he enfocado el problema de una forma completamente empírica/inductiva. Soy consciente de que existe el riesgo de quedarse atascado en un callejón sin salida sin ganar mucho conocimiento, pero pensé, voy a presentar lo que tengo hasta ahora de todos modos, en caso de que sea útil para alguien.

Empezando por calcular las probabilidades exactas de $n,t\in\{1,...,8\}$ obtenemos

Debido a la distribución multinomial subyacente, al multiplicar las entradas de la tabla por $(n+1)^t$ nos deja con una tabla puramente de enteros:

Ahora encontramos que hay un polinomio en $n$ para cada columna que actúa como la función de secuencia para esa columna:

Dividiendo las funciones secuenciales por $(n+1)^t$ nos da funciones de secuencia para las probabilidades originales de la primera $t$ 's. Estos polinomios racionales pueden simplificarse descomponiéndolos en fracciones parciales y sustituyendo $x$ para $1/(n+1)$ dejándonos con:

o como tabla de coeficientes

Empezando por el $x^2$ columna hay funciones de secuencia para estos coeficientes de nuevo:

Hasta ahí llegué. Definitivamente hay patrones explotables aquí que permiten que las funciones de secuencia ocurran, pero no estoy seguro si hay una buena solución de forma cerrada para estas funciones de secuencia.

Answer 3

Estoy de acuerdo con algunos comentarios, en el sentido de que la aproximación de Poisson suena bien aquí (no es una aproximación "burda"). Debería ser asimétricamente exacta, y parece lo más razonable, ya que una solución analítica exacta parece difícil.

Como alternativa intermedia, (si realmente lo necesitas) te sugiero una corrección de primer orden a la aproximación de Poisson, de la siguiente manera (ya hice algo parecido hace tiempo, y funcionó).

Como sugiere un comentario, su modelo es (no aproximadamente sino exactamente) Poisson si condicionamos la suma. Es decir

Sea $X_t$ ( $t$ es aquí un parámetro) sea un vector de $n$ variables de Poisson independientes, la primera con $\lambda = 2t/(n+1)$ los otros con $\lambda = t/(n+1)$ . Sea $s=\sum x$ Así que $E(s)=t$ . Es evidente que $X_t$ no es equivalente a otro modelo (porque nuestro modelo se limita a $s=t$ ), pero es una buena aproximación. Además, la distribución de $X_t | s$ es equivalente a nuestro modelo. De hecho, podemos escribir

$\displaystyle P(X_t) = \sum_s P(X_t | s) P(s)$

Esto también puede escribirse para el acontecimiento en cuestión (que $x_1$ es el máximo).

Sabemos que para calcular el LHS, y $P(s)$ pero nos interesa el otro término. Nuestra aproximación de Poisson de primer orden proviene de suponer que $P(s)$ se concentra en torno a la media para que pueda asimilarse a un delta, y luego $P(X_t) \approx P(X_t | s=t)$

Para afinar la aproximación, podemos ver lo anterior como una convolución de dos funciones: nuestra incógnita $P(X_t | s)$ que suponemos suave en torno a $s=t$ y una función cuasi delta, digamos una gaussiana con varianza pequeña. Ahora, tenemos nuestra aproximación de primer orden (para variables continuas) :

$h(x) = g(x) * N(x_0,\sigma^2)$ (convolución)

$h(x_0) \approx g(x_0) + g(x_0)''\sigma^2/2$

$g(x_0) \approx h(x_0) - h''(x_0)''\sigma^2/2$

Aplicando esto a la ecuación anterior se puede llegar a una aproximación refinada a nuestra probabilidad deseada.