Cryptology ePrint Archive: Report 2019/766

Complexity of Estimating Renyi Entropy of Markov Chains

Maciej Obremski and Maciej Skorski

Abstract: Estimating entropy of random processes is one of the fundamental problems of machine learning and property testing. It has numerous applications to anything from DNA testing and predictability of human behaviour to modeling neural activity and cryptography. We investigate the problem of Renyi entropy estimation for sources that form Markov chains.

Kamath and Verdķ (ISITí16) showed that good mixing properties are essential for that task. We show that even with very good mixing time, estimation of min-entropy requires $\Omega(K^2)$ sample size, while collision entropy requires $\Omega(K^{3/2})$ samples, where K is the size of the alphabet. Our results hold both in asymptotic and non-asymptotic regimes.

We achieve the results by applying Le Camís method to two Markov chains which differ by an appropriately chosen sparse perturbation; the discrepancy between these chains is estimated with help of perturbation theory. Our techniques might be of independent interest.

Category / Keywords: foundations / information theory, Renyi entropy, Min-entropy, Lower bounds

Date: received 30 Jun 2019

Contact author: obremski math at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190702:142951 (All versions of this report)

Short URL: ia.cr/2019/766


[ Cryptology ePrint archive ]