Expected number of random binary vectors so that the form a basis

Question

I would like to compute the expected number of vectors in $\mathbb{F}_2^n$ we need to draw (following a uniform distribution) so that they form a basis of $\mathbb{F}_2^n$, i.e., that we have $n$ linearly independent vectors.

Answer 1

This is a $q$-analogue of the coupon collector problem.

If the first few vectors span a subspace of codimension $k$, then the probability of drawing a vector outside this subspace is $1-2^{-k}$ and the expected number of draws to get a vector outside this subspace is the reciprocal $\frac{2^k}{2^k-1}=1+\frac{1}{2^k-1}$. The expected number of draws for the vectors to span $\mathbb{F}^n_2$ is

$$\sum_{k=1}^n \frac{2^k}{2^k-1} = n+1+\frac{1}{3}+\frac{1}{7}+\ldots+\frac{1}{2^n-1} \lt n+2.$$