papers/lux-wave-protocol/sections/05-markov-chain-model-of-counter-evolution.tex

\section{Markov Chain Model of Counter Evolution}

\label{sec:markov}

\subsection{State Space}

We model the confidence lead $\Delta d = d_1 - d_0$ as a Markov chain on $\mathbb{Z}$.
In each round, the state transitions are:

\begin{equation}
\Delta d(r+1) = \Delta d(r) + \begin{cases}
+1 & \text{with probability } q_1(1 - q_0) \\
-1 & \text{with probability } q_0(1 - q_1) \\
+1 & \text{with probability } q_1 q_0 \cdot \frac{1}{2} \text{ (simultaneous, net +1 by tie-break)} \\
0 & \text{otherwise}
\end{cases}
\label{eq:markov}
\end{equation}

where $q_c = \Phi(p_r, k, \alpha)$ for the current population fraction. In practice,
the simultaneous supermajority case ($q_1 q_0$ both positive) is negligible when the
population fraction $p_r$ is away from $1/2$.

\subsection{Absorption Time}

\begin{lemma}[Expected Finalization Time]
\label{lem:absorption}
Starting from $\Delta d(0) = 0$, the expected number of rounds to reach $\Delta d = \beta_1$
is:
\[
\mathbb{E}[\tau_{\beta_1}] = \frac{\beta_1}{q_1 - q_0} + O\left(\frac{q_0}{(q_1 - q_0)^2}\right)
\]
where the second term accounts for excursions toward color 0.
\end{lemma}

\begin{proof}
The random walk with drift $\mu = q_1 - q_0 > 0$ and step variance $\sigma^2 \leq q_1 + q_0$
has expected first passage time to level $\beta_1$ given by the Wald identity:
$\mathbb{E}[\tau_{\beta_1}] = \beta_1 / \mu$ to leading order. The correction term
arises from the discrete nature of the walk and the possibility of downward excursions
before the absorbing barrier. A standard renewal theory argument bounds the correction
by $\sigma^2/\mu^2 = O(q_0/(q_1 - q_0)^2)$ since $\sigma^2 \leq q_1 + q_0 \leq 2q_1$.
\end{proof}

\begin{proposition}[Latency Bound]
\label{prop:latency}
For standard parameters ($k = 20$, $\alpha = 0.8$, $\beta_1 = 11$) and $p_0 = 0.55$
(slight initial majority), the expected finalization latency is at most 20 rounds.
With a round time of 50ms, this yields sub-second finality.
\end{proposition}

\begin{proof}
After 4 convergence rounds (Theorem~\ref{thm:convergence}), $p_4 > 0.99$, giving
$q_1 \approx 0.63$ and $q_0 < 10^{-6}$. Thus the drift $\mu \approx 0.63$ and
$\mathbb{E}[\tau_{11}] \approx 11/0.63 \approx 17.5$ rounds. Adding the 4 convergence
rounds gives $\leq 22$ rounds total, well under the 50ms/round $\times$ 22 = 1.1s budget.
In practice, once $p > 0.8$, the confidence counter increments almost every round,
yielding $\approx 15$ total rounds (750ms).
\end{proof}

%% -----------------------------------------------------------------------
%%  6. DAG MONOTONICITY
%% -----------------------------------------------------------------------