PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal R\'enyi and Logarithmic Additive Functional Entropy Estimation

Arman Adibi, Piotr Krysta

arXiv:2610.28999v1cs.ITcs.CCeess.SPmath.ITmath.STstat.TH

TL;DR

Estimating Rényi entropy when its order varies with alphabet size requires bounds that remain valid near integer and high-order transitions. The paper develops uniform complexity characterizations and extends the analysis to logarithms of additive functionals. It establishes order-dependent rates and shows that a finite leading power determines the alphabet dependence for the stated class of functionals.

  • Problem

    A sample may not reveal most small probabilities even when it captures their aggregate entropy contribution, and existing Rényi results do not give noninteger transition bounds uniformly near one or an integer.

    Source: §1 · p. 3

  • Method

    The paper combines count and likelihood identities with weighted approximation duality, then uses a transfer theorem for functions with a finite leading power at zero.

    Source: §1 · p. 3, §3 · p. 6

  • Results

    For fixed functions with f(x) ∼ ax^r, logarithmic additive estimation has rate Θ(k^(1−1/r)) for integer r and Θ(k/log k) for noninteger r.

    Source: §2.2 · p. 6

  • Takeaways & Limitations

    For logarithmic additive functionals in the stated class, the leading power at zero determines the alphabet dependence without requiring differentiability.

    Source: §1 · p. 3

    The functional rate theorem fixes the function, its leading exponent, and the accuracy; it does not claim uniform constants over changing functions or orders.

    Source: §2.2 · p. 6

Abstract

from arXiv · show

We characterize the minimax sample complexity of estimating R\'enyi entropy from independent samples on an alphabet of size at most $k$, when the known order $\alpha>1$ may vary with $k$. For every fixed additive accuracy $\varepsilon\in(0,1/2)$ and success probability $2/3$, we prove matching bounds with constants independent of $k$ and $\alpha$. For $1<\alpha<\log k$, the rate is $\Theta_\varepsilon(\alpha k^{1-1/\alpha}X_\alpha(k,\varepsilon))$, where a monotone scalar inequality defines $X_\alpha$ at noninteger orders. The bounds remain uniform as the order approaches one or an integer, or grows with the alphabet. Integer orders below $\log k$ have rate $\Theta_\varepsilon(\alpha k^{1-1/\alpha})$; orders at least $\log k$ and min-entropy have rate $\Theta_\varepsilon(k\log k)$. We extend the analysis to logarithms of positive additive functionals. For every fixed continuous $f$ satisfying $f(0)=0$, $f(x)>0$ for $x>0$, and $f(x)\sim ax^r$ at zero, with $a>0$ and $r>1$, estimating $-\beta^{-1}\log\sum_i f(p_i)$ at fixed accuracy, for fixed $\beta>0$, has sample complexity $\Theta(k^{1-1/r})$ for integer $r$ and $\Theta(k/\log k)$ otherwise. A replication reduction preserves the sampling experiment and transfers the rates for powers. Smooth flat functions show that regularity alone does not determine the complexity. The upper bound combines polynomial approximation, Gamma count statistics, and an independent pilot, with a global affine correction near order one. The lower bound uses interpolation to construct positive mean-one priors and controls their distinguishability and entropy separation after normalization. Exact count-variance identities and weighted approximation duality connect the two arguments.

1 Introduction

The introduction frames Rényi entropy estimation as a problem of uniform sample-complexity bounds when the order varies, and extends the analysis to logarithms of additive functionals. It positions the work against prior entropy-estimation results and identifies uniformity near changing orders as an unresolved issue.

1 Introduction

  • The paper gives matching sample-complexity bounds for every real order, with a scalar root capturing distance to adjacent integers and requested accuracy.The characterization includes the collision scale at integer orders, k log k at large orders, and k/log k at fixed noninteger orders.Source: §1 · p. 3
  • For fixed f(x) ∼ ax^r, the leading power determines the alphabet dependence of logarithmic additive-functional estimation under continuity and positivity alone.The reduction retains its accuracy loss explicitly.Source: §1 · p. 3

1.1 Prior work and the remaining uniformity question

  • The paper develops count-variance and likelihood identities, weighted approximation duality, and conditions needed to turn these tools into statistical bounds.Its functional conclusions address logarithmic accuracy without differentiability under the finite-leading-power assumption, unlike the squared-error setting of Fukuchi and Sakuma [FS18].Source: §1 · p. 3, §1.1 · p. 4
  • Valiant and Valiant established Θ(k/log k) for Shannon entropy, while Acharya et al. [AOST17] identified the integer/noninteger Rényi distinction and Obremski and Skorski refined Rényi bounds.Adibi and Krysta [AK26] obtained matching bounds for growing integer orders and min-entropy; prior results did not provide uniform noninteger transitions near one or integers.Source: §1.1 · p. 3

2 Models and main results

The section states a uniform sample-complexity characterization for Rényi entropy and gives corresponding rates for logarithms of positive additive functionals. The rates distinguish integer from noninteger orders and leading powers, with scope and accuracy conditions stated for each result.

