Son casi todos los $k$-tuplas de vectores de alta el espacio tridimensional casi ortogonal?

Question

Me gustaría saber, en altas dimensiones, si usted escoge $k$ vectores (no necesariamente distintos) son propensos a ser $\textit{almost}$ ortogonal. Hago esta precisa a continuación, pero también estoy abierto a otros interpretación de la pregunta.

Ya que nosotros sólo nos preocupamos de ortogonalidad, podemos asumir que los vectores son vectores unitarios. Por lo tanto quiero considerar un conjunto $\textbf{V}=\{x_1,...,x_k\}\subset S^n$ donde $S^n$ es la unidad de la esfera. Así, podemos ver $\textbf{V}\in \underbrace{S^n\times\cdots\times S^n}_{k-times}=\mathcal{S}_{n,k}$. Deje $\mathcal{O}\subset\mathcal{S}_{n,k}$ denota el subconjunto de $k$-tuplas de vectores ortogonales. Deje $\mathcal{U}_\epsilon=\{x\in\mathcal{S}_{n,k} : d(x,\mathcal{O}) <\epsilon\}$ $\epsilon$ barrio de $\mathcal{O}$ $\mathcal{S}_{n,k}$ (usando, por ejemplo, el $l^2$ producto métrica, creo que eso no importa). Deje $\mu$ ser obvio probabilidad de producto medida en $\mathcal{S}_{n,k}$. Mi pregunta es entonces:

Es cierto que $$\forall \epsilon > 0\textrm{ and } \forall k\textrm{ }\lim_{n\rightarrow\infty}\mu(\mathcal{U}_\epsilon) = 1$$

Si no, ¿qué podemos decir acerca de este límite?

Answer 1

Vamos a escribir $P:= \mu$ (para obtener más probabilística de la notación) y vamos a mostrar que el $\lim_{n \to \infty} P(U_{\epsilon}) = 1$.

Lema 1: Para todos los $\epsilon>0$ existe alguna $\delta>0$ que si $(x^1,...,x^k) \in \prod_1^k S^n$ $\sum_{i<j} |\langle x^i,x^j \rangle|< \delta$ implica $d(x, \mathcal O)<\epsilon$.

Prueba: Esta es una consecuencia de las bacterias Gram-Schmidt orthogonalization proceso. En concreto, se definen $u^1:=x^1$,$u^2:=x^2-\frac{\langle x^2,u^1\rangle}{|u^1|^2} u^1$,$u^3=x^3 - \frac{\langle x^3,u^2\rangle}{|u^2|^2} u^2- \frac{\langle x^3, u^1 \rangle}{|u^1|^2} u^1$, y así sucesivamente. A continuación, vamos a $e^i:=u^i/|u^i|$, por lo que el $e^i$ forma un ortonormales conjunto que se construye a partir de la original $x^i$ mediante fórmulas que solo depende de los valores de la interna de los productos de $\langle x^i,x^j \rangle$. Por un cuidadoso seguimiento y el uso de la inducción, uno puede mostrar que $|x^j - u^j|$ (y por lo tanto $|x^j-e^j|$) puede hacerse arbitrariamente pequeña, haciendo que el $|\langle x^i,x^j \rangle|$ muy pequeño. $\Box$

Lema 2: Si $U,V$ son independientes y distribuidos de manera uniforme en $S^{n-1}$ $P(|\langle U, V \rangle|>\epsilon) \leq \frac{1}{n\epsilon^2}$

