Whats the probability a subset of an $\mathbb F_2$ vector space is a spanning set?

Solution 1:

A random subset of $V$ is owerwhelmingly likely to span $V$.

Let's look at how hard it is for a random subset not to span $V$. In order not to span $V$, there must be an $(n-1)$-dimensional subspace that contains the entire subset. There are exactly $2^n-1$ such subspaces, since they are in bijective correspondence with the nontrivial linear maps $V\to\mathbb F_2$ (each subspace is the kernel of exactly one map).

For each fixed $(n-1)$ dimensional subspace, the probability for a random subset to stay within that subspace is $2^{-2^{n-1}}$, since the $2^{n-1}$ vectors outside the subspace must all randomly decide not to be in the subset.

So the probability for a random set not to span is at most $(2^n-1)2^{-2^{n-1}} < 2^{-(2^{n-1}-n)}$ (and this is slightly too high, because there are a few non-spanning subsets that have more than one proper subspace they fit into and so are counted twice here). Everything else spans.

Even for $n$ as small as $5$ the probability for a random subset to span $V$ is above 99.9%, and the number of 9's increases exponentially with larger $n$s.

Solution 2:

It's worth mentioning that there is an explicit formula for the probability that $N$ random vectors drawn from $\mathbb{F}_q^n$ span. (Note: I am doing sampling with replacement. If you want to require the $N$ vectors to be distinct, you can do this using inclusion-exclusion, but the result will be much messier.) Of course, the answer is $0$ if $N<n$, so assume $N \geq n$.

Write down an $n \times N$ matrix whose columns are the vectors in question. Note that the following are equivalent:

1. The columns span $\mathbb{F}_q^n$.
2. The matrix has rank $n$.
3. The rows are linearly independent.

Thinking in terms of rows, we have the new question: If we draw $n$ vectors at random from $\mathbb{F}_q^N$, what is the probability that they are linearly independent?

The probability that the first vector is nonzero is $1-q^{-N}$. Given that, the probability that the second vector is not in the span of the first is $1-q^{-N+1}$. Given that, the probability that the third vector is not in the span of the first two is $1-q^{-N+2}$. Continuing in this manner, the probability that $n$ vectors in $\mathbb{F}_q^n$ are independent is $$(1-q^{-N}) (1-q^{-N+1}) \cdots (1-q^{-N+n-1}).$$ And, by the above argument, this is also the probability that $N$ random vectors will span $\mathbb{F}_q^n$.

In particular, as Henning says, once $N-n$ is of any significant size, this is extremely close to $1$.