= Random spanning of a binary vector space
{title2=$\mathbb E M=\sum_{j=1}^d(1-2^{-j})^{-1}<d+2$}
Take independent uniform samples from a $d$-dimensional <vector space> over the two-element <field>. At current <matrix rank> $r$, the existing span contains $2^r$ of the $2^d$ possible vectors, so a new sample increases the <matrix rank> with <probability> $1-2^{r-d}$. The mean waiting time for that increase is $1/(1-2^{r-d})$ by the <geometric distribution>. Adding the waiting times gives $\mathbb E M=d+\sum_{j=1}^d(2^j-1)^{-1}<d+2$. For $d\geq1$, the bound follows by separating $j=1$ and using $(2^j-1)^{-1}<2^{1-j}$ for $j\geq2$; for $d=0$, no samples are needed.
After $m=d+t$ samples, failure to span implies that some nonzero <linear functional> vanishes on all samples. Each fixed nonzero functional does so with <probability> $2^{-m}$; the <union bound> over the $2^d-1$ possibilities gives failure less than $2^{-t}$. This provides both an expected sample count and a fixed-budget high-success version of <Simon's algorithm>.
Back to article page