2.1 A rate uniform over all real orders above one

  • The noninteger-order scalar root retains dependence on the distance to adjacent integers and requested accuracy, and its defining function is monotone.The constants are chosen before k and α; replacing ε by a constant fraction can change the rate.Source: §2.1 · pp. 4–5
  • At fixed noninteger α, the rate is Θ_α,ε(k / log k), while integer orders below log k have rate Θ_ε(αk^(1−1/α)).For orders at least log k and for min-entropy, the rate is Θ_ε(k log k).Source: §2.1 · p. 5
  • Theorem 2.1 gives matching Rényi sample-complexity bounds with constants depending only on ε, uniformly over alphabet size k and real order α > 1.The rate uses a scalar root for noninteger orders; integer and high-order cases use separate branches.Source: §2.1 · p. 5

2.2 Logarithmic additive functionals

  • For fixed continuous positive f with f(0)=0 and f(x) ∼ ax^r at zero, logarithmic additive estimation has rate Θ(k^(1−1/r)) for integer r and Θ(k / log k) otherwise.The result assumes fixed f, leading exponent r, scale β_f, and accuracy; it requires no differentiability.Source: §2.2 · pp. 5–6
  • The functional rates follow from a reduction that preserves the sampling experiment while incurring an explicit deterministic accuracy loss.The theorem does not claim uniform constants over changing functions or orders.Source: §2.2 · p. 6

3 The general functional framework

The framework separates approximation error, sampling noise, and statistical indistinguishability through count and approximation identities. For logarithmic targets, it gives an exact accuracy threshold and a matching weighted approximation duality.

3 The general functional framework

  • In the Poisson experiment, polynomial approximation controls estimator bias while derivatives control its noise.The exact count-variance identity includes cross terms; a polynomial’s linear term can be replaced globally by its known aggregate, which matters near order one.Source: §3 · p. 6
  • For positive F, bounding estimator bias and variance relative to F certifies logarithmic error ε with failure probability at most ζ.The threshold uses η=tanh(βε), and the logarithmic half-width is exactly βε.Source: §3 · p. 6
  • Weighted approximation duality converts approximation error d into matched moments and a target-expectation ratio (1+d)/(1−d).At d=tanh(βε), this corresponds exactly to logarithmic separation 2ε.Source: §3 · p. 7
  • The sampling identity compares independent Poisson counts with means ν_eθ_e against a positive reference θ∗ through likelihood ratios.The framework treats deterministic approximation, sampling noise, and statistical indistinguishability as separate obligations.Source: §3 · pp. 6–7
  • Reference variance and separated prior expectations alone do not ensure uniform variance bounds or concentration of the realized target.Those properties are verified separately in the i.i.d. proof.Source: §3 · p. 7

4 Proof of the uniform i.i.d. theorem

The proof develops the i.i.d. upper bound by fitting an estimator into an exact target interval while leaving room for random fluctuations. Its noninteger-order construction uses main counts, an independent pilot, and a calibrated approximation margin.

4.1 Upper bound: approximation with a sampling margin

  • The noninteger estimator must lie in an exact target interval, with positive margins at both ends so random fluctuations do not consume the approximation tolerance.The proof introduces the construction and its quantitative obligations before giving complete proofs in the appendices.Source: §4.1 · p. 7, §4 · p. 7
  • For noninteger 3/2 ≤ α < log k, the estimator uses main and independent pilot Poisson counts with n=Dαk^(1−1/α)X.Here X is the root-defined multiplier, and auxiliary parameters are calibrated using the order and accuracy.Source: §4.1 · p. 7
  • A two-arm envelope selects a lower cutoff and deterministic tolerance, with root calibration ensuring a ≤ c_εβ/(αk).The tolerance is reduced to preserve room for sampling error.Source: §4.1 · p. 7

Appendix D.4 constructs an explicit polynomial Q(x) = Pd

The proof combines polynomial and count-based estimators for upper bounds with positive-prior testing constructions for lower bounds. It then assembles the regime-specific bounds into a uniform characterization and derives the fixed-noninteger rate.

Appendix D.4 constructs an explicit polynomial Q(x) = Pd

  • Reversing one endpoint profile makes its fractional power cancel against p^α, yielding ordinary polynomials in p.For larger probabilities, the method uses an analytic Gamma count transform whose small-count values can be signed and must be included in the error analysis.Source: Appendix D.4 · pp. 7–8
  • The upper-bound budgets can be chosen using ε alone to meet the target interval with probability at least 3/4, uniformly over p and noninteger 3/2 ≤ α < log k.The argument allocates error control across polynomial noise, the global linear replacement, pilot classification, and heavy-count concentration.Source: Appendix D.4 · p. 8
  • For integer orders 2 ≤ r < log k, the estimator uses the factorial-count statistic n^(−r)Σ_i(N_i)_r, whose mean is P^r.The proof controls variance by splitting coordinates according to whether np_i exceeds a multiple of r and bounding both tails.Source: Appendix D.4 · p. 8
  • At α ≥ log k, simultaneous count bounds at n=C_εk log k support estimates of Rényi entropy and min-entropy.A nonnegative capped-order Gamma transform and an ℓ_α norm bound estimate H_α; the maximum coordinate estimates min-entropy.Source: Appendix D.4 · p. 9

