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

Question

Let $V$ be an $n$-dimensional $\mathbb F_2$ vector space. Note that $V$ has $2^n$ elements and $\mathcal P(V)$ has $2^{2^n}$.

I'm interested in the probability (under a uniform distribution) that an element of $\mathcal P(V)$ is a spanning set for $V$. Equivalently a closed form formula (or at least one who's asymptotics as $n\rightarrow \infty$ are easy to work out) for the number of spanning sets or non-spanning sets.

It's not hard to show that the probability is greater than or equal to $1/2$. Since any subset of size greater than $2^{n-1}$ must span the space. I calculated the proportion of spanning sets of size $n$ for $n$ up to $200$ which seem to be going to a number starting with $.2887$. This leads me to believe that the probability exceeds $1/2$. I couldn't nail down a formula for arbitrary sized subsets though to continue experimental calculations.

I feel like this is something that's been done before, but googling I've mostly found things concerning counting points on varieties over finite fields or counting subspaces of finite fields. Any references would be appreciated.

Answer 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.

Answer 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$.