Prueba: Por el condicionamiento de a $V$ y el uso de la independencia podemos escribir $$P(|\langle U, V \rangle|>\epsilon) = \Bbb E\bigg[ P\big(|\langle U, V \rangle|>\epsilon \;\big| \;V\big)\bigg] = \int_{S^n} P(|\langle U, v \rangle|>\epsilon)\;\sigma(dv) = P(|\langle U, e_1 \rangle|>\epsilon)$$ where $\sigma$ is the uniform measure on $S^n$, and $e_1=(1,0,...,0)$. The final equality follows by rotational invariance of $\sigma$. Writing $U=(U_1,...,U_n)$ we see that the $U_j$ are identically distributed and $\sum U_j^2=1$. Thus $1 = E[\sum U_j^2] = nE[U_1^2]$, so that $E[U_1^2]=1/n$. Consequently, $$P(|\langle U, e_1 \rangle|>\epsilon) = P(|U_1|>\epsilon) \leq \frac{E[U_1^2]}{\epsilon^2} = \frac{1}{n\epsilon^2}$$ At the end we have used Chebyshev's inequality with the second moment. $\Caja$

La prueba de la reclamación original: Mediante la combinación de los dos lemas, vemos que $$P(U_{\epsilon}^c) = P\big( d(\{X^1,...,X^k\}, \mathcal O)>\epsilon\big) \leq P \bigg( \sum_{i<j} |\langle X^i,X^j \rangle |> \delta \bigg) $$$$\leq \sum_{i<j} P\bigg(|\langle X^i,X^j \rangle| > \frac{\delta}{k(k-1)}\bigg) \leq\frac{k^3(k-1)^3}{n \delta^2} \stackrel{n\to \infty}{\longrightarrow} 0$$

Observaciones: es esencial que la $k$ es fijo aquí (aunque la última línea muestra que $k$ es permitido a depender de $n$, mientras que crece lentamente suficiente). También tenga en cuenta que sólo se utiliza pares de la independencia en este argumento (completo mutua independencia de que no era necesario).

Answer 2

Es cierto, y puede ser visto como una consecuencia de la concentración de la medida en la esfera.

Deje $P$ ser el uniforme de probabilidad, medida en $\mathbb S^{n}$. Dado un subconjunto $A\subset \mathbb S^n$, llame a $A_t:=\{y\in\mathbb S^n:dist(y,A)<t\}$ $t$- el barrio. Entonces:

La concentración de la medida: Si $P(A)\geq\frac12$,$P(A_t^c)\leq 2e^{-nt^2/64}$. (los específicos constantes no son importantes aquí)

Aplicar esto a dos complementarios emispheres para obtener que para cualquier $\nu\in\mathbb S^n$ tenemos $P(|x\cdot \nu|\geq t)\leq 4e^{-nt^2/64}$, es decir, la medida se concentra cerca de cualquier ecuador cuando la dimensión aumenta.

En particular, se sigue inmediatamente que el resultado que se pide es cierto si $k=2$: una vez que hayas elegido el primer vector $x_1$, la probabilidad de que el segundo que usted elija será cerca de la hyperplane $x_1^\perp$ $1$ $n\to\infty$ (por la rotación de la invariancia de la medida en la esfera no importa que se concreta la $x_1$ eligió en el primer paso).

Para demostrarlo general $k$ el uso de la inducción. Voy a esbozar un argumento. El caso de $k=2$ (o $k=1$ si quieres) es el caso base y ha demostrado. Supongamos ahora que la afirmación es verdadera para $k$. Con probabilidad cercana a $1$ primera $k$ vectores $\epsilon$-ortogonal. Mover uno por uno hasta que $x_i$ está cerca de a$e_i$, $i^{th}$ estándar de la base de la unidad de vectores (por la rotación de la invariancia podemos calcular las probabilidades en esta nueva posición). A partir de la concentración de medir $$ P(\{|x\cdot e_1|\geq t\}\cup \ldots\cup\{|x\cdot e_k|\geq t\})\leq 4ke^{-nt^2/64}$$ Por lo tanto, con una probabilidad cercana a $1$ $(k+1)^{th}$ vector tiene una pequeña escalar productos con la anterior $x_i$'s. Esto implica que, con una probabilidad cercana a $1$ la familia es $\epsilon$-ortogonal.