4.2 Lower bound: positive priors and observable counts

  • Interpolation and parity splitting construct genuine mean-one priors U0 and U1 supported on {0} ∪ [1,B].Their integer moments match through the selected degree, except possibly at the integer nearest α; their first moments always match exactly.Source: §4.2 · p. 9
  • The lower bound controls separation after normalization and bounds the mixed-Poisson mixture distance using matched moments and actual prior atoms.The extra margin absorbs normalization fluctuations, including near order one; Theorem G.7 gives a testing contradiction at n ≍_ε R_α.Source: §4.2 · pp. 9–10

4.3 Completion for general real order

  • Theorem 2.1 follows by combining the regime-specific upper and lower bounds with constants and alphabet cutoffs depending only on ε.For fixed noninteger α, the root criterion gives X ≍_α,ε k^(1/α)/log k and R_α ≍_α,ε k/log k.Source: §4.3 · p. 10

5 Why the leading power determines the functional rate

This section studies estimation of logarithms of positive additive functionals with a finite leading power, using replication to transfer power-sum rates and Poisson-count methods to develop and analyze estimators. It also connects likelihood overlap to distinguishing moment-matched alternatives and illustrates order-two estimation with an unbiased collision-probability estimator.

5 Why the leading power determines the functional rate

  • For integer r, the logarithmic functional has rate Θ(k^(1−1/r)); for noninteger r, its rate is Θ(k/log k), and smooth flat functions show regularity alone does not determine complexity.The reduction uses fixed replication, preserving the sampling experiment and changing these rates by at most a constant factor; auxiliary sample cost is constant.Source: §5 · p. 10

A.1 Poissonization and factorial counts

  • Independent Poisson counts have Ni ∼ Poi(npi), and factorial counts (Ni)j/nj estimate pj without bias.Fixed-size sampling instead uses denominator (N)j; Poissonization can be implemented from a fixed pool with overflow controlled by coupling.Source: §A.1 · p. 11

A.2 From a polynomial approximation to a count estimator

  • Replacing polynomial powers by factorial counts yields an estimator whose mean is the approximating polynomial, with explicit variance governed by its derivatives.For Q(x)=x^2, the identity recovers the collision variance terms 4P3/n and 2P2/n2.Source: §A.2 · p. 12

A.3 Why power-sum accuracy must be calibrated before taking a logarithm

  • A power-sum estimate must be calibrated to a positive relative-error interval before taking its logarithm, yielding ε accuracy for −β−1 log F.The symmetric interval uses η=tanh(βε), and the argument applies to positive additive sums and pilot-based statistics.Source: §A.3 · pp. 12–13

A.4 Extending factorial counts to real powers: the nonnegative transform

  • For real s≥1, Gamma-ratio count transforms extend factorial counts: integer orders are unbiased, while noninteger transforms are downward biased with bias diminishing for frequent symbols.Taking an sth root gives a count-scale quantity within s of the count.Source: §A.4 · p. 13

A.5 An analytic count extension with exact order-one cancellation

  • The analytic signed count transform depends continuously on order, agrees with falling factorials at integer orders, and retains uniform β² variance cancellation near order one.Its bias is bounded by Cβe−λ/λ; the result applies for 0<β≤1/2 and λ≥1.Source: §A.5 · pp. 14–16
  • For frequent counts at noninteger orders, negative transform values have an exponentially small correction, while a count floor at least the order makes signed and nonnegative transforms agree.At integer orders, the transforms have no negative values.Source: §A.5 · pp. 16–17

A.6 The likelihood-overlap identity used in the lower bounds

  • The lower-bound subsection introduces χ² divergence for likelihood ratios and begins relating it to total variation.The supplied passage does not include the remainder of the likelihood-overlap identity.Source: §A.6 · p. 17
  • A small second moment of a mixture likelihood ratio makes the mixture difficult to distinguish from the reference law, and the same count kernel explains why moment matching hides differences from data.The kernel evaluates overlap for independent Poisson observations and yields a weighted squared difference between mixed Poisson count probabilities.Source: §A.6 · pp. 17–18

A.7 The order-two example

  • With a Poisson number of observations of mean n, symbol counts are independent with N_i distributed as Poi(np_i).The text notes that Section A explains the reduction and return to a fixed sample size.Source: §A.7 · p. 19

A.7.1 An unbiased estimator of the collision probability

  • The factorial-count estimator based on N_i(N_i − 1) is unbiased for the collision probability P2(p), the probability that two independent observations agree.The product counts ordered pairs of distinct observations of symbol i; subtracting N_i removes the extra n p_i bias in N_i^2.Source: §A.7.1 · p. 19

