Entropy as a Supermartingale, Stopping Times, and Query Complexity

Setting and Notation

We answer a query $q$ about a latent correct answer $Y\in\mathcal Y$. At time $t$, the agent has an evidence graph

$$G_t=\Phi(r_{1:t},q),$$

and its uncertainty is

$$H_t ;=; H(Y\mid q,G_t).$$

Let the filtration (the information the agent has seen so far) be

$$\mathcal F_t ;=; \sigma\big(q,a_{1:t},r_{1:t}\big).$$

Because $G_{t}$ is a deterministic function of $(q, r_{1:t})$, both $G_t$ and $H_t$ are $\mathcal F_t$-measurable. (For background on stopping times and measurability of stopped/optional objects, see the standard definitions and results in the general theory of stochastic processes.)

Assumptions

• A (no systematic misinformation): Conditioning on $\mathcal F_{t}$, the expected entropy after incorporating the next result does not increase: $$\mathbb{E} \left[ H \big(Y \mid q,G_{t}\cup{r_{t+1}}\big),\big|,\mathcal F_t\right]\leH(Y\mid q,G_t).$$
• B (causality): The policy chooses $a_t$ using only current information, i.e., $a_t$ is $\mathcal F_t$-measurable.

Theorem 1 — Entropy is a Supermartingale

Statement. Assume A–B and $0\le H_t<\infty$. Then $(H_t)_{t\ge 0}$ is a supermartingale w.r.t. $(\mathcal F_t)$:

$$\mathbb{E}[H_{t+1}\mid \mathcal F_t]\le H_t.$$

Proof of Theorem 1

Because $G_t$ is $\mathcal F_t$-measurable, so is $H_t=H(Y\mid q,G_t)$. By Assumption A,

$$\mathbb{E}\!\left[H(Y\mid q, G_t\cup r_{t+1})\mid \mathcal F_t\right]\le H(Y\mid q,G_t)=H_t,$$

and by definition $H_{t+1}=H(Y\mid q,G_{t+1})=H(Y\mid q,G_t\cup r_{t+1})$. Therefore $\mathbb{E}[H_{t+1}\mid\mathcal F_t]\le H_t$. ■

Stopping at Sufficient Confidence

Fix $\varepsilon>0$ and define the hitting time

$$au_\varepsilon := \inf\{t\ge 0: H_t\le \varepsilon\}.$$

Because $H_t$ is $\mathcal F_t$-measurable, the event $\{H_t\le\varepsilon\}\in\mathcal F_t$, hence $\tau_\varepsilon$ is a stopping time. (Stopped/optional objects at stopping times are measurable in the expected $\sigma$-fields.)

Under standard integrability/regularity (boundedness or bounded increments suffices in our discrete setup), optional stopping for supermartingales yields

$$\mathbb{E}[H_{\tau_\varepsilon}]\le\mathbb{E}[H_0],\qquad ext{and since } H_{\tau_\varepsilon}\le \varepsilon,\quad \mathbb{E}[H_0]-\varepsilon\le\mathbb{E}[H_0]-\mathbb{E}[H_{\tau_\varepsilon}].$$

(For the discrete-time optional sampling/sampling inequality, see Doob’s theorem in Pascucci’s Chapter 6; it is stated for sub/martingales and used analogously for supermartingales with signs adjusted. )

From Information Gain to Cost

Define the conditional expected entropy drop at step $t$:

$$\Delta_t := H_{t-1}-\mathbb{E}[H_t\mid \mathcal F_{t-1}] \ge 0 \quad\text{(by Theorem 1)}.$$

Summing to $\tau_\varepsilon$ and taking expectations,

$$\mathbb{E}\big[H_0-H_{\tau_\varepsilon}\big] = \mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}\Delta_t\right] \ge \mathbb{E}[H_0]-\varepsilon. \tag{*}$$

Let each action have cost $c(a_t)\ge 0$. Suppose the per-step “bits-per-cost” is bounded by a channel constant $\Gamma$ in expectation:

$$\mathbb{E}[\Delta_t\mid\mathcal F_{t-1}] \le \Gamma\,\mathbb{E}[c(a_t)\mid\mathcal F_{t-1}].$$

Then

