Multi-Scale Collision Counting for Rényi Entropy Rate Estimation

We present a method for estimating the Rényi 2-entropy rate h₂ of stationary ergodic sources from raw byte streams. The method expands bytes to nibbles (α = 16), computes debiased collision probabilities F̂₂(k) at k-gram orders k = 1, …, K via the falling-factorial estimator, and extracts the entropy rate from the ordinary least-squares slope of log F̂₂(k) versus k. On synthetic Markov chains with known ground truth, the estimator achieves median error 0.999. On 124 DNS tunnel capture files spanning ten classes (eight tunnel tools and two benign categories), the Rényi entropy rate h₂ alone (ARI = 0.720) outperforms Shannon entropy—both single-scale (ARI = 0.246) and multi-scale slope (ARI = 0.204)—for model-free tool classification (ΔARI = 0.516). This advantage persists after Miller-Madow debiasing of the Shannon estimator, confirming it is intrinsic to the collision probability functional rather than an artifact of estimation bias. The (h₂, h₃, h₄) multi-order fingerprint provides modest additional gain (ARI = 0.747). R² of the linear fit decreases monotonically with Markov order (orders 0–4), serving as a non-parametric memory depth diagnostic. The estimator runs in O(nK) time with O(αᴷ) space.