A while back I posted a question in MO about the average minimum number of independent random k-sparse (having at most $k$ non-zero elements) vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$. I am now interested in solving another similar problem. What is the average minimum number of independent random $k$-sparse vectors $\mathbf{v}_1,\dots,\mathbf{v}_m$ needed to span a specific base vector $\mathbf{e}_1 = [1 ~0 \dots 0] \in \mathbb{F}_2^n$? i.e. What is $\mathbb{E}[m]$ where $m$ is the minimum number such that $~\mathbf{e}_1 \in \mathrm{Span}\{\mathbf{v}_1,\dots,\mathbf{v}_m\}$? All ${\sum_{j=0}^k \binom{n}{j}}$ random $k$-sparse vectors are uniformly probable to be drawn.
Here are some observations:
For $k=1$ from the coupon collector problem we know that on average $\Theta(n \log(n))$ vectors are needed to span the whole space while on average $\mathbb{E}[m] = n$ vectors are needed to span a specific base vector.
As proved by Sam Zbarsky in the answer to my question, for $k=\Theta(\log(n))$ we need $\Theta(n)$ vectors to span the whole space so $\mathbb{E}[m] = O(n)$ in this case. Can we find a better upper bound or a lower bound on $\mathbb{E}[m]$ in this case?
My simulations show that as $k$ increases from $k=1$, $\mathbb{E}[m]$ reduces from $\mathbb{E}[m]=n$ up to a certain threshold value of $k$ (possibly it reduces up to $k=\Theta(\log(n))$). Then it quickly rises up to $\mathbb{E}[m] = n$ after that. Can we characterize the sweet spot for $k$ which minimized $\mathbb{E}[m]$ in terms of $n$? Does $k = \Theta(\log(n))$ represent the sweet spot? What is the value of $\mathbb{E}[m]$ for this sweet spot choice of $k$?
