Pequeña o-notación en probabilidad [prueba de Raab 1998].

Question

Necesito una aclaración sobre la notación utilizada en el teorema principal de la prueba "Balls into Bins" - A Simple and Tight Analysis

El teorema afirma que:

Sea $M$ sea la variable aleatoria que cuenta el número máximo de bolas en cualquier contenedor, si lanzamos $m$ bolas de forma independiente y uniforme al azar en $n$ contenedores. A continuación, $Pr[M > k_\alpha] = o(1)$ si $\alpha > 1$ y $Pr[M > k_\alpha] = 1 - o(1)$ si $ 0 < \alpha < 1 $ donde

$k_\alpha = \frac{m}{n} + \sqrt{\frac{2m \log_n}{n}(1 - \frac{1}{\alpha}\frac{log^{(2)} n}{2 \log n})}$ si $ m >> n (log n)^3$

He omitido el resultado para otros casos de m porque quiero preguntar el significado de las notaciones. Yo vengo de un fondo de Ciencias de la Computación. No entiendo la interpretación del uso de la notación small-o en probabilidad: $Pr[M > k_\alpha] = o(1)$ .

También revisé rápidamente la wikipedia https://en.wikipedia.org/wiki/Big_O_in_probability_notation . Pero no sirve de nada. Se trata de un conjunto de variables aleatorias. ¿Es el "Balls into Bins" hablando de un conjunto cuando dijo $M > k_\alpha$ ?

Gracias

Answer 1

Tal vez pueda ayudar a arrojar algo de luz.

La notación Little-o se utiliza para comparar el comportamiento de dos funciones $f$ , $g$ cuando las entradas son arbitrariamente grandes: no es más que una herramienta utilizada en el estudio de la asintótica.

En un entorno no probabalístico lo que tenemos es $$ f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)}=0 $$

que describe una situación en la que la función $f$ crece mucho más despacio que la función $g$ a medida que las entradas se acercan al infinito. Un ejemplo: $x = o(x^2)$ desde $\frac{x}{x^2} \to 0$ como $x \to \infty$ .

En cuanto a su caso concreto: desgraciadamente su notación es un poco chapucera. Lo que se supone en el contexto del problema es que dejamos que el número de bins $n \to \infty$ .

Defina $M_n$ como una variable aleatoria que representa el número máximo de bolas en cualquier recipiente cuando tenemos exactamente $n$ contenedores. En el caso de que $\alpha>1$ y hay MUCHAS más bolas que contenedores, es decir. $m >> n (\log n) ^3$ lo que tenemos es:

$$P(M_n > k_{\alpha}) = o(1)$$ lo que significa que $$\lim_{n\to \infty} P(M_n > k_{\alpha}) =0$$ por lo que la probabilidad de que encontremos un contenedor con más de $k_{\alpha}$ bolas a medida que el número de bins se acerca a infinito.

El caso en que $\alpha <1$ y $m >> n (\log n )^3$ puede reescribirse como $$1-P(M_n>k_{\alpha}) = P(M_n \leq k_{\alpha}) = o(1)$$

lo que significa que casi con toda seguridad encontraremos una papelera con al menos $k_{\alpha}$ si tenemos un número arbitrario de contenedores.

Su interpretación depende entonces de $\alpha$ y la definición de $k_{\alpha}$ . Considere que el primer término $\frac{m}{n}$ en $k_{\alpha}$ representa el número esperado de bolas en un contenedor dado, entonces interpreta el negocio de la raíz cuadrada como una función de $\alpha$ .