Skip to main content
1 of 2
mhsnk
  • 307
  • 2
  • 13

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:

  1. If $k=n$, this average value is $n+1.6067$ as proved here.
  2. 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)$.

mhsnk
  • 307
  • 2
  • 13