{"id":"arxiv/2607.16966","url":"https://arxiv.org/abs/2607.16966","tags":["cs.IT","cs.CC","cs.LG","math.ST","stat.ML"],"score":0,"title":"Tight Sample Bounds for Renyi and Min-Entropy Estimation","domain":"cs.IT","source":"arxiv","authors":["Arman Adibi","Piotr Krysta"],"reviews":0,"subject":"cs.IT","summary":"Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a $k$-symbol alphabet using $Θ(k/\\log k)$ samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-$α$ R'{e}nyi entropy, $H_α$. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for $k$ and integer $α>1$; our lower bounds also hold for noninteger $α\\ge1.001$. We prove that min-entropy estimation to constant additive accuracy has…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-18","reactions":{}}