PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic Causal Quantization with Representative States and Bounded Error

Rama Cont, Massoud Heidari

arXiv:2610.35933v1cs.ITmath.ITmath.PR

TL;DR

The paper studies how closely deterministic causal quantizers with pathwise bounded error can approach the least entropy rate of admissible block quantizers. It analyzes representative-based coding through geometric overlap and Fisher-information bounds, showing universal comparisons and sharper grid and source-matched results.

  • Problem

    The paper asks how close the address entropy rate of a causal, pathwise bounded-error quantizer can come to the least rate allowed by the same error constraint.

    Source: §1.1 · p. 3

  • Method

    It analyzes representative-state quantizers, relating their address entropy to block benchmarks through geometric overlap and Fisher-information estimates.

    Source: §6 · p. 37

  • Results

    With separated initialization, the address rate is at most 2 bits per sample above process ε-entropy, while lattice initialization sharpens the comparison to 1 bit and a Fisher-information bound.

    Source: §6 · p. 37

  • Takeaways & Limitations

    Uniform grids provide universal rate certificates, while source-matched non-lattice representatives can attain rates that same-width uniform grids miss.

    Source: §6 · p. 37

    The separation assumption cannot be dropped from a process comparison bound that is uniform in capacity.

    Source: §5.2 · p. 19

Abstract

from arXiv · show

We study deterministic causal quantization with pathwise error at most $\varepsilon$, using $\omega$ shared representatives updated from transmitted addresses alone. For a midpoint realization with first-in, first-out replacement, we compare address entropy rates with process $\varepsilon$-entropy, the least entropy rate of any block quantizer meeting the same constraint. From $\varepsilon$-separated initialization, the gap is at most two bits per sample for every stationary source with finite scalar $\varepsilon$-entropy, without density, independence or mixing assumptions. A causal address-tree argument extends this comparison to any synchronized quantizer with cell overlap $m$, giving $\log_2 m$ bits. Lattice initialization with consistent boundary ownership realizes uniform grids with sharp one-bit scalar and process comparisons. Under an entropy condition and finite Fisher information rate $J$, the gap is at most $2J\varepsilon^2/(\pi^2\ln 2)$; general initializations add a term of order $\omega\varepsilon\sqrt{J}$. The scalar grid estimate gives a nonasymptotic form of R\'enyi's theorem. Since a grid is causal, the price of causality is at most $\min\{1,2J\varepsilon^2/(\pi^2\ln 2)\}$ bits per sample, versus the high-resolution squared-error loss $\tfrac12\log_2(\pi e/6)$. These bounds certify $\varepsilon$-entropy brackets for autoregressive Laplace and Gaussian sources. For memoryless sources, the optimal causal rate equals the scalar $\varepsilon$-entropy. For a stationary process on finitely many $2\varepsilon$-separated centers, adding independent uniform noise of width $2\varepsilon$ gives exact Shannon lower-bound equality at every block length, attained by storing those centers. This includes histograms with finitely many bins. Storing two non-lattice centers beats every uniform grid of the same cell width by half a bit per sample.

1 Introduction

The introduction frames deterministic causal quantization as pathwise bounded-error coding with shared representative states, and compares its address entropy with scalar and process ε-entropy. It presents midpoint replacement, overlap-based universal bounds, sharper lattice and Fisher-information certificates, and source-matched geometries that can attain the entropy floor.

1.1 Deterministic quantization with bounded error

  • MRR uses representative-centered proximity cells and anchored refinement cells, inserts each refinement midpoint, and replaces the oldest representative while preserving pathwise fidelity and address-only synchronization.The system compares address entropy with scalar and process benchmarks, including the least causal rate when block entropy coding is allowed.Source: §1.1 · p. 3, §1.2 · p. 4

1.3 Two-bit and one-bit comparisons without distributional assumptions

  • With ε-separated initialization, MRR's address rate is at most 2 bits per sample above process ε-entropy for stationary sources with finite scalar ε-entropy, without density, independence, or mixing assumptions.A causal address-tree argument extends the comparison to synchronized systems with cell overlap m, with a log2 m-bit bound.Source: §1.3 · p. 4
  • Every uniform grid of spacing 2ε has sharp scalar and process entropy comparisons within 1 bit, uniformly over capacity and grid origin.Consistent boundary ownership makes the adaptive address string causally equivalent to the fixed-grid index string.Source: §1.3 · p. 4

