Consideremos un conjunto de variables aleatorias iid $x_1, \ldots x_n$ distribuido uniformemente en $[0, 1]$ . Para cada $S \subset [n]$ con $1 \leq |S| = k < n$ tomar $\sigma_S = \sum_{i \in S}x_i$ . Obviamente $\sigma_S$ son distintos con probabilidad 1. ¿Cuál es la expectativa de $\Delta = \min_{|S| = |S'| = k, S \neq S'} |\sigma_S - \sigma_{S'}|$ ¿al menos asintóticamente? ¿Podemos decir algo sobre la concentración de $\Delta$ ?
Respuesta
¿Demasiados anuncios?
Iosif Pinelis
Puntos
24742
He aquí algunas heurísticas, que deberían poder reforzarse hasta llegar a una respuesta completamente rigurosa.
Tenga en cuenta que $\sigma_S$ es la suma de la muestra de tamaño $k$ tomada con reemplazo de la distribución empírica (aleatoria) correspondiente a la muestra iid $x_1, \ldots x_n$ de la distribución uniforme en $[0, 1]$ . Para los grandes $n$ esta distribución empírica se aproxima a la distribución uniforme en $[0, 1]$ . Además, si $k=o(\sqrt n)$ (lo que suponemos), entonces el muestreo con reemplazo difiere poco del muestreo sin reemplazo. Así, la distribución de $\sigma_S$ (con $S$ se considera un subconjunto aleatorio de $[n]$ de tamaño $k$ ) se acerca a la distribución de la suma de $k$ variables aleatorias (v.r.) iid distribuidas uniformemente en $[0, 1]$ que, por el teorema central del límite, es a su vez cercano a $N(k/2,k/12)$ si $k$ es grande, lo que suponemos también.
Así, la distribución del vector $(\sigma_S\colon S \subset [n],|S| = k)$ se acerca a la del vector $(X_1,\dots,X_N)$ de $N:=\binom nk$ iid r.v. cada uno con una distribución cercana a $N(k/2,k/12)$ .
Dejemos que $U_j:=F(X_j)$ , donde $F$ es la fdc de $N(k/2,k/12)$ para que el $U_j$ se distribuyen uniformemente de forma aproximadamente iid en $[0, 1]$
y por tanto el vector aleatorio $(U_{(j)}-U_{(j-1)}\colon j=2,\dots,N)$ de las separaciones entre las estadísticas de orden consecutivas basadas en la $U_j$ es aproximadamente igual en la distribución $(V_2,\dots,V_N)/(V_1+\dots+V_{N+1})$ , donde el $V_j$ son v.r. iid, cada uno con la distribución exponencial estándar. Por la ley de los grandes números, $V_1+\dots+V_{N+1}\sim N$ . Así que, $(U_{(j)}-U_{(j-1)}\colon j=2,\dots,N)$ se acerca en su distribución a $(V_2,\dots,V_N)/N$ .
Por otro lado, el mínimo de $|X_i-X_j|$ sobre todo $i\ne j$ es igual a $\min\{X_{(j)}-X_{(j-1)}\colon j=2,\dots,N\}$ , donde el $X_{(j)}$ son las estadísticas de pedidos basadas en $X_1,\dots,X_N$ . Ahora escribe \begin{equation*} U_{(j)}-U_{(j-1)}=F(X_{(j)})-F(X_{(j-1)}) \sim(X_{(j)}-X_{(j-1)})F'(X_{(j)}) \end{equation*} \begin{equation*} =(X_{(j)}-X_{(j-1)})F'(F^{-1}(U_{(j)})) \sim(X_{(j)}-X_{(j-1)})F'(F^{-1}(j/N)), \end{equation*} por lo que, con $\tau:=F'\circ F^{-1}$ ,
\begin{equation*} X_{(j)}-X_{(j-1)}\sim\frac{U_{(j)}-U_{(j-1)}}{\tau(j/N)} \sim\frac1{\tau(j/N)}\frac{V_j}{V_1+\dots+V_{N+1}}\sim\frac{V_j}{N\tau(j/N)}. \end{equation*} Siguiente, \begin{equation*} E\min\{\frac{V_2}{\tau(2/N)},\dots,\frac{V_N}{\tau(N/N)}\} =\int_0^\infty \prod_{j=2}^N P(V_2>\tau(j/N)x)dx \end{equation*} \begin{equation*} =\int_0^\infty \exp\Big(-\sum_{j=2}^N \tau(j/N)x\Big)dx =\frac1{\sum_{j=2}^N \tau(j/N)}\sim \frac1{N\int_0^1\tau(u)du}=\frac{\sqrt{\pi k/3}}N, \end{equation*} utilizando la sustitución $u=F(z)$ en la integral $\int_0^1\tau(u)du$ .
Por lo tanto, debería seguirse que \begin{equation*} E\min\{X_{(j)}-X_{(j-1)}\colon j=2,\dots,N\} \sim \frac1N\,E\min\{\frac{V_2}{\tau(2/N)},\dots,\frac{V_N}{\tau(N/N)}\} \sim\frac{\sqrt{\pi k/3}}{N^2} \end{equation*} y por lo tanto \begin{equation*} E\min_{|S| = |S'| = k, S \neq S'} |\sigma_S - \sigma_{S'}|\}\sim \sqrt{\pi k/3}\Big/\binom nk^2. \end{equation*}