$$\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}\Delta_t\right] \le \Gamma\,\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}c(a_t)\right].$$

Combining with ((*)) gives the effort lower bound

$$\boxed{ \mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}c(a_t)\right] \ge \frac{\mathbb{E}[H_0]-\varepsilon}{\Gamma} }$$

Proof notes (why optional stopping is legitimate)

• We’re in discrete time, (Ht) is bounded below, and (\tau\varepsilon) is (by design) a bounded/finite stopping time under any admissible policy that either hits (\varepsilon) or halts with abstention. Under these mild conditions, the optional sampling/optional stopping statements we used are standard.

Query Complexity

Definition (Query complexity at tolerance $\varepsilon$).

$$C(q;\varepsilon) := \inf_{\pi\ \text{admissible}} \mathbb{E}_\pi\Bigg[\sum_{t=1}^{\tau_\varepsilon}c(a_t)\Bigg].$$

Taking infimum over policies in ((†)) yields a first-principles lower bound on (C(q;\varepsilon)).

Sigma-Algebras & Filtrations (quick refresher)

• A sigma-algebra lists the events you can measure; a filtration $(\mathcal F_t)$ is a growing family of such sigma-algebras capturing information over time. (Formal definitions and the role of optional/predictable $\sigma$-fields are standard; see, e.g., the development of optional processes and their measurability at stopping times.)
• Stopping times are random times whose occurrence is knowable from the past: $\{\tau\le t\}\in\mathcal F_t$. (Definition and basic properties; also how stopped processes inherit measurability.)
• Optional sampling/Doob: for (super/sub)martingales, conditional expectations at stopping times behave as expected; see the discrete statement used repeatedly in practice.

Proof of “$\tau_\varepsilon$ is a stopping time”

Because $H_t$ is $\mathcal F_t$-measurable, $\{H_t\le\varepsilon\}\in\mathcal F_t$. The event $\{\tau_\varepsilon\le t\}$ equals $\bigcup_{s\le t}\{H_s\le\varepsilon\}\in\mathcal F_t$, so $\tau_\varepsilon$ is a stopping time (and standard section/projection results ensure the usual measurability behaviors at $\tau$).

---

Takeaways

Supermartingale spine

(H_t) drops in conditional expectation under non-deceptive retrieval.

Stopping-time policy

“Stop when (H_t\le \varepsilon)” is well-posed and analyzable.

Effort lower bound

Expected cost (\ge (\mathbb E[H_0]-\varepsilon)/\Gamma).

Composable with graphs

Combine the bits-per-cost bound with graph-theoretic lower bounds (e.g., Steiner-style) to capture structural hardness as well as informational hardness.

---

Proof of Optional Sampling we rely on

(Discrete) Optional Sampling Theorem. If $M$ is a (sub/super)martingale and $\sigma\le \tau$ are stopping times with standard integrability/boundedness, then

$$\mathbb{E}[M_\tau\mid \mathcal F_\sigma]\ \begin{cases} = M_\sigma & \text{(martingale)}\\ \ge M_\sigma & \text{(submartingale)}\\ \le M_\sigma & \text{(supermartingale)}. \end{cases}$$

See Pascucci, Ch. 6 (discrete case); analogous statements reappear in continuous time with usual conditions.

---

---

Derivation — Cost Lower Bound from Supermartingale

Proof

Let $\Delta_t=H_{t-1}-\mathbb{E}[H_t\mid\mathcal F_{t-1}]\ge 0$. Summing to $\tau_\varepsilon$ and taking expectations gives

$$\mathbb{E}[H_0-H_{\tau_\varepsilon}] =\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}\Delta_t\right] \ge \mathbb{E}[H_0]-\varepsilon.$$

If $\mathbb{E}[\Delta_t\mid\mathcal F_{t-1}]\le \Gamma\,\mathbb{E}[c(a_t)\mid\mathcal F_{t-1}]$ for some $\Gamma>0$, then

$$\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}\Delta_t\right] \le \Gamma\,\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}c(a_t)\right],$$

so

$$\mathbb{E}\!\left[\sum_{t=1}^{\tau_\varepsilon}c(a_t)\right] \ge \frac{\mathbb{E}[H_0]-\varepsilon}{\Gamma}.$$