1.4 Fisher-information bounds and grid certificates

  • With finite Fisher information rate J and mild entropy conditions, the process-rate gap is bounded by 2Jε^2/(π^2 ln 2); lattice alignment also yields a nonasymptotic scalar form of Rényi's theorem.The scalar grid estimate holds for every positive spacing and grid offset.Source: §1.4 · p. 5
  • A causal uniform-grid code has price at most min{1, 2Jε^2/(π^2 ln 2)} bits per sample, while for independent inputs the scalar ε-entropy is the optimal causal rate.The paper also gives ε-entropy brackets for autoregressive Laplace and Gaussian sources.Source: §1.4 · p. 5

1.5 Exact attainment and the role of geometry

  • For stationary processes on finitely many 2ε-separated centers with independent uniform noise of width 2ε, storing the centers attains the Shannon lower bound at every block length.This includes finite-bin histograms; lattice-aligned centers can be handled at any positive capacity.Source: §1.5 · pp. 5–6
  • For the specified two-center i.i.d. source, capacity-two MRR attains 1 bit per sample, while every uniform grid of width 2ε requires at least 3/2 bits per sample.The centers are non-lattice, and the comparison allows every grid offset and optimal block entropy coding.Source: §1.5 · p. 6

1.6 Representative dynamics and rate formulas

  • For i.i.d. inputs, block entropy decomposes into state-conditional address entropies; convergence of averaged state laws yields a rate formula under the limiting invariant law.The representative process has a Feller property under bounded, atomless independent inputs.Source: §1.6 · p. 6

2 Finite-resolution reconstruction systems

A finite-resolution reconstruction system pairs a shared representative state with a value projection, reconstruction scheme, and update operator. Its axioms constrain capacity, distinctness, deterministic evolution, and replacement; fidelity and decoder compatibility ensure pathwise accuracy and address-based synchronization.

2 Finite-resolution reconstruction systems

  • A representative state is an ω-element set of value-timestamp pairs with values and timestamps separately pairwise distinct.Ordering the values identifies the state geometry for the system's measurable structure.Source: §2 · pp. 6–7

2.1 Ingredients

  • A system consists of a representative state, its value projection, a reconstruction scheme on a countable address alphabet, and an update operator.The shared state evolves from the current state and input; reconstruction and the next state are determined by the current shared state and emitted address.Source: §2 · p. 7, §2.1 · p. 7, §2.3 · p. 8

2.2 Axioms

  • The structural axioms require exactly ω representatives, pairwise-distinct representative values and timestamps, and one autonomous update map without an external time index or unrecorded observations.An update either leaves the state unchanged or replaces one representative-timestamp pair while preserving the state axioms.Source: §2.2 · pp. 7–8

2.3 Fidelity and decoder compatibility

  • The scheme must be ε-faithful and decoder-compatible, so reconstruction and the next state can be recovered from the current shared state and emitted address.These conditions constrain reconstruction and update without changing the four structural axioms.Source: §2.3 · p. 8

3 Midpoint Representative Realization

MRR builds a bounded-error partition from shared representatives: proximity cells use stored values, while uncovered gaps use anchored midpoint cells and FIFO replacement. Its construction is pathwise faithful and decoder-synchronized; bounded atomless inputs also yield compact age-ranked dynamics.

3.1 Construction

  • MRR assigns points within ε of a representative to its proximity cell and divides uncovered gaps into anchored cells of width at most 2ε, reconstructed at their midpoints.On refinement, it inserts the midpoint and removes the oldest representative.Source: §3.1 · p. 8

3.2 Well-posedness and separation

  • Every address cell has positive length at most 2ε, so MRR satisfies the pathwise error bound for every input sequence.Refinements insert values more than ε from every value in the preceding state.Source: §3.2 · pp. 9, 11
  • From an ε-separated initialization, all geometries remain ε-separated; after ω refinements, every pair of current representatives is more than ε apart.The insertion trace evicts initial representatives in timestamp order, then proceeds in insertion order.Source: §3.2 · p. 11