A.7.2 Its exact variance and a uniform sample bound

The section uses count identities to estimate entropy through an aggregate collision statistic rather than estimating individual probabilities. The example motivates direct estimation of sums and explains why noninteger orders require polynomial approximation with variance control.

A.7.2 Its exact variance and a uniform sample bound

  • For a Poisson count with mean λ, Var((N)2) = 4λ3 + 2λ2, giving an explicit variance calculation for the collision statistic.Independence across symbol counts lets the coordinate variances be combined.Source: §A.7.2 · p. 19
  • The collision-probability estimate yields an entropy estimate, and Poissonization can be implemented from a fixed pool with exponentially small overflow probability.The passages state that a hidden-coordinate argument supplies a matching lower bound, but do not show its rate here.Source: §A.7.2 · p. 19
  • The collision statistic estimates the probability sum directly, avoiding the need to estimate each symbol probability accurately.For noninteger orders, finite polynomials cannot represent x^α exactly, so polynomial approximation must be paired with variance control.Source: §A.7.2 · p. 19

B A direct proof for every integer order

For integer orders, ordered collisions give a nonnegative unbiased estimator of the power sum, which can be used without identifying rare and frequent symbols. When the order grows, the entropy guarantee permits a wider multiplicative interval than a constant relative-variance bound would allow.

B A direct proof for every integer order

  • Ordered collisions give a nonnegative unbiased estimator of the power sum without requiring knowledge of which symbols are rare or frequent.The rare/frequent partition is used only to analyze the estimator’s lower tail.Source: B A direct proof for every integer order · p. 20

B.1 Why a constant relative-variance bound is too restrictive

  • For growing integer order, entropy accuracy requires only that the estimated power sum lie in a multiplicative interval, which widens with the order.Taking logarithms and dividing by r −1 converts this interval condition into an entropy error bound.Source: §B.1 · p. 20
  • Relative variance can diverge as r grows even when the entropy guarantee remains attainable; the proof controls the upper tail by a second moment and the lower tail by positivity and weighted Jensen.The example uses n = Drk1−1/r.Source: §B.1 · p. 20

B.2 The estimator and the uniform guarantee

For integer orders, a raw collision estimator achieves the order-uniform upper rate below the high-order threshold. For orders at least log k, a capped-order count transform achieves the O(k log k) rate for Rényi entropy and min-entropy.

B.2 The estimator and the uniform guarantee

  • The integer-order guarantee holds uniformly over distributions, and a fixed pool of ⌈2n⌉ iid observations achieves success probability at least 2/3.The estimator first obtains independent Poisson counts; the fixed-sample conversion adds a Poisson-tail failure probability.Source: §B.2 · pp. 20, 22
  • Oε(rk^(1−1/r)) samples suffice for every integer r ≥ 2 using the same raw collision estimator.Its constant is independent of r and k; this argument does not claim the raw estimator attains the saturation rate when r ≫ log k.Source: §B.2 · pp. 20, 22

C.1 Why the upper bound saturates at high orders

  • For α ≥ max{2, log k}, a capped-order count transform estimates Rényi entropy and min-entropy with Oε,δ(k log k) samples.The proof controls each empirical coordinate to relative-plus-1/k accuracy, then bounds the ℓα norm or maximum.Source: §C.1 · p. 23

C.2 One hidden-coordinate calculation for the iid collision scale

A hidden enlarged coordinate yields a uniform collision-scale lower bound, while noninteger orders require an additional approximation obstruction. The accompanying upper-bound construction makes polynomial approximations observable through counts and reserves separate margins for approximation, pilot selection, and noise.

C.2 One hidden-coordinate calculation for the iid collision scale

  • For α ≥ 3/2, a hidden-coordinate construction gives a uniform collision and saturation lower bound; min-entropy also requires Ωε(k log k) samples.The alternatives raise one of several candidate coordinates and reduce the reservoir mass to preserve normalization; for noninteger orders, this argument gives only the collision obstruction.Source: §C.2 · pp. 23–24
  • The lower-bound proof compares a null distribution with alternatives that enlarge one candidate probability and drain the shared reservoir.A uniform mixture of alternatives remains statistically close to the null at small sample sizes, despite entropy separation.Source: §C.2 · p. 24

D.1 How the polynomial becomes an observable estimator

1. Why use the two adjacent integers?

  • Adjacent-integer polynomial blocks cancel fractional exponents exactly, while coupled profiles control behavior across the approximation interval.A reverse profile controls the lower endpoint, a forward profile the upper endpoint, and an interior term connects them.Source: §1 · p. 26

4. Why subtract the linear term?

  • Subtracting the known linear total replaces its noisy estimate with its exact value, leaving a residual whose variance is explicitly bounded.Near α = 1, the affine subtraction exposes a residual of order β, matching the shrinking tolerance interval.Source: §4 · pp. 27–28

