¿Cuál es la probabilidad de un subconjunto de un espacio del vector $\mathbb F_2$ es un conjunto que abarca?

Question

Deje $V$ $n$- dimensional $\mathbb F_2$ espacio vectorial. Tenga en cuenta que $V$ $2^n$ elementos y $\mathcal P(V)$$2^{2^n}$.

Estoy interesado en la probabilidad (en virtud de una distribución uniforme) que un elemento de $\mathcal P(V)$ es un sistema generador de $V$. De forma equivalente, una forma cerrada de la fórmula (o al menos uno que asymptotics como $n\rightarrow \infty$ son fáciles de trabajo) para el número de abarca establece o no-que abarca conjuntos.

No es difícil mostrar que la probabilidad es mayor o igual a $1/2$. Desde cualquier subconjunto de tamaño mayor que $2^{n-1}$ debe abarcar el espacio. He calculado la proporción de la distribución de los conjuntos de tamaño $n$$n$$200$, lo que parece ser que va a un número que empieza con $.2887$. Esto me lleva a creer que la probabilidad supera $1/2$. Yo no podía concretar una fórmula arbitraria de subconjuntos de tamaño a pesar de continuar experimental cálculos.

Siento que esto es algo que ya se ha hecho antes, pero googleando he encuentran sobre todo cosas relacionadas con el conteo de puntos en las variedades más finito campos o contando los subespacios de campos finitos. Las eventuales referencias que se agradece.

Answer 1

Un subconjunto aleatorio de $V$ es owerwhelmingly probable para abarcar $V$.

Echemos un vistazo a lo difícil que es para un subconjunto aleatorio no a palmo $V$. Con el fin de no abarcar $V$, debe haber un $(n-1)$-dimensiones del subespacio que contiene la totalidad del subconjunto. Hay exactamente $2^n-1$ tales subespacios, ya que son en bijective correspondencia con la lineal no trivial de mapas de $V\to\mathbb F_2$ (cada subespacio es el núcleo de exactamente un mapa).

Para cada uno de los fijos $(n-1)$ dimensiones subespacio, la probabilidad de que un subconjunto aleatorio de mantenerse dentro de ese subespacio es $2^{-2^{n-1}}$, puesto que el $2^{n-1}$ vectores fuera del subespacio deben al azar decide no estar en el subconjunto.

De modo que la probabilidad de que un conjunto aleatorio no a palmo es en la mayoría de las $(2^n-1)2^{-2^{n-1}} < 2^{-(2^{n-1}-n)}$ (y esto es un poco demasiado alto, porque hay algunos que no abarcan los subconjuntos que tienen más de una adecuada subespacio encajan en y, entonces, se cuentan dos veces aquí). Todo lo demás se extiende.

Incluso para $n$ tan pequeño como $5$ la probabilidad de que un subconjunto aleatorio para abarcar $V$ es superior al 99,9%, y el número de 9 aumenta exponencialmente con mayor $n$s.

Answer 2

Vale la pena mencionar que no hay una fórmula explícita para la probabilidad de que $N$ aleatoria de vectores dibujados a partir de $\mathbb{F}_q^n$ de intervalo. (Nota: estoy haciendo el muestreo con reemplazo. Si desea solicitar el $N$ vectores a ser distinto, usted puede hacer esto mediante la inclusión-exclusión, pero el resultado será mucho más complicada.) Por supuesto, la respuesta es $0$ si $N<n$, por lo que asumen $N \geq n$.

Escribir un $n \times N$ matriz cuyas columnas son los vectores en cuestión. Tenga en cuenta que los siguientes son equivalentes:

1. Las columnas span $\mathbb{F}_q^n$.
2. La matriz tiene rango $n$.
3. Las filas son linealmente independientes.

Pensar en términos de filas, tenemos la nueva pregunta: Si dibujamos $n$ vectores al azar de $\mathbb{F}_q^N$, ¿cuál es la probabilidad de que sean linealmente independientes?

La probabilidad de que el primer vector es distinto de cero es $1-q^{-N}$. Dado que, la probabilidad de que el segundo vector no es en el lapso de la primera es $1-q^{-N+1}$. Dado que, la probabilidad de que el tercer vector no es en el lapso de los dos primeros es $1-q^{-N+2}$. Continuar de esta forma, la probabilidad de que $n$ vectores en $\mathbb{F}_q^n$ son independientes es $$(1-q^{-N}) (1-q^{-N+1}) \cdots (1-q^{-N+n-1}).$$ Y, por el argumento anterior, esta es también la probabilidad de que $N$ random vectores tendrá una duración de $\mathbb{F}_q^n$.

En particular, como Henning dice, una vez $N-n$ es de cualquier tamaño significativo, esto está muy cerca de a $1$.