3.3 Synchronization and local stability

  • The decoder recovers reconstructions and states from the shared initial state and emitted addresses, and finite-time reachable states are countable.Inputs perturbed within each address cell's margin retain the same addresses, reconstructions, and states through the finite horizon.Source: §3.3 · p. 12
  • A replacement affects at most three gaps of the original geometry, but deleting a representative can merge large intervals and need not reduce the maximum gap.Replacement deletes one representative and inserts a new value into a gap of the remaining geometry.Source: §3.3 · p. 12

3.4 Bounded inputs and compact age-ranked dynamics

  • For bounded i.i.d. inputs with a common atomless law, the compact age-ranked process is Feller and has an invariant probability measure, which need not be unique.The state space is invariant under inputs in the specified bounded interval.Source: §3.4 · pp. 12–13
  • With a finite set of possible refinement reconstructions, i.i.d. inputs give a finite-state Markov chain, while periodic deterministic inputs yield eventually periodic states, reconstructions, and addresses.For period p and N possible age-ranked states, preperiod and period are each at most pN.Source: §3.4 · pp. 13–14

4 Minimality of the MRR

The section establishes a sharp four-cell overlap bound for ε-separated geometries, then uses partition overlap to compare MRR address entropy with scalar ε-entropy. Its local cell-count minimality applies only when the prescribed proximity regions are retained.

4.1 Minimality with prescribed proximity regions

  • MRR uses the minimum number of additional cells needed to cover each representative gap outside the prescribed proximity regions, and attains that constrained minimum.The minimality claim depends on retaining those proximity regions and their reconstruction values.Source: §4.1 · p. 14

4.2 Four-cell overlap

  • For ε-separated geometries, every interval of length 2ε meets at most four MRR cells, and the constant four is sharp uniformly over capacities.The supplied example has four distinct addresses within an interval of length 1.62 when ε = 1.Source: §4.2 · p. 15, Figure 2 · p. 16

4.3 Scalar floors at equal conditioning

  • The MRR address entropy is between scalar ε-entropy and scalar ε-entropy plus 2 bits, a sharp comparison that also holds conditionally on a countable variable.The upper bound is sharp for a three-representative geometry and a finitely supported law with scalar floor zero.Source: §4.3 · p. 16

5 Geometric complexity

The section links representative-gap geometry to symbolic entropy and defines the process and causal benchmarks for bounded-error coding. MRR's address strings are faithful reconstructions, so their entropy rate bounds the causal benchmark above the process ε-entropy floor.

5 Geometric complexity

  • At a fixed state, the number and arrangement of reconstruction cells depend on representative gaps, while cell probabilities determine symbolic entropy.The key geometric quantities are rectangular address preimages and the number of short cells per state.Source: §5 · p. 16

5.1 The block benchmark

  • The process ε-entropy is the limiting per-coordinate infimum of block-partition entropy under sup-norm error ε, and the causal floor minimizes rates over causal codes with block entropy coding.The benchmark uses closed error balls; null-probability regions can be covered without changing entropy.Source: §5.1 · p. 17
  • Every MRR address string determines a faithful reconstruction vector, giving process ε-entropy no greater than the address entropy rate, and that rate no smaller than the causal floor.MRR is a causal code because its labels are its addresses.Source: §5.1 · p. 17

5.2 A distribution-free process comparison

A causal address-tree argument turns a one-step cell-overlap bound into a block-entropy comparison. For ε-separated MRR, the four-cell overlap gives a two-bit-per-sample bound without density, independence, or mixing assumptions.

5.2 A distribution-free process comparison

  • If every reachable state has at most m address cells intersecting any closed interval of length 2ε, a faithful block cell intersects at most m^n length-n address cells.The argument bounds the number of possible address extensions at each step of the tree.Source: §5.2 · p. 18
  • For every block law, address entropy is at most block ε-entropy plus n log2(m); ε-separated MRR therefore has a two-bit-per-sample comparison.The bound requires no density, independence, or mixing assumption.Source: §5.2 · p. 18
  • The separation assumption is necessary for a bound uniform in capacity: clustered initial representatives can yield address entropy n log2 ω while the block ε-entropy is zero.For ε = 1, ω distinct initial values in [0, 1] and a source uniform on them give this contrast.Source: §5.2 · p. 19

5.3 Adaptive reconstruction rectangles

Decoder compatibility makes each adaptive address string correspond to a rectangular input region. The exact entropy decomposition separates differential entropy, cell volume, and density variation within those rectangles.