5. What do the margins pay for?

D.2 Exact overlap normalization at the original accuracy

This section develops exact overlap normalization and calibrated deterministic margins for combining endpoint polynomial approximations, including bounds across the central range and below the cutoff. It then analyzes how polynomial count noise, pilot errors, and replacing the random global affine aggregate with its known value affect those margins.

D.2 Exact overlap normalization at the original accuracy

  • The two-arm envelope gives a unique overlap level and uniform correction bounds, retaining the exponential factor and prefactor needed near order one.For Fγ(t) = ht − H(γ) + Dγ(t), the stated bounds are 2[J(t/4) − 1] ≤ Fγ(t)h ≤ t; the capacity calibration remains conditional on later polynomial construction.Source: §D.2 · pp. 28–31

D.3 One parameter rule for the regularized upper bound

  • The regularized-root rule provides uniform scale and cutoff controls, with increasing sample multiplier D making the lower cutoff sufficiently small without changing accuracy ε.The same parameter rule also calibrates errors to vanish linearly as α approaches one, where the target power sum approaches 1.Source: §D.3 · pp. 31, 32, 34

D.4 Constructing the polynomial explicitly

  • The polynomial construction combines integer-power representations of p^α to control the lower and upper endpoints, joined by smooth polynomial cutoffs.The lower-end term uses a function of a/p behaving like (a/p)^γ, while the upper-end term uses a function of p/b behaving like (p/b)^δ.Source: §D.4 · p. 35
  • A global lower envelope for the high profile is justified only when ω is bounded below; the stronger claim fails uniformly as ω approaches zero because of interior kernel zeros.For arbitrary ω approaching zero, the proof uses only the stated alternative bounds.Source: §D.4 · p. 39
  • The construction combines low- and high-endpoint fractional-power polynomial profiles under an exact capacity choice to bound the approximation on [a,b] and control its contribution below a.The deterministic bounds apply before sampling, with constants that do not vary with the fractional part or m.Source: §D.4 · pp. 37, 40

D.5 From pointwise approximation to a power-sum estimate

  • The upper approximation margin pays for errors from probabilities below a, allowing a deterministic additive correction instead of requiring accurate approximation at every arbitrarily small probability.The below-cutoff errors may accumulate across as many as k probabilities.Source: §D.5 · p. 42
  • The corrected oracle mean is separated from both endpoints of [κP, P] only after calibration conditions are checked; deterministic bounds alone do not establish sample complexity.The next step must bound polynomial-count fluctuations, heavy-count errors, and pilot mistakes against this available margin.Source: §D.5 · p. 44

E From the polynomial approximation to a sampling guarantee

  • The affine anchor replaces the sum of linear count terms by the known value q1, with a mean-zero adjustment that matters near order one.The proof then combines deterministic approximation room on both sides of the target interval with high-probability control of count fluctuations and pilot mistakes.Source: E From the polynomial approximation to… · p. 45

E.1 Conditional count noise for the common polynomial

  • The conditional count bound controls noise against the available margin; the actual polynomial’s coefficient bounds and an independent pilot limit factorial-statistic noise.The pilot suppresses excessive polynomial noise by making frequent symbols unlikely to enter the polynomial branch; pilot randomness is handled separately from conditional count noise.Source: E From the polynomial approximation to… · p. 45, §E.1 · p. 48

Define the actual margin

  • A comparison margin Mb is at most (1 + Cε)M, enabling variance analysis when the actual cutoff is arbitrarily small near an integer.The subsection bounds contributions from polynomial degrees below the real order using power means, coefficient bounds, and the pilot factorial-moment bound.Source: Define the actual margin · p. 49
  • High-degree variance is bounded by splitting small and larger count means: the leading degree gets a sharp bound, while remaining degrees use the pilot and a geometric series.This yields the first term of (CC16).Source: Define the actual margin · p. 50
  • The variance bounds become small relative to the actual margin by choosing the final sample multiplier D sufficiently large, completing the comparison in (CC12).The construction constants are fixed before D, so a negative power of D can reduce the remaining noise.Source: Define the actual margin · p. 50
  • Replacing the random affine aggregate by its known value adds centered noise with variance q1^2/n, at most C d ε M^2/n relative to the margin, independently of how small a is.The variance identity follows from the total main-sample count having a Poisson distribution with mean n.Source: Define the actual margin · p. 51
  • Near order one, subtracting the nearly linear part makes the light-residual variance at most ηβ^2P^2; the bound also holds with the common q1 anchor.The remaining degrees exceed α, so the medium- and large-mean argument applies without a small-mean split.Source: Define the actual margin · p. 51
  • The section supplies the conditional count-variance component of the common proof; pilot and heavy-count estimates and the full mean-margin analysis are combined later in Theorem E.13.The stated coefficient assumptions persist under the omega-tail modification and common global anchor.Source: Define the actual margin · p. 51

E.2 Pilot errors and the analytic heavy count

