 Expected query count for Simon sampling

With a nonzero hidden period, Simon's algorithm samples uniformly from its $(n-1)$-dimensional orthogonal complement over the binary field. At rank $k$, a new sample raises the rank with probability $1-2^{k-(n-1)}$. Summing the geometric waiting times gives an expected $n-1+{\sum }_{j=1}^{n-1}(2^j-1{)}^{-1}<n+1$ queries. After $n-1+c$ samples, the probability of insufficient rank is less than $2^{-c}$, by a union bound over the nonzero linear functionals that could annihilate all samples.