5.3 Adaptive reconstruction rectangles

  • Each valid address string has a rectangular preimage whose side lengths are the selected scalar-cell lengths.After fixing a prefix, the next state is fixed, so the next input must belong to its specified cell; induction gives the product structure.Source: §5.3 · p. 19
  • Proposition 5.3 decomposes address entropy into differential entropy, a cell-volume term, and a relative-entropy term within the rectangles.The stated density, entropy, and log-volume integrability assumptions justify the decomposition.Source: §5.3 · p. 19
  • Both nonnegative terms vanish exactly when every positive-probability rectangle has full side lengths 2ε and the density is almost everywhere constant on each rectangle.The volume penalty vanishes for full-width sides, and relative entropy vanishes when the compared densities agree almost everywhere.Source: §5.3 · p. 19

5.4 A quantitative density estimate

The density estimate controls variation within rectangular quantization cells using Fisher information. A separate expected-volume-loss bound applies when conditional input densities are uniformly bounded.

5.4 A quantitative density estimate

  • The rectangle estimate applies to a positive-probability cell with finite side lengths when √f belongs to H1 on that cell.The comparison is between the conditional law on the rectangle and the uniform law there.Source: §5.4 · p. 20
  • For rectangular partitions with side lengths at most 2ε, the density-to-cell-average discrepancy is bounded using Fisher information.The result assumes √f belongs to H1(R^n); the passages do not provide the displayed bound's formula.Source: §5.4 · p. 20
  • When each conditional density is bounded by M, expected volume loss is controlled using at most mω short cells per state, without a separation assumption.Conditioning on the address prefix preserves the density bound; only short cells contribute to volume loss.Source: §5.4 · p. 21

5.5 Certified approximation to the process floor

The paper bounds the address-rate gap from the process ε-entropy using entropy and Fisher-information conditions, with sharper bounds for lattice initialization. These comparisons also yield certified brackets for an autoregressive Laplace source.

5.5 Certified approximation to the process floor

  • With lattice initialization, full-width cells eliminate the volume term, yielding the Fisher-information comparison uniformly over capacity and grid origin.The bounds also apply when block log densities have uniformly bounded coordinate scores, and can certify an explicit interval for the process floor when entropy and an upper bound on J are known.Source: §5.5 · pp. 21, 24
  • Under the theorem's stationarity, entropy, and finite Fisher-information-rate assumptions, the process-rate comparison gives an upper bound on the MRR-to-floor gap.The general-initialization bound includes a capacity-and-tolerance term; with bounded conditional densities, the volume contribution admits a sharper refinement.Source: §5.5 · pp. 21–23
  • For a fixed source satisfying the stated assumptions, the gap bound tends to zero as ε decreases when ω(ε)ε tends to zero.The capacity–tolerance scaling makes both terms in the bound vanish.Source: §5.5 · pp. 22–23
  • For the autoregressive Laplace source, a lattice-initialized MRR has the stated rate guarantee at every capacity, while arbitrary fixed initialization has a separate guarantee.The example's conditional densities are bounded by 1/(2b), and its marginal Fisher information is at most 1/b^2.Source: §5.5 · p. 24
  • For the autoregressive Laplace example with a = 0.8 and ε/b = 10^-3, the certified process ε-entropy bracket is 11.408479325551 to 11.408479805007 bits per sample.The interval width is less than 4.795 × 10^-7 bits per sample; lattice-initialized MRR lies in the same bracket at every capacity.Source: §5.5 · p. 25

5.6 Invariant lattices and fixed-grid representation

Lattice initialization keeps the representative geometry on a fixed uniform grid, with cells of width 2ε. Consistent boundary ownership makes adaptive addresses equivalent to fixed-grid indices, enabling sharp one-bit comparisons and Fisher-information bounds.

