Known-amplitude success bound

If $1\mathrm{/}2\le a<1$, the candidate $k=0$ belongs to the finite search range and has success probability ${\sin }^2\theta =a=\max \{a,1-a\}$ by [F2]. The maximizing $k$ therefore has at least this probability.

Suppose $0<a<1\mathrm{/}2$. Let $s=\sin (\pi \mathrm{/}4)=\cos (\pi \mathrm{/}4)>0$, where positivity follows from strict increase in [F5]. By [F6], $1=\sin (\pi \mathrm{/}2)=2s^2$, so $s=1\mathrm{/}\sqrt{2}$. Since $\sin \theta =\sqrt{a}<1\mathrm{/}\sqrt{2}=s$, [F5] gives $0<\theta <\pi \mathrm{/}4$. Put $r=\pi \mathrm{/}(4\theta )-1\mathrm{/}2>0$, and choose a nearest nonnegative integer $k_0$ to $r$, breaking ties toward the smaller integer. Then $\mathrm{\mid }{k}_0-r\mathrm{\mid }\le 1\mathrm{/}2$, so $\mathrm{\mid }(2k_0+1)\theta -\pi \mathrm{/}2\mathrm{\mid }\le \theta$. The addition and Pythagorean identities [F3] give ${\sin }^2((2k_0+1)\theta )\ge {\cos }^2\theta =1-a$.

Since $\sin \theta =\sqrt{a}$, [F4] gives $\theta \ge \sqrt{a}$. Hence $k_0\le r+1\mathrm{/}2=\pi \mathrm{/}(4\theta )\le \pi \mathrm{/}(4\sqrt{a})<1\mathrm{/}\sqrt{a}$ by [F7], so $k_0\le \lceil 1\mathrm{/}\sqrt{a}\rceil$. Thus $k_0$ lies in the algorithm's finite range, and [F1]–[F2] show that its selected maximizer has probability at least $1-a=\max \{a,1-a\}$. The explicit zero and unit-weight branches give the stated endpoint behavior.