Average minimum number of random k-sparse vectors in GF(2) to span the whole space? What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? Any such vector is uniformly probable to be chosen among the total $\sum_{j=0}^k \binom{n}{j}$ vectors. 
Here are the two extreme cases: 


*

*If $k=n$, this average value is $n+1.6067$ as proved here.

*If $k=1$, using coupon collector problem this average value is proved to be larger than $\Theta(n \log n)$.


Can we prove that if $k = \Theta(\log n)$, then this average value is $\Theta(n)$? or something similar? My simulation results show that for a pretty large range of $k$ this average value is $\Theta(n)$. 
 A: Let $k=\Theta(\log n)$. We will keep adding random $k$-sparse vectors one at a time and stop when we get a spanning set. Assume that currently the vectors span a space $A$ of codimension $j$ for $j\le n/(2k)$. We want to figure out the expected number of steps to reach codimension $j-1$, which is the inverse of the probability that a randomly chosen $k$-sparse vector is outside of $A$.
Since $A$ has codimension $j$, we can find $j$ basis vectors $e_{\ell_1},\ldots,e_{\ell_j}$ such that $A\cap\text{span}(e_{\ell_1},\ldots,e_{\ell_j})=\{0\}$. This means that for any vector $v$ that has $k-1$ 1's, none of them at a position $\ell_i$, we have that at most one of $v,v+e_{\ell_1},v+e_{\ell_2},\ldots,v+e_{\ell_j}$ is in $A$. Thus there are at least $j\binom{n-j}{k-1}$ $k$-sparse vectors outside of $A$, so the probability of a random $k$-sparse vector is outside of $A$ is at least
$$
\frac{j\binom{n-j}{k-1}}{\sum_{i=0}^k \binom{n}{i}}=\Theta\left(\frac{j\binom{n}{k-1}}{\binom{n}{k}}\right)=\Theta\left(\frac{jk}{n}\right)=\Theta\left(\frac{j\log n}{n}\right)
$$
where we used the fact that $j\le n/(2k)$ to get $\binom{n-j}{k-1}=\Theta\left(\binom{n}{k-1}\right)$. This means that going from codimension $j$ to codimension $j-1$ takes an average of $\Theta\left(\frac{n}{j\log n}\right)$ steps, so going from codimension $\lfloor \frac{n}{2k}\rfloor$ to codimension $0$ (spanning set) takes an average of
$$
\sum_{j=1}^{n/(2k)} \frac{n}{j\log n}=\Theta\left(\frac{n\log(n/(2k))}{log n}\right)=\Theta(n)
$$
steps.
If the codimension is $j=\lfloor \frac{n}{2k}\rfloor$, then we derived above that decreasing the codimension by 1 requires an average of $\Theta\left(\frac{n}{j\log n}\right)=\Theta(1)$ steps. Since the number of steps necessary is only smaller when the codimension is greater, it takes us at most $\Theta(n/\log n)$ steps to get to codimension $\lfloor \frac{n}{2k}\rfloor$. Therefore the whole process takes $\Theta(n)$ steps.
