Random spanning of a binary vector space ($\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\ge 1$, the bound follows by separating $j=1$ and using $(2^j-1{)}^{-1}<2^{1-j}$ for $j\ge 2$; 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.