The estimator controls pilot misclassification through aggregate error bounds rather than symbolwise guarantees, then combines polynomial and Gamma-count components in a calibrated upper-bound construction.

E.2 Pilot errors and the analytic heavy count

  • False-heavy pilot assignments are controlled in aggregate: their absolute expected value is at most e^(-c*αB), with variance made an arbitrarily small fixed multiple of M^2.Summing contributions avoids an unnecessary alphabet-sized union bound.Source: §E.2 · p. 52
  • For false-light assignments above b, exponential decay in the pilot lower tail dominates polynomial growth when the fixed pilot multiplier is large enough.The bound applies to a polynomial of degree at most CdL with the stated coefficient-sum bound.Source: §E.2 · p. 53
  • For genuine heavy symbols, the proof controls the entire count vector's ℓα norm instead of requiring accurate estimates coordinate by coordinate.The resulting concentration bound also applies conditionally to subsets selected by independent pilot counts when their means meet the lower threshold.Source: §E.2 · p. 53
  • The omega-scaled heavy statistic is calibrated to lie inside its permissible interval with probability at least 1 − ρ for α ≥ 3/2.The multiplicative factor leaves room on both sides for random fluctuations.Source: §E.2 · p. 54
  • Symbols below the approximation cutoff contribute at most Cmka^α in absolute total, and their ratio to the baseline tends uniformly to zero as D increases.This handles the region p < a, where the approximation guarantee on [a, b] does not apply.Source: §E.2 · p. 54

E.3 One calibrated estimator and its matching upper bound

  • The hybrid estimator combines a deterministic correction, the known affine total, a polynomial branch for light pilot counts, and a Gamma branch for heavy counts.The construction described here covers noninteger orders at least 3/2; the near-one range is treated separately.Source: §E.3 · p. 55
  • Theorem E.13 gives a common upper bound uniformly for noninteger 3/2 ≤ α < log k, using the root X from Lemma D.4.The construction is calibrated so its constants depend only on ε, and the estimator is converted to fixed samples by Poisson thinning.Source: §E.3 · pp. 55, 57
  • The proof compares the estimator with an ideal statistic, bounds centered fluctuations and boundary errors, then combines fixed probability budgets before returning to fixed samples.Poisson thinning implements the independent main and pilot samples from a fixed pool.Source: §E.3 · pp. 56–57

F The near-one upper bound

The section develops near-one entropy estimation bounds, establishing an $O_\varepsilon(k/\log k)$ estimator for $1<\alpha\le 3/2$ while preserving cancellation through polynomial and Gamma statistics and a random pilot. For lower bounds, it explains the need to control normalization near one and constructs interpolation-based positive mean-one priors that preserve moment matching and entropy separation near order-one and integer boundaries.

F The near-one upper bound

  • Near α = 1, cancellation of the known total mass makes the required power-sum error and estimator error vanish at the same rate; degree-at-least-two coefficients carry a factor β.The argument uses that the target p^(1+β) becomes p at β = 0, yielding variance of order β²P², including randomness from the pilot.Source: F The near-one upper bound · pp. 58, 60, 62, 63
  • The near-one estimator estimates Hα within ε, with sample complexity Oε(k/log k), equivalently Oε(αk^(1−1/α)X), uniformly on the near-one range.Source: F The near-one upper bound · p. 61

G Lower bounds: two random distributions that the data cannot distinguish

  • The lower-bound strategy constructs mean-one random weights with matching low integer moments but differing αth moments, normalizes them into probability vectors, and shows their sample laws remain close.The stated aim is to obtain entropy separation above 2ε while keeping the hypotheses statistically indistinguishable.Source: G Lower bounds: two random… · p. 64

G.1 Why normalization must be analyzed explicitly

  • Replacing the random weights’ sum by its expectation can lose uniformity as α approaches one, so the lower bound analyzes normalization explicitly and removes the affine term.The supplied passage introduces a normalization lemma for nonnegative U with EU = 1 and finite A = EU^α.Source: §G.1 · p. 64
  • Controlling S and W separately bounds the entropy error by m/(4β) on the stated event, using a variance bound and Chebyshev’s inequality.The normalization error is isolated before bounding the two random errors separately.Source: §G.1 · p. 65
  • As α approaches 1, the exact cancellation in gβ removes the apparent β^-2 loss when the separation margin is proportional to β.For U in {0} ∪ [1, B] with bounded A, the passage bounds |gβ(U)| by U^(1+β) log B and Egβ(U) by A log B.Source: §G.1 · p. 65

