Problema: sean \(X_1, \ldots, X_N\) vectores aleatorios independientes e idénticamente distribuidas de dimensión \(p\) con distribución uniforme sobre la bola unitaria centrada en el origen. ¿Cuál es la mediana del mínimo de las distancias al origen de estos vectores?
Sean \(0 < r < 1\) un escalar y \(B_p\) la bola unitaria centrada en el origen. Denotamos por \(rB_p\) al conjunto \(\{ r\vec{x} \colon \vec{x} \in B_p \}\). Por la uniformidad de \(X_1, \ldots, X_N\) se sigue que las distancias \(D_i = ||X_i||_2\) tienen distribución acumulada $$ F_{D_i}(r) = \frac{Vol(rB_p)}{Vol(B_p)} = \frac{r^pVol(B_p)}{Vol(B_p)} = r^p. $$ Luego, \(D_1, \ldots, D_N\) son idénticamente distribuidas. Además, como el mapeo \(X_i \mapsto ||X_i||_2\) depende únicamente de \(X_i\), se sigue por la independencia de \(X_1, \ldots, X_N\) que \(D_1, \ldots, D_N\) también son independientes. Como nota adicional, a partir de la función de distribución acumulada \(F_{D_i}\) observamos que \(D_i \sim beta(p, 1)\).
Denotamos por \(D_{(1)}\) al estadístico de orden \(\min\{D_1, \ldots, D_N\}\). Luego, $$ \begin{aligned} F_{D_{(1)}}(r) &= P(\min\{D_1, \ldots, D_N\} \leq r) \\ &= 1 - P(\min\{D_1, \ldots, D_N\} > r) \\ &= 1 - P(D_1 > r, \ldots, D_N > r) \\ &= 1 - P(D_1 > r)\cdots P(D_N > r) \\ &= 1 - P^N(D > r) \\ &= 1 - (1 - F_D(r))^N \\ &= 1 - (1 - r^p)^N. \end{aligned} $$ Para calcular la mediana observamos que $$ F_{D_{(1)}}(r) = 1/2 \iff r = (1 - (1/2)^{1/N})^{1/p}. $$ Ahora me gustará estudiar propiedades asintóticas de \(D_{(1)}\) cuando variamos la dimensión \(p\) de los vectores aleatorios o el tamaño \(N\) de nuestra muestra. Esto nos permitirá aproximar \(\mathbb{E}D_{(1)}\). Utilizaré la notación \(\dot{\sim}\) para denotar convergencia en distribución para una sucesión de variables aleatorias.
Observemos que \(F_{D_{(1)}}(r) \to 1\) para toda \(r \in (0, 1)\) cuando \(p \to \infty\) y \(N\) es fija. De aquí se sigue que \(D_{(1)} ~\dot{\sim}~ 0\). Similarmente, \(D_{(1)} ~\dot{\sim}~ 1\) cuando \(N \to \infty\) y \(p\) es fija. ¿Obtenemos resultados más interesantes cuando ambos \(N,p \to \infty\) y se satisface cierta relación entre estos parámetros?
De \(F_{D_{(1)}}\) analizamos la función \((1-r^p)^N\). Para simplificar el análisis estudiamos el logaritmo \(N\ln(1 - r^p)\). Primero escogemos una \(x \in (0, 1)\) y luego generalizamos los resultados para toda \(r \in (0, 1)\). Por ansatz nos concentramos en los dos casos límite de \(Nx^p\).
Primer caso: \(Nx^p \to \infty\). Doy por sentado la desigualdad \(\ln(1 - x) \leq -x \) aunque no es difícil de demostrar. El mapeo \(x \mapsto x^p\) es creciente para \(p,x > 0\), luego $$ N\ln(1-x^p) \leq -Nx^p \to -\infty, $$ y entonces \((1 - x^p)^N \to e^{-\infty} = 0\). Esto implica que \(F_{D_{(1)}}(x) \to 1 - 0 = 1\).
Segundo caso: \(Nx^p \to \lambda\) para alguna \(\lambda \geq 0\). Por Taylor de \(\ln(1-x)\) alrededor del cero, tenemos $$ N\ln(1-x^p) = -Nx^p + \mathcal{O}(Nx^{2p}). $$ Por hipótesis, \(Nx^{2p} = (Nx^p) \cdot x^p \to \lambda \cdot 0\), pues \(x \in (0, 1)\). De esto se sigue que \(\mathcal{O}(Nx^{2p}) = o(1)\), y entonces $$ N\ln(1 - x^p) = -Nx^p + o(1) \to -\lambda. $$ Luego, \(F_{D_{(1)}}(x) \to 1 - e^{-\lambda}\). Cabe remarcar que \(F_{D_{(1)}}(x) \to 0\) si y solo si \(\lambda = 0\).
Ahora bien, del primer caso tenemos que si \(Nr^p \to \infty\) para toda \(r \in (0, 1)\), entonces \(D_{(1)} ~\dot{\sim}~ 0\), pues $$ F_{D_{(1)}}(r) \to \begin{cases} 0 & r < 0, \\ 1 & r \geq 0. \end{cases} $$ De esto se sigue que \(\mathbb{E}D_{(1)} \to 0\).
Supongamos que nos encontramos en el segundo caso junto con el supuesto de que \(\lambda > 0\). Sea \(r \in (0, x)\), por lo que existe \(k > 1\) tal que \(x = k\cdot r\). Luego, $$ Nr^p = \frac{Nx^p}{k^p} \to \frac{\lambda}{\infty} = 0, $$ y entonces \(F_{D_{(1)}}(r) \to 0\) para \(r < x\). Utilizando el mismo razonamiento junto con el caso anterior, encontramos que \(F_{D_{(1)}}(r) \to 1\) para \(r > x\). Es decir, $$ F_{D_{(1)}}(r) = \begin{cases} 0 & r < x, \\ 1 - e^{-\lambda} & r = x, \\ 1 & r > x, \end{cases} \stackrel{c.s.}{=} \begin{cases} 0 & r < x, \\ 1 & r \geq x, \end{cases} $$ donde el símbolo \(\stackrel{c.s.}{=}\) significa igualdad casi segura. De esta manera encontramos que \(D_{(1)} ~\dot{\sim}~ x\) y por lo tanto \(\mathbb{E}D_{(1)} \to x\). Recordando el significado de las variables aleatorias, podemos asegurar que todas las distancias son mayores a \(x\); existe un espacio vacío entre el origen y la bola \(xB_p\). La tasa con la que aumentamos nuestro tamaño de muestra \(N\) no es suficiente para llenar el espacio vacío generado al agregar dimensiones adicionales. Esto es conocido como la maldición de la dimensionalidad.
No nos dejemos impresionar tan fácilmente. La maldición pierde impacto a medida que \(x\) se acerca a 0, pues el espacio vacío que fallamos en llenar es pequeño y no hay nada de que preocuparnos. Si \(x \approx 1\) entonces todos los vectores \(X_1, \ldots, X_N\) se encuentran cerca de la frontera de \(B_p\). Observemos de la convergencia \(Nx^p \to \lambda\) con \(\lambda > 0\) que \(N = \Theta(x^{-p})\). Supongamos, por simpleza, que \(N(x) = x^{-p}\). Luego el costo de disminuir \(x\) marginalmente es \(|N'(x) / N(x)| = p/x\) veces mayor que el costo actual, lo cual tiende a infinito cuando \(x\) tiende a cero. ¿Será esto una manera efectiva de cobrar la adquisición de nuevas observaciones de manera que se preserve la densidad?
Para el último caso donde \(Nx^p \to 0\) observemos que si \(r \in (0, x)\), entonces existe \(k > 1\) tal que \(x = k\cdot r\) y, por lo tanto, $$ Nr^p = \frac{Nx^p}{k^p} \to \frac{0}{\infty} = 0. $$ A diferencia del punto anterior, no podemos asegurar que \(Nr^p \to \infty\) cuando \(r > x\), pues nos encontramos con una forma indeterminada \(0/0\), la cual puede tomar cualquier valor en \(\mathbb{R}^+\cup\{\infty\}\). Como no podemos hacer nada al respecto, supongamos que \(Nr^p \to 0\) para todo \(r \in (0, 1)\). Luego, por el segundo caso encontramos que \(F_{D_{(1)}}(r) \to 0\) para todo \(r \in (0, 1)\) y por lo tanto \(D_{(1)} ~\dot{\sim}~ 1\), lo cual implica que \(\mathbb{E}D_{(1)} \to 1\). En realidad, esto es lo que comúnmente se conoce como la maldición de la dimensionalidad, pues el interior de \(B_p\) es vacío, y todas las observaciones \(X_1, \ldots, X_N\) se encuentran sobre la frontera de esta bola. La densidad de nuestra muestra tiende a cero a medida que aumenta la dimensión.
El teorema 1.2.16 de esta tesis indica que la red \(\mathbb{Z}^n\) se puede descomponer como la suma directa de las dos subredes \(\Lambda_p\) y \(\Lambda_h\) definidas como $$ \begin{align*} \Lambda_p &= \{ k\vec{\nu} \colon k \in \mathbb{Z} \}, \\ \Lambda_h &= \{ M\vec{t} \colon \vec{t} \in \mathbb{Z}^{n-1} \}, \end{align*} $$ donde \(M\) y \(\vec{\nu}\) son calculados a partir de un vector coprimo \(\vec{q}\). Lo interesante de estas dos subredes es que satisfacen \(\vec{q}^T\Lambda_p = k\) y \(\vec{q}^T\Lambda_h = 0\). Es decir, \(\Lambda_h\) es la subred que contiene todas las soluciones a la ecuación lineal diofantina homogénea \(\vec{q}^T\vec{x} = 0\). Similarmente, \(\Lambda_p\) es la subred de soluciones particulares de la ecuación lineal diofantina \(\vec{q}^T\vec{x} = k\) para cada \(k \in \mathbb{Z}\). Para cada vector coprimo \(\vec{q} \in \mathbb{Z}^n\) obtendremos una descomposición de \(\mathbb{Z}^n\) del estilo anterior. Una pregunta que intenta --de manera incompleta, debo añadir-- resolver la tesis es la siguiente: si tenemos dos vectores coprimos \(\vec{q}, \tilde{\vec{q}}\) junto con las subredes \(\Lambda_p, \Lambda_h\) y \(\tilde{\Lambda}_p, \tilde{\Lambda}_h\) inducidas por ellos, ¿cómo se relacionan \(\Lambda_p\) y \(\tilde{\Lambda}_p\), o cómo se relacionan \(\Lambda_h\) y \(\tilde{\Lambda}_h\)? /tmp/data.bkp muestra en el teorema 1.2.22 que estas subredes son isomorfas siempre que ciertas proyecciones de \(\vec{q}\) y de \(\tilde{\vec{q}}\) pertenezcan a la misma órbita. En pocas palabras, estas subredes son isomorfas siempre que exista una permutación entre las entradas no nulas de estos vectores coprimos. En este pequeño escrito mostraré que, en realidad, el resultado es mucho más general, pues esto es cierto para cualesquiera dos vectores coprimos con el mismo número de entradas no nulas, independientemente de cualesquiera otras propiedades que pudiesen o no compartir. Esto implica que solamente existe, bajo isomorfismo, una única descomposición de \(\mathbb{Z}^n\) en subredes de este estilo. En lo que sigue a continuación supondré, sin pérdida de generalidad, que los vectores coprimos no tienen entradas nulas. Ahora quiero precisar el concepto de isomorfismo de redes, puesto que el autor de la tesis no lo dejó suficientemente claro. Definición: Sean \(V, W\) dos espacios vectoriales y sea \(T \colon V \to W\) una transformación lineal invertible tal que su matriz asociada es unimodular. Sean \(\Lambda_V\) y \(\Lambda_W\) dos redes de \(V, W\) respectivamente y supongamos que la imagen de \(T \big|_{\Lambda_V}\) es \(\Lambda_W\). Entonces decimos que estas redes son isomorfas y escribimos \(\Lambda_V \cong \Lambda_W\). Sea \(\vec{q} \in \mathbb{Z}^n\) un vector coprimo y consideremos la matriz \(U = [\vec{\nu} \mid M]\). Por el teorema 1.2.16 sabemos que las columnas de esta matriz forman una base de la red \(\mathbb{Z}^n = \Lambda_p \oplus \Lambda_h\). Además, por el corolario 1.2.17, \(U\) es unimodular. Vista como una transformación lineal, tenemos entonces que \(U\colon \mathbb{Z}^n \to \Lambda_p \oplus \Lambda_h\) es un isomorfismo entre estas dos redes. Similarmente, para otro vector coprimo \(\tilde{\vec{q}} \in \mathbb{Z}^n\) obtenemos un isomorfismo \(\tilde{U} \colon \mathbb{Z}^n \to \tilde{\Lambda}_p \oplus \tilde{\Lambda_h}\) de redes. Ahora bien, consideremos la transformación lineal $$ U\tilde{U}^{-1} \colon \tilde{\Lambda}_p \oplus \tilde{\Lambda}_h \to \Lambda_p \oplus \Lambda_h. $$ No es difícil ver que \(U\tilde{U}^{-1}\) es invertible y unimodular. Por cómo están construidas las matrices \(U, \tilde{U}\) obtenemos $$ \begin{align*} \tilde{\vec{\nu}} &\overset{\tilde{U}^{-1}}{\longmapsto} \vec{e}_1 \overset{U}{\longmapsto} \vec{\nu}, \\ \tilde{M} &\overset{\tilde{U}^{-1}}{\longmapsto} [\vec{e}_2 \mid \cdots \mid \vec{e}_n] \overset{U}{\longmapsto} M, \end{align*} $$ Como \(\tilde{\vec{\nu}}\) y \(\vec{\nu}\) son bases respectivas de \(\tilde{\Lambda}_p\) y \(\Lambda_p\), encontramos que la imagen de \(U\tilde{U}^{-1}\big|_{\tilde{\Lambda}_p}\) es \(\Lambda_p\). Luego, \(\tilde{\Lambda}_p \cong \Lambda_p\). Por un razonamiento similar, obtenemos \(\tilde{\Lambda}_h \cong \Lambda_h\). Esta fue la demostración de la generalización del lema 1.2.21 de la tesis, la cual enuncio acá a modo de resumen. Lema 1.2.21 generalizado: Sean \(\vec{q}, \tilde{\vec{q}} \in \mathbb{Z}^n\) vectores coprimos y sean \(\Lambda_p, \tilde{\Lambda}_p, \Lambda_h, \tilde{\Lambda}_h\) las subredes inducidas por ellos y que satisfacen \(\Lambda_p \oplus \Lambda_h = \mathbb{Z}^{n} = \tilde{\Lambda}_p \oplus \tilde{\Lambda}_h\). Entonces \(\Lambda_p \cong \tilde{\Lambda}_p\) y \(\Lambda_h \cong \tilde{\Lambda}_h\). La generalización del teorema 1.2.22 es inmediata, por lo que no la enuncio acá. Ahora bien, ¿cómo justificamos la decisión de /tmp/data.bkp de considerar solamente permutaciones de vectores coprimos? Francamente no me he atrevido a preguntarle debido a que se molestará por las enmendaduras que de su tesis he tenido que realizar. Lo que está escrito a continuación es entonces la conversación que me gusta imaginar que tendríamos. fermín ghebre: Después de leer minuciosamente el primer capítulo de tu tesis fui capaz de generalizar un par de resultados, como lo puedes observar en este breve texto que he escrito. Con un poco de suerte será publicado en la gaceta semanal de matemáticas que organiza la marquesa de Cambremer. /tmp/data.bkp: Dispénsame un minuto en lo que ajusto este monóculo el mío y absorbo el nuevo conocimiento que seguramente has generado... Jiji, cierto es todo lo que has escrito. Lamento decirte que en una conversación previa que tuve con la princesa de Laumer realizó ella las mismas observaciones... e incluso antes que ella tropecé moi-même con aquellos hallazgos. fermín ghebre: Si es cierto lo que estás diciendo, ¿por qué no postular el lema 1.2.21 en su generalidad? ¿Por qué dar falsas esperanzas al lector que tan ciertamente interesado está con lo que tu pluma deja impreso? /tmp/data.bkp: Me encantaría darte una respuesta que satisfaga tu sed de curiosidad y lamento la excusa que voy a decirte: por economía de tiempo y espacio. Verás, al caballero Legrandin que tan bien conoces no le agradó en lo más mínimo toda esa sección. Ambos sabemos que toda cuestión algebraica no entra en su paladar, aparentemente por ser anteriores al imperio; que sus gustos recaen siempre en las nuevas tendencias y no se permite apreciar la belleza de tiempos pasados. Sería una lástima que tu escrito no sea publicado en la gaceta de la marquesa, así que, si me lo permites, puedo añadir algunas proposiciones que unirán tus resultados con los míos. Verás, para pasar de una red \(\tilde{\Lambda}_p\) a la otra \(\Lambda_p\) es necesario invertir la matriz \(\tilde{U}^{-1}\), lo cual es un trabajo de orden cúbico --claro, si bien recuerdo las lecciones tan finas de aquel compositor Vinteuil. Mi enfoque en las permutaciones es consecuencia del hecho que estas forman un subgrupo del grupo de matrices ortogonales sobre los enteros, ¡así reduciendo el trabajo de invertir la matriz a solo transponerla! Como evidencia, y no estoy sugiriendo que no me creas, te muestro esta nota que tan convenientemente he encontrado en el bolsillo de mi pantalón: Definición: Decimos que una matriz invertible \(X\) es ortogonal si \(X^{-1} = X^T\). Denotamos por \(O_n(\mathbb{Z})\) al grupo de matrices ortogonales sobre los enteros. Proposición: Es cierto que $$ O_n(\mathbb{Z}) = \{ [\pm \vec{e}_{\sigma(1)} \mid \cdots \mid \pm \vec{e}_{\sigma(n)}] \colon \sigma \in S_n \}, $$ donde \(S_n\) es el grupo de permutaciones en \(n\) letras. Demostración: La contención de derecha a izquierda es trivial, por lo que no nos molestamos en mostrar su veracidad. Sea \(X \in O_n(\mathbb{Z})\). Del hecho que \(X^TX = I_n\) encontramos que \(||X_i||^2 = 1\) y \(X_i^TX_j = 0\) para \(i \neq j\), donde \(X_i\) denota la \(i\)-ésima columna de \(X\). Puesto que las entradas son enteras, de la primera observación encontramos que solo una entrada, digamos la \(k_i\)-ésima entrada, es \(\pm 1\), mientras que las otras son cero, por lo que \(X_i = \pm e_{k_i}\). De la segunda observación encontramos que \(X_i\) y \(X_j\) deben ser vectores canónicos distintos. Si definimos la permutación \(\sigma \in S_n\) a partir de \(i \mapsto k_i\), encontramos que \(X = [\pm e_{\sigma(1)} \mid \cdots \mid \pm e_{\sigma(n)}]\) y entonces la contención de izquierda a derecha también es verdadera. fermín ghebre: Ya veo, al enfocarte solo en \(O_n(\mathbb{Z})\) puedes construir más fácilmente la transformación lineal que testifica los isomorfismos de redes \(\Lambda_p \cong \tilde{\Lambda}_p\) y \(\Lambda_h \cong \tilde{\Lambda}_h\), pues si los vectores coprimos que inducen estas descomposiciones de \(\mathbb{Z}^n\) son uno la permutación del otro, entonces \(U\tilde{U}^{-1} = U\tilde{U}^T\). ¡Rikis! Empero, tu tesis se enfoca exclusivamente en matrices de permutación sin signos, por lo que el tamaño de las órbitas pasan de ser \(2^nn!\) a solamente \(n!\). /tmp/data.bkp: Razones de sobra tengo para justificar esa otra reducción al subgrupo de permutaciones, y me encantaría discutirlas contigo en n'importe quelle autre fête organizada ora por los Guermantes, ora por los Verdurin. Temo que en en estos momentos no puedo, puesto que Ya...Odette seguramente está esperando ansiosa mi llegada a su casa desde hace varias horas. Adieu mon ami ! Que Dieu te bénisse ! fermín ghebre (susurrándose a sí mismo): ¿Odette? ¿de Crécy? La última vez que la visité fue en Niza y su nombre estaba en boca de todos. Claro, fueron tiempos anteriores a Joyce cuando todavía arrancábame el corazón leyendo a Proust.