5.6 Invariant lattices and fixed-grid representation

  • Every MRR geometry initialized on the lattice remains there, and every nonempty address cell has length 2ε.The invariant-lattice conclusions hold at every capacity.Source: §5.6 · pp. 25–26
  • For lattice initialization under the stated density and entropy assumptions, the rate gap is bounded by the Fisher-information term because the volume penalty vanishes.These conclusions hold for every capacity.Source: §5.6 · pp. 25–26
  • A fixed grid offset gives a natural benchmark: its entropy differs from the offset-averaged entropy at scale 2ε by at most one bit.Optimizing the offset requires knowledge of the source.Source: §5.6 · p. 26
  • With consistent boundary ownership, the MRR address string and fixed-grid index string determine each other for every input law and block length.For the original boundary rule, the identity holds when inputs almost surely avoid grid boundaries.Source: §5.6 · p. 27
  • The lattice grid entropy is within one bit of the scalar ε-entropy, with corresponding block and process comparisons.The comparison is sharp; the process conclusions apply to consistent-boundary MRR at every capacity and to original MRR under the boundary qualification.Source: §5.6 · pp. 27–28
  • The fixed-grid comparison extends to blocks because each coordinate interval of an admissible block cell meets at most two grid cells.This yields a one-bit-per-coordinate entropy comparison with the process ε-entropy.Source: §5.6 · p. 28
  • The price of causality is bounded by the smaller of one bit and the Fisher-information term under the stated assumptions.The comparison is for lattice-initialized MRR and stationary sources.Source: §5.6 · p. 28
  • The boundary condition is essential for the one-bit comparison with the original MRR: with ε = 1, ω = 1, and R0 = {0}, uniform X on {1, 2, 3} has H(S1) = log2 3 while F1(µ) = 0.Source: §5.6 · p. 28

5.7 Exact and near-exact floor evaluation

For separated centers with independent uniform within-cell noise, the scalar and process floors can equal the Shannon lower bound, with MRR attaining them under specified initializations. The section also gives exact grid comparisons and a non-lattice example that beats every fixed grid offset.

5.7 Exact and near-exact floor evaluation

  • For stationary center indices with independent uniform noise on [−ε, ε), the scalar and process floors equal their respective Shannon lower bounds, and MRR attains the process floor under either specified initialization.Finite non-lattice center sets can be stored when capacity equals the number of centers; lattice centers can use any positive capacity with lattice initialization.Source: §5.7 · pp. 29–31
  • Histograms with bin width 2ε and finite bin entropy attain the scalar Shannon lower bound; for independent samples this is also the process floor, attained by lattice-initialized MRR at every block length.The same initialization attains the process floor for stationary dependent bin indices under the stated independent within-bin noise assumptions.Source: §5.7 · p. 31
  • A capacity-two non-lattice geometry attains a one-bit rate, while every fixed grid offset has entropy at least 1.5 bits per sample, even with block entropy coding.At offset zero the grid entropy is 1.5 bits; the non-lattice construction stores centers 0 and 5ε.Source: §5.7 · p. 32
  • The two centers 0 and 5ε form the unique absorbing capacity-two geometry and a strict local minimizer of one-step address entropy, but this does not establish convergence from arbitrary initializations.The geometry is isolated among local one-step entropy minimizers, not in the ambient state space or among asymptotic-rate minimizers.Source: §5.7 · pp. 32–33

The process floor satisfies the certified bracket

  • For an independent Laplace source with ε/b = 10^-3, the certified process ε-entropy bracket is 11.408479325551 to 11.408479565820 bits per sample, narrower than 2.403 × 10^-7 bits per sample.The bound follows from the Shannon lower bound and the exact achievable MRR rate.Source: The process floor satisfies the… · pp. 33–34
  • For stationary autoregressive Gaussian inputs, the section derives a certified process-floor bracket from the model’s Fisher information; when a = 0, the stated gap term is 2ε^2/(π^2σ^2 ln 2).The model assumes |a| < 1 and independent Gaussian innovations with variance σ^2.Source: The process floor satisfies the… · p. 34

5.8 I.i.d. inputs and invariant state laws

For independent inputs, MRR block entropy is governed by the expected one-step address entropy at the current state. This yields scalar-floor rate bounds and, when averaged state laws converge, a rate formula based on their limiting occupation law.

