Timeline for Average minimum number of random k-sparse vectors in GF(2) to span the whole space?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2016 at 21:02 | comment | added | Sam Zbarsky | 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. | |
| May 4, 2016 at 18:56 | vote | accept | mhsnk | ||
| May 4, 2016 at 17:36 | comment | added | mhsnk | 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))$? | |
| May 4, 2016 at 8:59 | history | answered | Sam Zbarsky | CC BY-SA 3.0 |