Skip to main content
2 of 2
added 5 characters in body
usul
  • 4.5k
  • 27
  • 30

Here's a step that seems nice enough to point out. It still leaves a parameter to pick, and I'm not sure it's ever better than applying Bernstein, but it does something different.

We can get a probability bound in terms of how much $S_n$ exceeds the Renyi entropy $H_{\alpha}$ of $\mu$ (equivalently, worded in terms of the $\ell_{\alpha}$ norm of $\mu$), for any $0 < \alpha < 1$. The unresolved question is if we can to pick $\alpha$ to get a nice closed form of some kind. Maybe someone more clever than I can speak to that.

Claim. Let $X_1,\dots,X_n$ be i.i.d. according to $\mu$ and $Y_i = \log(1/\mu(X_i))$; let $S_n = \frac{1}{n} \sum_{i=1}^n Y_i$. Then for any $0 < \alpha < 1$, \begin{align} \Pr[ S_n \geq t ] &\leq 2^{-n (1-\alpha) \left( t - H_{\alpha}(\mu) \right) } \\ &= 2^{-n \left( (1-\alpha)t - \alpha \log \| \mu \|_{\alpha} \right) } . \end{align} Here I'm writing $\mu = (\mu_1,\dots,\mu_m)$ as a vector of probabilities. Note that $H_{\alpha}$ is decreasing in $\alpha$ and $H_1 = H$, Shannon entropy. So as $n \to \infty$, we can pick $\alpha \to 1$ and get tail bounds for $t \to H(\mu)$.

Proof. Using the general Chernoff method, \begin{align} \Pr[S_n \geq t] &= \Pr\left[ 2^{\lambda S_n} \geq 2^{\lambda t}\right] & (\forall \lambda \geq 0) \\ &\leq \frac{\mathbb{E} 2^{\lambda S_n} }{2^{\lambda t}} & (\text{Markov's}). \end{align} We have \begin{align} \mathbb{E} 2^{\lambda S_n} &= \left( \mathbb{E} 2^{\frac{\lambda}{n} Y_1} \right)^n \\ &= \left( \mathbb{E} \mu(X_1)^{-\lambda/n} \right)^n \\ &= \left( \sum_{j=1}^m \mu_j^{1-\lambda/n} \right)^n . \end{align} Hence \begin{align} \Pr[S_n \geq t] \leq 2^{-n \left(\frac{\lambda}{n} t - \log \sum_j \mu_j^{1-\lambda/n} \right)} . \end{align} Pick $\lambda$ such that $1-\lambda/n = \alpha$, for a chosen $\alpha \in [0,1]$. In other words, $\frac{\lambda}{n} = 1-\alpha$, and factoring this out and substituting, \begin{align} \Pr[S_n \geq t] \leq 2^{-n (1-\alpha) \left(t - \frac{1}{1-\alpha} \log \sum_j \mu_j^{\alpha} \right)} . \end{align}

usul
  • 4.5k
  • 27
  • 30