5.8 I.i.d. inputs and invariant state laws

  • For i.i.d. inputs, the address-block entropy equals the sum of expected one-step address entropies conditioned on the current age-ranked state, even when the state process is not stationary.The address history and current input are independent, so conditioning on the history gives the same address probabilities as conditioning on the state.Source: §5.8 · p. 35
  • For independent inputs with common law µ, the causal floor equals the scalar ε-entropy, and MRR from an ε-separated initialization is within two bits per sample of that floor.With lattice initialization and consistent boundary ownership, the upper gap improves to one bit.Source: §5.8 · pp. 35–36
  • If the averaged state laws converge, the normalized block entropy converges to the one-step address entropy integrated against their limiting invariant law.A unique invariant probability measure on the stated compact state set is one sufficient condition for convergence.Source: §5.8 · pp. 36–37
  • The state-conditional entropy identity depends on input independence; for dependent inputs, conditioning on the current state can discard predictive information in the address history.Existence of an invariant state law alone does not guarantee convergence of state laws or their averages.Source: §5.8 · p. 37

6 Discussion

The discussion relates representative geometry to scalar and process entropy comparisons, while distinguishing universal bounds from source-matched gains and implementation limits. It also identifies conditions for rate convergence and questions left open.

Discussion

  • Finite Fisher information controls both density variation within reconstruction rectangles and volume loss from short proximity and remainder cells.Lattice alignment removes the volume-loss term; a uniform bound on one-step conditional densities is needed only for an optional refinement.Source: §6 · p. 37
  • Lattice alignment yields a sharp one-bit scalar comparison and process bound (5.42), uniformly over capacity and grid origin.For a fixed source satisfying the stated Fisher-information and entropy assumptions, the rate gap vanishes as ε decreases, even if capacity grows without restriction.Source: §6 · p. 37
  • Two stored non-lattice centers attain 1 bit per sample, while every fixed width-2ε grid requires at least 3/2 bits per sample.The comparison uses the best grid offset and optimal block entropy coding.Source: §6 · p. 37
  • The two-center attaining state is absorbing, so this comparison establishes neither a benefit of FIFO adaptation nor convergence from arbitrary states.The unordered absorbing geometry is unique and a strict local minimizer of one-step address entropy, but is not isolated; universal upper bounds also do not imply monotonic actual rates.Source: §6 · pp. 37–38
  • For i.i.d. inputs, normalized block entropy equals averaged state-conditional address entropy; under compact Feller hypotheses, subsequential limits are integrals against invariant occupation laws.Convergence of averaged laws can yield a rate limit, but an invariant measure alone does not imply convergence; with dependent inputs, the state can discard predictive information in address history.Source: §6 · p. 38
  • The representative capacity bounds stored values, not their bit representation, timestamp size, or entropy-coder memory; address block coding can exploit dependence beyond the state.A coding implementation with specified memory and delay requires separate analysis.Source: §6 · p. 38
  • The Fisher-information estimate covers unbounded Gaussian scores at finite tolerance, while further questions include weaker density conditions and quantitative state convergence.The discussion also raises replacement rules that directly control expected cell-volume loss.Source: §6 · p. 38

A Certified evaluation of the entropy floor

The evaluation formulates the scalar entropy floor through admissible source-value sets and an interval-incidence representation. It gives a certified optimization procedure and an example separating scalar and process floors.

A Certified evaluation of the entropy floor

  • For i.i.d. finite-alphabet inputs, admissible reconstruction sets are independent sets of the graph connecting values more than 2ε apart; block cells correspond to independent sets in the disjunctive graph power.This identifies the partition benchmark with chromatic entropy, whose asymptotic characterization applies to the graph formulation [AO96].Source: A Certified evaluation of the entropy… · p. 40
  • Maximal admissible sets are consecutive index intervals, and sorting with a moving right endpoint enumerates candidates in an interval-incidence representation of size at most N^2.Contained candidates are then removed.Source: A Certified evaluation of the entropy… · p. 40
  • The alternating-minimization objective converges to (A.2), and log2 c(q(k)) certifies optimization error at each iteration [HNB24].Rigorous numerical certification requires outward rounding at both endpoints in (A.4); an unrounded optimizer output alone is insufficient.Source: A Certified evaluation of the entropy… · p. 41
  • For the uniform source on {0, 1, 2} with ε = 0.6, q = (1/2, 1/2) gives U(q) = 2/3 and c(q) = 1; the process floor is 2/3, while the scalar floor exceeds it by about 0.252 bit per sample.The scalar value is h2(1/3), since a scalar cell must separate 0 and 2; the optimal causal rate equals the process floor.Source: A Certified evaluation of the entropy… · p. 41
Loading 2610.35933v1…