Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = \frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $-H(\mu)$.

What concentration inequalities exist for finite $n$? In other words, what upper bounds are known for the expression $P(|S_n - H(\mu)|>t)$?

Of course, we can get some upper bounds using, for instance, Bernstein's inequality for bounded variables, with bound depending on the size of the smallest atom of $\mu$. However, using the sup norm bound seems very rough in this case, since small atoms inflate the norm but also have small contributions to the mean. On the other hand, using more general versions of Bernstein's inequality with moment bounds does not seem natural. ($\sum_{i \in X} \mu(i) \log^k \mu(i)$ does not seem like a natural quantity).

Since this is a classical situation, there probably exist sharper inequalities than sup norm, using some natural quantities. What are they?

Consider a measure $\mu$ on a finite set, and let $x_1, \ldots, x_n$ be i.i.d samples from $\mu$. Then the expression $S_n = -\frac{1}{n} \sum_{i=1}^n \log \mu(x_i)$ converges by a.s. to the entropy $H(\mu)$.

What concentration inequalities exist for finite $n$? In other words, what upper bounds are known for the expression $P(|S_n - H(\mu)|>t)$?

Of course, we can get some upper bounds using, for instance, Bernstein's inequality for bounded variables, with bound depending on the size of the smallest atom of $\mu$. However, using the sup norm bound seems very rough in this case, since small atoms inflate the norm but also have small contributions to the mean. On the other hand, using more general versions of Bernstein's inequality with moment bounds does not seem natural. ($\sum_{i \in X} \mu(i) \log^k \mu(i)$ does not seem like a natural quantity).

Since this is a classical situation, there probably exist sharper inequalities than sup norm, using some natural quantities. What are they?