papers/lux-ray-protocol/sections/04-estimator-convergence.tex

\section{Estimator Convergence}

\label{sec:estimator}

\begin{theorem}[Adversary Estimate Convergence]
\label{thm:estimator}
The Bayesian adversary estimator $\hat{\gamma}_r$ converges to the true adversarial
fraction $\gamma$ with rate:
\[
\mathbb{E}[|\hat{\gamma}_r - \gamma|] \leq (1 - \eta)^r |\hat{\gamma}_0 - \gamma| + \frac{\eta \sigma_k}{\sqrt{2 - \eta}}
\]
where $\sigma_k = \sqrt{p(1-p)/k}$ is the sampling standard deviation and $\eta \in (0, 1)$
is the learning rate.
\end{theorem}

\begin{proof}
The estimator follows the recursion $\hat{\gamma}_r = \eta X_r + (1 - \eta)\hat{\gamma}_{r-1}$
where $X_r = 1 - n_c/k$ is the observed adversarial fraction. Each $X_r$ has mean $\gamma$
and variance $\sigma_k^2 = p(1-p)/k$.

The bias decays as $(1-\eta)^r$:
\[
\mathbb{E}[\hat{\gamma}_r] - \gamma = (1-\eta)^r(\hat{\gamma}_0 - \gamma)
\]

The variance satisfies:
\[
\text{Var}[\hat{\gamma}_r] = \eta^2 \sigma_k^2 \sum_{i=0}^{r-1} (1-\eta)^{2i}
\leq \frac{\eta^2 \sigma_k^2}{1 - (1-\eta)^2} = \frac{\eta \sigma_k^2}{2 - \eta}
\]

Combining bias and standard deviation by Jensen's inequality gives the stated bound.
For $\eta = 0.1$, $k = 20$, and $r \geq 30$: the bias term is negligible
($(0.9)^{30} < 0.04$) and the variance term contributes $\sqrt{0.1 \cdot 0.25/20 / 1.9} \approx 0.026$,
giving an estimate accurate to within 3\% of the true $\gamma$.
\end{proof}

\begin{lemma}[Conservative Threshold]
\label{lem:conservative}
If the estimator uses an upper confidence bound $\hat{\gamma}^+ = \hat{\gamma}_r + z_{\delta} \sqrt{\text{Var}[\hat{\gamma}_r]}$
with $z_\delta$ chosen for confidence level $1 - \delta$, then the derived threshold
$\beta^*$ is sufficient for safety with probability $\geq 1 - \delta$.
\end{lemma}

\begin{proof}
The upper confidence bound ensures $\hat{\gamma}^+ \geq \gamma$ with probability $1 - \delta$.
When $\hat{\gamma}^+ \geq \gamma$, the derived threshold satisfies:
\[
\beta^* = \frac{128 \ln 2}{\ln(q_1(\hat{\gamma}^+) / q_0(\hat{\gamma}^+))} \geq \frac{128 \ln 2}{\ln(q_1(\gamma) / q_0(\gamma))}
\]
since $q_1/q_0$ is decreasing in $\gamma$ (more adversaries make the ratio closer to 1).
Thus $\beta^*$ overestimates the required threshold, maintaining safety.
\end{proof}

%% -----------------------------------------------------------------------
%%  5. SAFETY ANALYSIS
%% -----------------------------------------------------------------------