G.2 Constructing moment-matched weights by interpolation

  • Tensor interpolation turns moment-matched signed measures into positive probability laws on {0} ∪ [1, B] with mean one and a shared logarithmic margin.An exact accuracy ε and positive margin m are preserved when 1 + R−R+ ≥ e^(2εβ+m)(R−+R+).Source: §G.2 · pp. 66–67
  • For noninteger α, the two interpolation factors match integer moments through degree L + 1, with only moments adjacent to α potentially unmatched.Setting ρ−=0 or ρ+=0 also matches moment m0 or m0+1, respectively.Source: §G.2 · p. 67
  • Near α=1, the unperturbed construction matches moments through L + 1 while keeping negative mass R+ ≤ e^-16.This is the order-one endpoint substitution using the complementary factor of exponent 1−β.Source: §G.2 · pp. 67–68
  • Near higher integers, perturbing the appropriate factor leaves only moment r potentially unmatched, without replacing ε by a smaller fixed accuracy.The construction applies when α = r + σs and the negative masses satisfy the stated condition.Source: §G.2 · p. 68

G.3 From the weight construction to an impossibility theorem

The lower-bound argument turns constructed weights into a test between entropy hypotheses. It makes the fingerprints difficult to distinguish while ensuring that an accurate entropy estimate would separate the hypotheses.

G.3 From the weight construction to an impossibility theorem

  • Random relabeling makes symbol names uninformative, while Poissonizing the number of weights makes fingerprint coordinates independent for an exact distance calculation.The fingerprint records counts of symbols appearing once, twice, and so on, while discarding their names.Source: §G.3 · p. 68
  • Total variation at most 1/4 forces average testing error at least 3/8, and the fingerprint comparison is used to reach that testing barrier.The proof then transfers a hypothetical accurate entropy estimate into a test.Source: §G.3 · pp. 68–69
  • A hypothetical estimator using n = ⌊θb/4⌋ iid samples cannot achieve additive entropy error ε with probability at least 2/3 uniformly on the k-symbol simplex when the stated conditions hold.The impossibility follows by converting accurate entropy estimation into a test between the two hypotheses.Source: §G.3 · pp. 68–69
  • Under each hypothesis, independent Poisson marking gives independent fingerprint entries with means bq_ij, enabling a comparison of the fingerprint laws.The construction draws Q ∼ Poi(b) weights and then conditionally independent counts.Source: §G.3 · p. 69
  • The transfer to labeled samples randomly assigns distinct observed symbols to labels and bounds the exceptional event that more than k symbols appear.Conditional on the weights, the ordered labels are iid from normalized weights given the total count.Source: §G.3 · p. 69

G.4 Choosing the parameters at the target sample scale

This section calibrates and completes a lower-bound construction for noninteger orders, developing the count and interpolation estimates and parameter choices needed for it. It also specializes the argument to fixed noninteger orders, where the upper and lower bounds match at scale k/log k.

G.4 Choosing the parameters at the target sample scale

  • The subsection gives a longer calculation than preceding constructions to keep constants uniform as α approaches one, an integer, or grows with k.Source: §G.4 · p. 69
  • Matching integer moments cancels low-degree terms in count probabilities, while one unmatched moment leaves a controlled Taylor term and remainder.The estimates are used to bound fingerprint distance, including the exact-matching case.Source: §G.4 · pp. 70–71
  • Chebyshev interpolation nodes control extrapolation while preserving a principal atom, yielding negative mass at most exp(−ξ)z and principal positive mass at least 1/2.The principal atom also supplies a denominator for the count-distance bound.Source: §G.4 · p. 71
  • The parameter rule chooses sample intensity proportional to αk^(1−1/α)X/k and calibrates interpolation degrees and support to keep estimates uniform across orders.The construction uses one interpolation rule for every noninteger order and a common hidden-coordinate argument when the root is bounded.Source: §G.4 · pp. 69, 72
  • The lower-bound construction reuses the upper-bound proof’s scalar root to control the perturbation across orders.For the calibrated case x > X0, the root equation is an equality and yields the stated perturbation control.Source: §G.4 · p. 72
  • The target-scale lower bound is completed by a regularized-root parameter rule, tensor construction, and statistical transfer, including an exact coefficient bound for degree-zero interpolation.The fixed-sample transfer uses n = ⌊θk/8⌋ ≍_ε R, and the degree-zero root satisfies x ≍_ε k^(1/α)/K.Source: §G.4 · pp. 76–77

G.5 A complete fixed-real-order specialization

  • For each fixed noninteger α > 1, the sample complexity is Θ_{α,ε,δ}(k/log k) for fixed ε > 0 and 0 < δ < 1/2.The upper bound uses X ≍_{α,ε} k^(1/α)/log k; the lower bound holds for every fixed positive accuracy, and repetition extends it to fixed confidence levels.Source: §G.5 · pp. 77–78
  • The fixed-real-order lower bound uses interpolation factors and a tensor prior with matching integer moments, then transfers indistinguishable counts to a lower bound of Ω_{α,ε}(k/log k).Its choices allow any fixed positive accuracy; support overflow and sample shortage vanish as θk ≍ k/log k grows.Source: §G.5 · pp. 77–78

H.1 A real-order universality theorem for additive logarithmic targets

For fixed continuous positive functions with a finite leading power at zero, logarithmic additive-functional estimation transfers to the corresponding power-estimation problem. The result gives alphabet-size rates for fixed functions and orders, while explicitly not claiming uniformity as those functions or orders change.

