36. A finite experimental route to the probability table
On this page · Permalink · Source line 1501
The following deliberately simple protocol makes a finite-sample statement possible without confusing a deterministic identity with a statistical guarantee.
Fix positive integers \(M\) and \(N\) and choose \(M\) finite words before estimation. For each word, reset independently to the same initial distribution, execute its prescribed action sequence, and record the indicator that all observations match. Obtain \(N\) independent trials per word. Dependencies between different words' estimates are allowed, but the \(N\) trials used for each individual mean must be independent with the declared success probability.
Proposition 35: Reset-experiment probability certificate
Let \(\widehat f(w)\) be the sample mean for each selected word. For \(0<\delta<1\), with probability at least \(1-\delta\), all \(M\) estimates satisfy
If the selected words cover every entry of \(H\), every \(G_s\), and \(b_0\), then on the same event
These bounds feed Propositions 32 and 33 whenever their respective gap conditions hold. The empty-word probability may be set exactly to one instead of sampled.
Read proof · Recorded Lean scope · Permalink · Source line 1507
Proof
For a centered Bernoulli variable \(X-p\), write \(g(t)=\log\mathbb E\exp(t(X-p))\). Then \(g(0)=g'(0)=0\), and \(g''(t)\) is the variance of a Bernoulli under exponential tilting, at most \(1/4\). Integrating twice gives \(g(t)\leq t^2/8\). Independence and the exponential Markov inequality give an upper-tail bound \(\exp(-2N\epsilon^2)\) after optimizing \(t=4\epsilon\). The lower tail has the same bound. A union bound over the \(M\) words proves the simultaneous result. The spectral norm is bounded by the Frobenius norm, yielding the matrix and vector estimates. \(\square\)
This is the Bernoulli form of Hoeffding's inequality [R11], proved here for the protocol used. It is a conservative entrywise-to-spectral bound, not a claim of optimal sample complexity. The number and lengths of chosen experiments are part of its cost.
If core tests and histories were selected from data, use a separate independent discovery sample and freeze the selected finite experiment list before these estimation trials. Conditional on that selection, the proposition applies. Alternatively, a uniform bound over a fixed larger candidate list can support data-dependent selection within that list. Reusing a post-selected table without either argument changes the claim.
A single dependent trajectory, an adaptive stopping rule, unknown resets, drifting sensors, or experiments chosen without coverage do not satisfy this proposition as stated. Those settings require their own concentration and identifiability arguments. Synthetic reset sampling in the reference example demonstrates the protocol, not its validity for every measurement source.