Probabilidad cada hiperplano contiene en mayoría $m/2$ vectores

Question

Elegir $m \geq n$ vectores dibujados uniformemente de $\{-1,1\}^n$ y llamar el conjunto de vectores $X$. ¿Cuál es la probabilidad que cada cero $v \in \mathbb{R}^n$ allí hay por lo menos vectores de $m/2$ $X$ que no son ortogonales a $v$?

¿Si no es posible una probabilidad exacta, se pueden encontrar límites?

Answer 1

Voy a dar varios límites en la probabilidad de $p(m,n)$ y esbozar sus pruebas.

Nota: supongo que los vectores en $X$ son contados con "repeticiones/multiplicidades".

Reivindicación 1. $p(m,n) \leq p(m, n-1)$.

Prueba: tenga en cuenta que si $X$ satisface la condición dada $m$$n$, entonces la restricción de vectores en $X$ a la primera $n-1$ coordenadas cumple la condición para$m$$n' = n-1$. Por lo tanto $p(m,n) \leq p(m, n-1)$. No es difícil ver que la desigualdad es estricta al $p(m,n-1) > 0$. QED

Reivindicación 2. Supongamos que $X$ cumple la condición del problema. Deje $i$ $j$ ser distintos índices de$1$$n$. Entonces $$\sum_{u\in X} u_i u_j = 0$$ here, $u_i$ and $u_j$ are $i$-th and $j$-th coordinates of $u$, respectivamente.

Prueba: Supongamos lo contrario que $\sum_{u\in X} u_i u_j \neq 0$ algunos $i$$j$. Digamos que $\sum_{u\in X} u_i u_j > 0$. Tenga en cuenta que $u_i u_j \in \{\pm 1\}$ todos los $u\in \{\pm 1\}^n$. Deje $Y$ ser el conjunto de vectores $u \in X$$u_i u_j = 1$; es decir, $Y$ es el conjunto de vectores $u\in X$ tal que cualquiera de las $u_i=u_j = 1$ o $u_i = u_j = -1$. Entonces $$0 < \sum_{u\in X} u_i u_j = |Y| - (|X| - |Y|) = 2|Y| -m$$ and thus $|Y| > m/2$.

Ahora considere el $v=e_i - e_j$ donde $e_i$ $e_j$ son estándar vectores de la base. Tenga en cuenta que $\langle v, u\rangle = 0$ por cada $u\in Y$. Por lo tanto $v$ es ortogonal a más de $m/2$ vectores en $X$. Tenemos una contradicción. El caso de al $\sum_{u\in X} u_i u_j < 0$ es similar: se considerar $Y=\{u\in X: u_i u_j = -1\}$ y deje $v=e_i + e_j$.

QED

Observación. Escribir un $n\times m$ matriz $U$ formado por los vectores $u\in X$: $$U = \left(x_1 x_2 \cdots x_m\right), \text{ where } X = \{x_1, \dots, x_m\},$$ La reivindicación 2, dice que si $X$ satisface la condición de que el problema, a continuación, las filas de $U$ son mutuamente ortogonales. Por lo tanto $p(m,n)$ es superior delimitada por la probabilidad de que todas las filas de un random $n\times m$ matriz con $\pm 1$ entradas son mutuamente ortogonales.

El producto de cada una de las dos filas de la distribución binomial, ya que es la suma de $m$ independientes $\pm 1$-variables aleatorias de Bernoulli. Por lo tanto la probabilidad de que dos filas son ortogonales es $\binom{m}{m/2}/2^m \approx \sqrt{\frac{2}{\pi\,m}}$ si $m$ es incluso y $0$ lo contrario. Sabemos que si $X$ satisface la condición de que el problema, a continuación, cada dos filas son ortogonales. Si los eventos para los diferentes pares eran independientes, nos gustaría obtener una cota superior de $$\left(\binom{m}{m/2}/2^m\right)^{n(n-1)/2} \approx 1/m^{n(n-1)/4},$$ where $n(n-1)/2$ es el número de pares de filas. Pero estos eventos no son independientes. Vamos a utilizar a continuación un poco diferente de argumento.

