8c9a374Unbiased Monte-Carlo entropy estimation for quantized filtered Gaussian seriesJeremy Magland 1# timeseries-entropy
3Unbiased Monte-Carlo estimation of the entropy of a quantized filtered
4Gaussian time series:
6 x iid N(0, sigma^2) -> y = h * x -> z = round(y)
8The estimand is the conditional entropy H(z_{M+1} | z_1..z_M) in bits, which
9decreases to the entropy rate of z — the true lossless compression limit in
10bits/sample — as the past window M grows beyond the memory of the process.
41e0ef9Note the hand-synced TypeScript port in timeseries-compressibilityJeremy Magland 12Companion to [timeseries-compressibility](https://github.com/concept-collection/timeseries-compressibility),
13which carries a hand-synced TypeScript port of this estimator in `src/entropy/`
14(run in the browser from a worker) — when changing the algorithm here, change
15it there too.
8c9a374Unbiased Monte-Carlo entropy estimation for quantized filtered Gaussian seriesJeremy Magland 16
17## Method
191. **Stationary conditional sampling.** Draw x from the prior and push it
20 through the pipeline to get a past z_1..z_M. The generating x is an exact
21 draw from p(x | z), so a Gibbs chain started there is already in
22 stationarity — no burn-in bias. Each Gibbs conditional is a box-truncated
23 normal; after each sweep the free tail latent is drawn fresh, emitting one
24 exact sample of z_{M+1}. The samples form a stationary, autocorrelated
25 discrete chain.
262. **Unbiased entropy of the chain's marginal.** Plug-in entropies of blocks
27 whose sizes double per level are combined by Rhee–Glynn randomized
28 telescoping with antithetic half-block corrections
29 Delta_m = h(B_m) - [h(B_m^1) + h(B_m^2)]/2, truncated at a random level N
30 with P(N >= m) = 2^(-r m) and reweighted. The expectation is exactly
31 H(z_{M+1} | that past) despite the plug-in bias at every finite block size
32 and despite the autocorrelation, which affects only the variance.
333. **Average over independent pasts** to get H(z_{M+1} | z_1..z_M) with a
34 valid standard error. The only remaining approximation to the entropy rate
35 is the finite window M.
37## Install
39 pip install -e .
41Requires numpy and scipy.
43## Usage
45```python
46from timeseries_entropy import estimate_conditional_entropy, kernels
48est = estimate_conditional_entropy(kernels.moving_average(8), sigma=4.0)
49print(est.mean, est.se) # bits/sample, over independent pasts
50```
52Lower level: `ConditionalChain(kernel, sigma, past, rng).draw(k)` yields the
53stationary chain of z_{M+1} samples, and `unbiased_entropy(draw, n0, r, rng)`
54is one randomized-telescoping realization for any stationary discrete chain.
56## CLI
58 timeseries-entropy --sigma 4 --filter moving-average --width 8
59 timeseries-entropy --sigma 8 --filter lowpass --high 3000 --rate 30000
60 timeseries-entropy --sigma 2 --filter none --pasts 8
62Filters match the web app: `none`, `moving-average`, `lowpass`, `bandpass`,
63`first-difference`.
65## Tuning
67- `r` (default 1.5) sets the truncation tail P(N >= m) = 2^(-r m). Finite
68 expected work needs r > 1; finite variance needs E[Delta_m^2] to decay
69 faster than 2^(-r m). Run `--pilot 6` to see the RMS Delta_m decay before
70 trusting a value.
71- `n0` (default 128) is the base block size; `thin` inserts extra Gibbs
72 sweeps per emitted sample to cut autocorrelation for slowly mixing
73 (narrowband, large-sigma) settings.
74- `--past` sets M; increase it until the estimate stops moving to approach
75 the rate.