H.1 A real-order universality theorem for additive logarithmic targets

  • Polynomial approximation of f(x)/x gives a fixed-sample absolute estimate of its additive sum, independent of k.The statistic is built from polynomial approximation and factorial-count statistics, with Rao–Blackwellization using the observed counts.Source: §H.1 · p. 79
  • For fixed α > 1, β > 0, and f with a finite leading power at zero, Theorem H.2 transfers logarithmic additive estimation to the Rényi power target with explicit accuracy loss ζ.The lower bound holds for sufficiently large k, with thresholds and constants allowed to depend on f, α, β, ε, ζ, and δ.Source: §H.1 · p. 79
  • Replication transfers power-estimation rates to logarithmic additive targets while preserving the sampling experiment exactly.The transfer incurs the stated deterministic accuracy loss; the replicated distributions are exactly normalized.Source: §H.1 · p. 80
  • The fixed-order conclusions do not provide uniform constants when the leading order approaches an integer or when the function or order changes.The lower bound is stated for k sufficiently large, with its threshold and constants depending on the fixed parameters.Source: §H.1 · pp. 79, 81
  • For positive analytic targets, the first nonzero Taylor order distinguishes zero-sample behavior at r=0, bounded sufficient samples at r=1, and the integer rate for r≥2.For r=1, at least one observation is needed when the target range exceeds 2ε; otherwise its range midpoint suffices without samples.Source: §H.1 · p. 81

H.1.1 Why arbitrary smooth convex functions need additional data

Smoothness, convexity, and a common Lipschitz bound do not ensure a common polynomial sample rate for logarithmic additive functionals. By contrast, a finite leading power supports a transfer result, including matching rates for a class of nonpower targets.

H.1.1 Why arbitrary smooth convex functions need additional data

  • For the flat family f_s, logarithmic additive-functional estimation requires Ω(k^(2s)) observations as k grows.The construction uses uniform and perturbed probability vectors and separates their target values for a suitable fixed perturbation.Source: §H.1.1 · pp. 81–82
  • A positive, increasing, convex, C∞, 1-Lipschitz target with all derivatives zero at the origin can require Ω(k^(2e^4k)) samples along even alphabet sizes.This example shows that those regularity properties alone do not imply a common polynomial sample rate.Source: §H.1.1 · p. 82
  • A finite leading power permits a transfer theorem, but the paper does not establish a minimax formula for arbitrary positive continuous functions.The regularity of the smooth counterexamples does not substitute for the finite-leading-power condition.Source: §H.1.1 · pp. 82–83
  • For f(x)=x^r h(x), with integer r≥2 and continuous positive h, logarithmic additive-functional estimation requires and suffices with Θ(k^(1−1/r)) samples.This rate follows by transferring the fixed integer-order power rate.Source: §H.1.1 · p. 83

I.1 Exact multiplicative approximation and its count dual

The section develops an exact duality between multiplicative approximation and separated prior expectations, then connects polynomial count noise to likelihood overlap while identifying conditions needed for statistical bounds.

I.1 Exact multiplicative approximation and its count dual

  • Weighted relative approximation error has an exact signed-measure dual, whose normalized Jordan parts give probability laws with matching V-moments.The duality is attained; when the approximation error is positive, the weighted variation constraint is active.Source: §I.1 · p. 84
  • The logarithmic accuracy threshold is exactly η=tanh(βε): error at most η is equivalent to the stated approximation conditions, while larger error yields separated laws.The separated laws have matching V-moments.Source: §I.1 · pp. 84–85

I.1.1 The Poisson basis gives the same quadratic form on both sides

  • In the Poisson count model, one feature map makes polynomial coefficient norm equal reference sampling noise and its dual equal truncated likelihood overlap.The variance identity also shows that a reference norm bound alone need not control variance uniformly.Source: §I.1.1 · p. 86
  • The finite-dimensional dual is a likelihood certificate only after its tail is bounded; weighted variation alone may be too costly for sharp entropy rates.Variance must also be controlled on the relevant parameter region or with a norm incorporating all required references.Source: §I.1.1 · p. 86

I.1.2 Scope of the approximation duality

  • For x^α on an interval including zero, the positive-minimum theorem cannot be invoked directly, and a rate conclusion needs quantitative approximation bounds.The limiting argument from intervals bounded away from zero additionally requires uniform weighted-measure bounds, a controlled affine correction, and tightness.Source: §I.1.2 · p. 87
  • Permutation averaging can yield a symmetric polynomial certificate without forcing additivity; the ∆4 example rules out restricting the global primal to additive polynomials.For the iid count model, averaging preserves degree and does not increase worst-case bias or variance.Source: §I.1.2 · p. 87

AI methodology

  • OpenAI ChatGPT/Codex assisted with mathematical exposition, proof review, literature comparison, and LaTeX preparation.Source: AI methodology · p. 88
Loading 2610.28999v1…