A mathematical specification and zero-allocation C99 streaming engine for Symbolic Ergodeviation (
When monitoring discrete event streams—such as Hardware Performance Counter (HPC) deltas, syscall traces, kernel state transitions, or network flow buckets—classical invariants fail in two predictable ways:
-
Entropy & Lempel-Ziv are blind to geometry: Two processes supported on disjoint regions of state space (or an attacker pacing a polling loop to match baseline entropy) can share the exact same Shannon entropy rate, Kolmogorov-Sinai entropy, Lempel-Ziv complexity, and correlation dimension while occupying completely different transition sub-manifolds (Section 3.1).
-
Total Variation & KL divergence explode on local jitter: Under a discrete metric, harmless scheduler or counter noise that nudges a symbol into an adjacent quantizer bin looks like a novel distribution.
-
Naive spectral penalties fail on finite windows: Penalizing by the algebraic connectivity of the empirical visit graph diverges on non-repeating windows before the cover time (
$\lambda_2(P_n) \le 12/(n(n+1))$ ), while a two-sided ratio of Fiedler energies actively discounts anomalies that oscillate rapidly across rare graph cuts (shrinking a transport cost of$4/5$ down to$4/17$ , Section 6.2).
Let
-
Exact Zero Set (Prop. 7.1):
$\mathcal{E}_S = 0 \iff \hat\mu_{N,\ell} = \nu_\ell$ . The spectral factor never shifts the zero set. -
Local Jitter Stability (Prop. 7.3): Perturbing symbols by at most
$\eta_{\mathrm{loc}}$ in the ground metric$\delta$ increases$\mathcal{E}_S$ by at most$(1+\eta)\eta_{\mathrm{loc}}\frac{1-\theta^\ell}{1-\theta}$ , regardless of how much Shannon entropy the jitter injects. -
No-Hiding & Bottleneck Amplification (Prop. 7.4): Any drift at distance
$W_p \ge \tau$ scores at least$\tau$ . If the drift is confined to one side of the Fiedler bottleneck ($\hat\Delta_N < \lambda_2$ ), the score is strictly amplified up to$(1+\eta)\tau$ . -
Non-Asymptotic Concentration & Spectral Stability (Thm. 8.4, Cor. 8.5, Rem. 8.3): Explicit finite-
$N$ Azuma-Hoeffding tail bounds under Dobrushin contraction ($\kappa < 1$ ) and Davis-Kahan$\sin\theta$ bounds when$\nu$ and$\psi$ are estimated from a finite baseline corpus of length$N_0$ .
For the 3-state baseline chain with stationary law
| Process / Law | Entropy Rate (bits) |
|
Fiedler Defect |
|
Finite Window Mean ( |
|---|---|---|---|---|---|
| Baseline |
|
||||
| Local Jitter (scale |
|
|
|||
| i.i.d. on Cut |
|||||
| Rare-Cut Alternation |
|||||
| i.i.d. One-Sided |
|||||
| Constant State |
Notice rows 3 and 5: both have entropy rate 1 bit and transport cost {0,1}) fails to carry the baseline Dirichlet energy and is penalized from 0.054) sits an order of magnitude below every structured deviation.
The C99 library separates corpus fitting from online sliding-window ingestion so that per-event updates run in constant time with zero heap allocations:
-
Zero
malloc/free: All state lives inside a caller-allocatedergodev_ctx_tstruct (~34 KB default footprint), suitable for ring-0 callbacks, eBPF user-space ring consumers, or embedded telemetry daemons. -
$O(1)$ Per-Symbol Ingestion (ergodev_push): Pushing a new symbol updates the base$m$ rolling word index, increments the incoming$\ell$ word counter, decrements the outgoing$\ell$ word counter from$N$ ticks ago, and updates the rolling Fiedler Dirichlet energy via two LUT lookups in < 10 CPU cycles. -
Stack-Only
$W_1$ Evaluation (ergodev_score_sinkhorn): Evaluates entropic optimal transport over the$m^\ell$ word space on demand without dynamic memory allocation.
Evaluating on a 10,000,000-event stream (query stride = 16 ticks) across window lengths
-
ergodev_push_fast()is 100% integer-only (zero FPU instructions): Transition indexing uses a precomputed 1-cycle state lookup table (step_lut), and ring-buffer updates use pure integer increments—making per-event ingestion safe for ring-0 / kernel contexts withoutXSAVE/FXSAVEFPU state-save overhead and completely immune to floating-point rounding drift. -
Constant
$O(1)$ latency (~2.7–3.4 ns / event): throughput stays in the 290–370 million events/sec range on a single core and does not degrade as the window horizon N grows from 128 to 16,384.
=======================================================================================
LIBERGODEV STREAMING BENCHMARK: 10,000,000 Events (Query Stride = 16 ticks)
=======================================================================================
Window N | Method | Throughput | Latency | Relative Speed
---------------------------------------------------------------------------------------
N = 128 | Naive Window Rescan | 205.9 M/s | 4.86 ns | [####### ]
N = 128 | libergodev O(1) Ring | 291.8 M/s | 3.43 ns | [########## ] (1.4x faster)
---------------------------------------------------------------------------------------
N = 512 | Naive Window Rescan | 78.6 M/s | 12.73 ns | [## ]
N = 512 | libergodev O(1) Ring | 348.1 M/s | 2.87 ns | [############ ] (4.4x faster)
---------------------------------------------------------------------------------------
N = 2048 | Naive Window Rescan | 21.6 M/s | 46.27 ns | [# ]
N = 2048 | libergodev O(1) Ring | 351.7 M/s | 2.84 ns | [############ ] (16.3x faster)
---------------------------------------------------------------------------------------
N = 8192 | Naive Window Rescan | 5.5 M/s | 181.94 ns | [# ]
N = 8192 | libergodev O(1) Ring | 340.8 M/s | 2.93 ns | [########### ] (62.0x faster)
---------------------------------------------------------------------------------------
N = 16384 | Naive Window Rescan | 2.7 M/s | 363.82 ns | [# ]
N = 16384 | libergodev O(1) Ring | 372.5 M/s | 2.68 ns | [############# ] (135.5x faster)
---------------------------------------------------------------------------------------
# 1. Build the C99 shared library, static archive, and self-test binary
make
# 2. Run both the C99 streaming self-test and Python exact primal-dual verifier
make check├── Makefile # Builds C99 library, runs tests, compiles LaTeX PDF
├── README.md # Overview and quick-start guide
├── SYMBOLIC_ERGODEVIATION.md # Full Markdown mathematical specification
├── docs/
│ └── symbolic_ergodeviation.pdf # Manuscript
├── include/
│ └── ergodev.h # Zero-allocation C99 API header
├── src/
│ └── ergodev.c # O(1) ring-buffer engine + built-in self-test
└── python/
└── verify_es.py # Exact rational primal-dual verifier & Monte Carlo suite