Reivindicación 3. $$p(m,n) \leq C_n /m^{n(n-1)/4}$$ where $C_n$ depends only on $$n.

Prueba: Para $1 \leq i < j \leq n$, definir $\xi_{ij}(u) = u_i u_j$. A continuación, $\xi(u)$ es un vector aleatorio con $\binom{n}{2}$ coordenadas. Considere el vector $S = \sum_{u\in X} \xi(u)$. Como hemos demostrado en la Reivindicación 2, si $X$ cumple la condición, a continuación, $S_{ij} = 0$ por cada $1\leq i < j \leq n$; es decir, el vector $S$ es igual a $0$.

Es fácil ver que la matriz de covarianza de $\xi$ es la matriz identidad $I_{n(n-1)/2}$. Por lo tanto, por el Teorema Central del Límite $S$ se distribuye asintóticamente como $\cal{N}(0, m \, I_{n(n-1)/2})$ (distribución normal multivariante). Por otra parte, el Local Teorema Central del Límite nos da un límite en la probabilidad de que $S=0$. Recordemos que el Teorema del Límite Central muestra que para cada $S_0$, $$\Pr(S=S_0) \leq C_n' \left(\frac{1}{\sqrt{2\pi m}}\right)^{n(n-1)/2}\left(e^{-|S_0|^2/(2m)} + o(1)\right),$$ donde $C_n'$ es un número que depende de $n$ (más precisamente, en la distribución de $\xi$), $\left(\frac{1}{\sqrt{2\pi m}}\right)^{n(n-1)/2}\cdot e^{-|S_0|^2/(2m)}$ es la densidad de la distribución multivariante, y $o(1)$ es un término de error.

Conectar $S_0 = 0$, obtenemos que la probabilidad es en la mayoría de las $C_n \cdot (1/\sqrt{m})^{n(n-1)/2} = C_n /m^{n(n-1)/4}$. Así

$$p(m,n) \leq C_n /m^{n(n-1)/4}.$$

QED

Reivindicación 4. Tenemos:

1. $p(m,2) = \binom{m}{m/2}/2^m$ si $m$ es incluso; $p(m,2) = 0$ si $m$ es impar.
2. $p(m,3) = m!/(4^m ((m/4)!)^4)$ si $m$ es divisiva por 4; $p(m,3) = 0$ lo contrario.

Prueba: tenga en cuenta que la condición en el set $X$ es equivalente a la siguiente:

Condición de $\star$: Cada hyperplane de dimensión $n-1$ (que pasa por el origen) contiene en la mayoría de las $n/2$ vectores de $X$.

Digamos que un hyperplane $H$ es maximal si no hay hyperplane $H'$ tal que $H\cap \{\pm 1\}^n \subset H'\cap \{\pm 1\}^n$ y la inclusión es estricta. Está claro que es suficiente con considerar sólo la máxima hyperplanes en Condición de $\star$. Para $n=2$ la única máxima hyperplanes son $$H_1 = \{(u_1,u_2):u_1=u_2\} = \{(1,1),(-1,-1)\} \text{ and } H_2=\{(u_1,u_2):u_1=-u_2\}=\{(1,-1),(-1,1)\};$$ para $n=3$, cada máxima hyperplane es de la forma $$H_{ij}^+ = \{(u_1,u_2,u_3):u_i=u_j\} \text{ and } H_{ij}^-=\{(u_1,u_2,u_3):u_i=-u_j\}$$

Deje $f(v)$ el número de vectores en $X$ (con multiplicidades) igual a $v$ o $-v$. Es fácil comprobar que $X$ satisface la Condición $\star$ si y sólo si $f(v) = m/2$ por cada $v\in \{\pm 1 \}^2$ al $n=2$ $f(v) = m/4$ por cada $v\in \{\pm 1 \}^3$ al $n=3$. La declaración de la reclamación de la siguiente manera.

QED