6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You might look at this related MO question of mine and its answer by Kevin Costello. $\endgroup$ – Robert Israel May 3 '16 at 17:21
  • $\begingroup$ Thank you Robert! I have seen this post before and also the mentioned papers. My guess is that if $k$ is larger than the XORSAT satisfiability threshold, the average minimum required number of vectors will be equal to $n(1+o(1))$ but I don't know how to prove or disprove it? $\endgroup$ – Mohsen Kiskani May 3 '16 at 17:37
  • $\begingroup$ When k=2, this is equivalent to taking a graph on n+1 vertices and adding random edges until it is connected. Here the vector $e_i+e_j$ corresponds to edge $(i,j)$ and the vector $e_i$ corresponds to edge $(0,i)$ $\endgroup$ – Sam Zbarsky May 4 '16 at 14:31
  • $\begingroup$ This is a nice analogy. Do you know the exact value of the minimum number of edges to be added to make this graph connected. $\endgroup$ – Mohsen Kiskani May 4 '16 at 20:34
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Sam! I think this is the correct answer for $k=\Theta(\log(n))$. But what is the actual threshold for $k$ such that the average number is $\Theta(n)$? Can we prove something stronger that the average value is indeed $n(1+o(1))$ for $k=\Omega(\log(n))$? $\endgroup$ – Mohsen Kiskani May 4 '16 at 17:36
  • $\begingroup$ This was based on taking $jk/n$ as the lower bound that each new vector is outside of $A$, which corresponds to the worst case when $A=span\{e_1,\ldots,e_{n-j}\}$. Intuitively, it seems like the average case should have higher probability (and thus take fewer steps), which would make the threshold for k less than $\log n$, but I'm not sure how to prove that. $\endgroup$ – Sam Zbarsky May 5 '16 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.