Simon rank growth probability

By [F1], each accepted row was outside the span of its predecessors. In a zero linear combination, if the last nonzero coefficient were $1$, that row would be a combination of its predecessors, contradicting acceptance; since the only nonzero scalar is $1$, this proves inductively that the accepted list is independent by [F6]. It spans $V_k$ by [F7], hence is a basis by [F8]. The coefficient map from ${\mathbb{F}}_2^k$ to $V_k$ is injective by independence and surjective by span; [F4] gives $2^k$ possible coefficient lists, so $\mathrm{\mid }{V}_k\mathrm{\mid }=2^k$.

By [F2]–[F3], samples are uniform on the $2^d$ elements of $s^{\perp }$, and [F1] gives $V_k\subseteq s^{\perp }$. Exactly $2^k$ lie in $V_k$ by step 1.1, so the probability the next sample is accepted is $(2^d-2^k)\mathrm{/}{2}^d=1-2^{k-d}=p_k$, while the failure probability is $q_k=2^{k-d}\le 1\mathrm{/}2$.

Condition on any rank-$k$ history and use the finite $r$-sample continuation experiment. Let $A_{k,r}$ be the event that every one of those $r$ samples lies in the current span $V_k$. On this event the span remains $V_k$ throughout; by freshness, each conditional failure probability is $q_k$, so multiplying the finite conditional probabilities gives $\mathrm{Pr}(A_{k,r})=q_k^r$. For $r=0$, $A_{k,0}$ is the whole one-outcome empty continuation and has probability $1=q_k^0$.

For each finite horizon $M$, the explicitly defined $W_{k,M}$ is a function on the finite experiment by [F9]–[F10]. For every $0\le j<M$, the event $\{W_{k,M}>j\}$ is the event $A_{k,j}$ after projection to its first $j$ samples, so $W_{k,M}={\sum }_{j=0}^{M-1}{\mathbf{1}}_{A_{k,j}}$. The expectation definition [F11] and step 3.1 give $\mathbb{E}[W_{k,M}]={\sum }_{j=0}^{M-1}{q}_k^j$. Since $0\le q_k\le 1\mathrm{/}2$, [F12] bounds these partial sums by $1\mathrm{/}(1-q_k)=1\mathrm{/}{p}_k\le 2$.