Chernoff repetition bound for common-kernel recovery

If $s$ cuts have occurred, repeated halving gives $\mathrm{\mid }K\mathrm{\mid }\le N\mathrm{/}{2}^s\le 1$. Since $H\le K$ and a subgroup contains the identity, this forces $K=H$. Consequently, on the event $K_M\mathrm{\ne }H$, the process remained strictly above $H$ for all $M$ trials and fewer than $s$ actual cuts occurred.

Couple each trial, while $K_{t-1}>H$, by first drawing its cut indicator $C_t$ with conditional probability $p_t\ge 1\mathrm{/}2$ and then drawing ${\chi }_t$ from the uniform distribution conditioned on that indicator. If $C_t=1$, draw an auxiliary $Y_t\in \{0,1\}$ with conditional probability $\mathbb{P}(Y_t=1\mid C_t=1,\text{past})=1\mathrm{/}(2p_t)$; if $C_t=0$, set $Y_t=0$. Then $Y_t\le C_t$ and $\mathbb{P}(Y_t=1\mid \text{past})=1\mathrm{/}2$. After the process reaches $H$, draw fresh independent $Y_t\sim \mathrm{B}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{o}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}(1\mathrm{/}2)$. Thus the $Y_t$ are independent Bernoulli$(1\mathrm{/}2)$ variables, and on every failure outcome ${\sum }_t{Y}_t\le {\sum }_t{C}_t<s$.

Let $X:={\sum }_{t=1}^M{Y}_t$ and $\mu =M\mathrm{/}2$. The coupling and Step 1.1 give $\mathbb{P}(K_M\mathrm{\ne }H)\le \mathbb{P}(X<s)$. Since $\mu \ge 2s+8\ln (1\mathrm{/}\delta )$, we have $s\le \mu \mathrm{/}2$, so $\{X<s\}\subseteq \{X\le \mu \mathrm{/}2\}$.

Apply [F2] with $\eta =1\mathrm{/}2$ to obtain $\mathbb{P}(X\le \mu \mathrm{/}2)\le e^{-\mu \mathrm{/}8}$. The bound on $\mu$ implies $e^{-\mu \mathrm{/}8}\le e^{-\ln (1\mathrm{/}\delta )}=\delta$. Hence $\mathbb{P}(K_M\mathrm{\ne }H)\le \delta$. If $H=K_0$, the process stays at $H$ by definition, giving the stated zero failure probability.