Expectativa del máximo de variables aleatorias geométricas i.i.d.

Question

Dado $n$ variables aleatorias geométricas independientes $X_n$ , cada uno con un parámetro de probabilidad $p$ (y por lo tanto la expectativa $E\left(X_n\right) = \frac{1}{p}$ ), lo que es $$E_n = E\left(\max_{i \in 1 .. n}X_n\right)$$

---

En cambio, si consideramos un análogo en tiempo continuo, por ejemplo, las variables aleatorias exponenciales $Y_n$ con el parámetro de velocidad $\lambda$ esto es simple: $$E\left(\max_{i \in 1 .. n}Y_n\right) = \sum_{i=1}^n\frac{1}{i\lambda}$$

(Creo que esto es correcto... es el tiempo de la primera más el tiempo de la segunda más... más el tiempo de la última).

Sin embargo, no puedo encontrar algo similar para el caso de tiempo discreto.

---

Lo que yo tienen hecho es construir una cadena de Markov que modele el número de $X_n$ que aún no han "pegado". (es decir, en cada intervalo de tiempo, realizar un ensayo binomial sobre el número de $X_n$ restante para ver cuál "acertó", y luego pasar al número que no "acertó"). Esto da $$E_n = 1 + \sum_{i=0}^n \left(\begin{matrix}n\\i\end{matrix}\right)p^{n-i}(1-p)^iE_i$$ que da la respuesta correcta, pero es una pesadilla de recursión para calcular. Espero algo de forma más corta.

Answer 1

No existe una expresión agradable y de forma cerrada para el máximo esperado de las variables aleatorias geométricas IID. Sin embargo, el máximo esperado de las correspondientes variables aleatorias exponenciales IID resulta ser una muy buena aproximación. Más concretamente, tenemos los límites duros

$$\frac{1}{\lambda} H_n \leq E_n \leq 1 + \frac{1}{\lambda} H_n,$$ y la aproximación cercana $$E_n \approx \frac{1}{2} + \frac{1}{\lambda} H_n,$$ donde $H_n$ es el $n$ número armónico $H_n = \sum_{k=1}^n \frac{1}{k}$ y $\lambda = -\log (1-p)$ el parámetro de la distribución exponencial correspondiente.

Aquí está la derivación. Sea $q = 1-p$ . Utiliza la expresión de Did con el hecho de que si $X$ es geométrico con el parámetro $p$ entonces $P(X \leq k) = 1-q^k$ para conseguir

$$E_n = \sum_{k=0}^{\infty} (1 - (1-q^k)^n).$$

Viendo esta suma infinita como aproximaciones de la suma de Riemann a la derecha y a la izquierda de la integral correspondiente obtenemos

$$\int_0^{\infty} (1 - (1 - q^x)^n) dx \leq E_n \leq 1 + \int_0^{\infty} (1 - (1 - q^x)^n) dx.$$

El análisis se reduce ahora a comprender el comportamiento de la integral. Con el interruptor de la variable $u = 1 - q^x$ tenemos

$$\int_0^{\infty} (1 - (1 - q^x)^n) dx = -\frac{1}{\log q} \int_0^1 \frac{1 - u^n}{1-u} du = -\frac{1}{\log q} \int_0^1 \left(1 + u + \cdots + u^{n-1}\right) du $$ $$= -\frac{1}{\log q} \left(1 + \frac{1}{2} + \cdots + \frac{1}{n}\right) = -\frac{1}{\log q} H_n,$$ que es exactamente la expresión que el PO tiene arriba para el máximo esperado de $n$ variables aleatorias exponenciales IID correspondientes, con $\lambda = - \log q$ .

Esto demuestra los límites duros, pero ¿qué pasa con la aproximación más precisa? La forma más fácil de comprobarlo es probablemente utilizar el Fórmula de suma de Euler-Maclaurin para aproximar una suma por una integral. Hasta un término de error de primer orden, dice exactamente que

$$E_n = \sum_{k=0}^{\infty} (1 - (1-q^k)^n) \approx \int_0^{\infty} (1 - (1 - q^x)^n) dx + \frac{1}{2},$$ lo que da lugar a la aproximación $$E_n \approx -\frac{1}{\log q} H_n + \frac{1}{2},$$ con el término de error dado por $$\int_0^{\infty} n (\log q) q^x (1 - q^x)^{n-1} \left(x - \lfloor x \rfloor - \frac{1}{2}\right) dx.$$ Se puede comprobar que es bastante pequeño a no ser que $n$ también es pequeño o $q$ es extrema.

Todos estos resultados, incluyendo una justificación más rigurosa de la aproximación, la fórmula recursiva de la OP y la expresión adicional $$E_n = \sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-q^i},$$ están en el artículo de Bennett Eisenberg "On the expectation of the maximum of IID geometric random variables" ( Cartas de Estadística y Probabilidad 78 (2008) 135-143).

Answer 2

Primer principio:

Para tratar los máximos $M$ de variables aleatorias independientes, utilice en lo posible eventos de la forma $[M\leqslant x]$ .

Segundo principio:

Para calcular la expectativa de una variable aleatoria no negativa $Z$ , utilice en la medida de lo posible la función de distribución acumulativa complementaria $\mathrm P(Z\geqslant z)$ .

En el caso discreto, $\mathrm E(M)=\displaystyle\sum_{k\ge0}\mathrm P(M>k)$ El evento $[M>k]$ es el complemento de $[M\leqslant k]$ y el evento $[M\leqslant k]$ es la intersección de los eventos independientes $[X_i\leqslant k]$ cada uno de ellos con una probabilidad $F_X(k)$ . Por lo tanto, $$ \mathrm E(M)=\sum_{k\geqslant0}(1-\mathrm P(M\leqslant k))=\sum_{k\geqslant0}(1-\mathrm P(X\leqslant k)^n)=\sum_{k\geqslant0}(1-F_X(k)^n). $$ El caso continuo es aún más sencillo. Para los casos i.i.d. no negativos $X_1, X_2, \ldots, X_n$ , $$ \mathrm E(M)=\int_0^{+\infty}(1-F_X(t)^n) \, \mathrm{d}t. $$

Answer 3

$$\begin{align} P(\max Y_i=k)&=P(\max Y_i\leq k)-P(\max Y_i<k)\\\\&=F(k)^n-(F(k)-f(k))^n. \end{align}$$ Así, $$\begin{align} E(\max Y_i) &= \sum_{k=0}^{\infty} k\left[F(k)^n-(F(k)-f(k))^n\right] \\\\ &=\sum_{k=1}^{\infty}k\left[\left(1-(1-p)^k\right)^n-\left(1-(1-p)^{k-1}\right)^n\right]. \end{align}$$

Pero no es una forma cerrada.

Ver también Estadística de pedidos tanto para el caso continuo como para el discreto. La fórmula para el caso continuo aparece en el post de Shai Covo aquí .