Error and bias behavior of ksg mutual information estimator on gaussian channel
A Poisson Transition and Bias Law for KSG Mutual-Information Estimation
Information Theory
Summary
Measuring how much two things are related using data can be tricky because tools can make mistakes. The authors studied one popular tool (the KSG estimator) when the connection it's measuring is very clear or almost perfect. They found that even with more data, the tool keeps a certain bias, meaning it consistently over- or underestimates by a fixed amount. Their work shows when and why this bias happens and offers a way to correct it based on how the tool counts neighborhoods in the data.
What this means in practice
- •For data scientists: Improve accuracy of mutual information estimates in noisy or nearly deterministic data relationships by applying bias corrections for the KSG estimator.
- •For communications engineers: Refine performance evaluations of communication channels by correcting mutual information estimates when channels approach deterministic behavior.
Authors
Abhiram Gorle, Tsachy Weissman
Abstract
We quantify the error of the strict-radius Kraskov--Stögbauer--Grassberger (KSG-1) mutual-information estimator on a Gaussian channel as the sample size \(n\) grows and the channel becomes nearly deterministic. For fixed dimension \(p\) and neighbor index \(k\), we define the resolution parameter \(u_n=ne^{-I_n}\), where \(I_n\) is the true mutual information in nats. When \(u_n\to u\in(0,\infty)\), we prove that the estimation error converges in mean square to a computable deterministic bias \(B_{p,k}(u)\). Sampling fluctuations therefore vanish, while an additive bias can persist. We derive this bias from an explicit marked-Poisson law for the neighborhood counts, characterize its small-\(u\) asymptotics, and show that it tends to zero as \(u\to\infty\). The same law describes how often neighborhoods saturate, meaning that they make the largest possible contribution to the estimate. The limiting saturation probability decreases continuously and strictly from one to zero, allowing a Gaussian-model bias correction on fixed critical intervals. Finite-sample experiments show substantial bias even when the true information lies below the estimator's logarithmic ceiling and saturated neighborhoods are rare. Saturation-based correction reduces estimation error in these experiments, though recovering the resolution parameter from the observed saturation fraction can remain difficult when saturation is rare.