Return to Answer

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY/n})^n \tag{1} $$ for all real $h$. Note also that $$-\max_z\ln\mu(z)=\min Y<EY=H(\mu)<\max Y=-\min_z\ln\mu(z).$$

Take now any real $t$ such that $H(\mu)=EY\le t<\max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-ht+\ln Ee^{hS_n}\}=\exp\{-ht+n\ln Ee^{hY/n}\}. \tag{2} $$ The derivative of the exponent $-ht+n\ln Ee^{hY/n}$ in $h$ is $-t+\frac{EYe^{hY/n}}{Ee^{hY/n}}$, which strictly and continuously increases from $-t+EY\le 0$ to $-t+\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the upper bound $\exp\{-ht+n\ln Ee^{hY/n}\}$ on the right-tail probability $P(S_n\ge t)$ is minimized when $h=h_{t,+}$ is the only nonnegative root of the equation $$\frac{EYe^{hY/n}}{Ee^{hY/n}}=t. \tag{3} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t>\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-ht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}$ is the only non-positive root of the equation $(2)$.

In view of $(1)$, equation $(3)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-s}=0, \tag{4} $$ where $s:=h/n$, and this equation can be easily solved for $s$ numerically if the set $Z$ is not too large.

Note that then the upper bound in $(2)$ can be rewritten as $e^{-na}$, where $a:=st-\ln Ee^{sY}>0$ if $t\ne EY$, so that this bound exponentially decreases in $n$ if $t$ is fixed.

All this is of course well known, even in the general case of i.i.d. random summands with finite exponential moment of the absolute value. Basically, in this particular situation I have just added the first equality in $(1)$ and rewrote $(3)$ as $(4)$.

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY})^n \tag{1} $$ for all real $h$. To avoid trivialities, assume that $\max Y:=-\min_z\ln\mu(z)>-\max_z\ln\mu(z)=:\min Y$. Then $$\min Y<EY=H(\mu)<\max Y.$$

Take now any real $t$ such that $H(\mu)=EY\le t<\max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-nht+\ln Ee^{nhS_n}\}=\exp\{-nht+n\ln Ee^{hY}\}. \tag{2} $$ The derivative of the exponent $-nht+n\ln Ee^{hY}$ in $h$ is $-nt+n\frac{EYe^{hY}}{Ee^{hY}}$, which strictly and continuously increases from $-nt+nEY\le 0$ to $-nt+n\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the upper bound $\exp\{-nht+n\ln Ee^{hY}\}$ on the right-tail probability $P(S_n\ge t)$ is minimized when $h=h_{t,+}=h_{t,\mu,+}$ is the only nonnegative root of the equation $$m(h):=m_\mu(h):=\frac{EYe^{hY}}{Ee^{hY}}=t. \tag{3} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t>\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-nht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}=h_{t,\mu,-}$ is the only non-positive root of the equation $(2)$.

Thus, $$P(S_n\ge t)\le e^{-na_+(t)},\quad\text{where $a_+(t):=h_{t,+}t-\ln Ee^{h_{t,+}Y}>0$} \tag{4} $$ if $H(\mu)=EY<t<\max Y$, $$P(S_n\le t)\le e^{-na_-(t)},\quad\text{where $a_-(t):=h_{t,-}t-\ln Ee^{h_{t,-}Y}>0$} \tag{5} $$ if $H(\mu)=EY>t>\min Y$ So, these bounds exponentially decrease in $n$ if $t$ is fixed. By formulas (3.7) and (3.8) in [Chernoff], bounds $(4)$ and $(5)$ cannot be improved by replacing $a_\pm(t)$ by greater values.

In view of $(1)$, equation $(3)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-h}=0, \tag{6} $$ and this equation can be easily solved for $h$ numerically if the set $Z$ is not too large.

All this is of course well known, even in the general case of i.i.d. random summands with finite exponential moment of the absolute value. Basically, in this particular situation I have just added the first equality in $(1)$ and rewrote $(3)$ as $(6)$.

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY/n})^n \tag{1} $$ for all real $h$. Note also that $$-\max_z\ln\mu(z)=\min Y<EY=H(\mu)<\max Y=-\min_z\ln\mu(z).$$

Take now any real $t$ such that $H(\mu)=EY\le t<\max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-ht+\ln Ee^{hS_n}\}=\exp\{-ht+n\ln Ee^{hY/n}\}. \tag{2} $$ The derivative of the exponent $-ht+n\ln Ee^{hY/n}$ in $h$ is $-t+\frac{EYe^{hY/n}}{Ee^{hY/n}}$, which strictly and continuously increases from $-t+EY\le 0$ to $-t+\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the upper bound $\exp\{-ht+n\ln Ee^{hY/n}\}$ on the right-tail probability $P(S_n\ge t)$ is minimized when $h=h_{t,+}$ is the only nonnegative root of the equation $$\frac{EYe^{hY/n}}{Ee^{hY/n}}=t. \tag{3} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t>\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-ht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}$ is the only non-positive root of the equation $(2)$.

In view of $(1)$, equation $(3)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-h/n}=0, $$ and it can be easily solved numerically if the set $Z$ is not too large.

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY/n})^n \tag{1} $$ for all real $h$. Note also that $$-\max_z\ln\mu(z)=\min Y<EY=H(\mu)<\max Y=-\min_z\ln\mu(z).$$

Take now any real $t$ such that $H(\mu)=EY\le t<\max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-ht+\ln Ee^{hS_n}\}=\exp\{-ht+n\ln Ee^{hY/n}\}. \tag{2} $$ The derivative of the exponent $-ht+n\ln Ee^{hY/n}$ in $h$ is $-t+\frac{EYe^{hY/n}}{Ee^{hY/n}}$, which strictly and continuously increases from $-t+EY\le 0$ to $-t+\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the upper bound $\exp\{-ht+n\ln Ee^{hY/n}\}$ on the right-tail probability $P(S_n\ge t)$ is minimized when $h=h_{t,+}$ is the only nonnegative root of the equation $$\frac{EYe^{hY/n}}{Ee^{hY/n}}=t. \tag{3} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t>\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-ht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}$ is the only non-positive root of the equation $(2)$.

In view of $(1)$, equation $(3)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-s}=0, \tag{4} $$ where $s:=h/n$, and this equation can be easily solved for $s$ numerically if the set $Z$ is not too large.

Note that then the upper bound in $(2)$ can be rewritten as $e^{-na}$, where $a:=st-\ln Ee^{sY}>0$ if $t\ne EY$, so that this bound exponentially decreases in $n$ if $t$ is fixed.

All this is of course well known, even in the general case of i.i.d. random summands with finite exponential moment of the absolute value. Basically, in this particular situation I have just added the first equality in $(1)$ and rewrote $(3)$ as $(4)$.

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY/n})^n \tag{1} $$ for all real $h$. Note also that $$-\max_z\ln\mu(z)=\min Y<EY=H(\mu)<\max Y=-\min_z\ln\mu(z).$$

Take now any real $t$ such that $H(\mu)=EY\le t\le \max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-ht+\ln Ee^{hS_n}\}=\exp\{-ht+n\ln Ee^{hY/n}\}. $$ The derivative of the exponent $-ht+n\ln Ee^{hY/n}$ in $h$ is $-t+\frac{EYe^{hY/n}}{Ee^{hY/n}}$, which strictly and continuously increases from $-t+EY\le 0$ to $-t+\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the exponent $-ht+n\ln Ee^{hY/n}$ is minimized when $h=h_{t,+}$ is the only nonnegative root of the equation $$\frac{EYe^{hY/n}}{Ee^{hY/n}}=t. \tag{2} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t\ge\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-ht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}$ is the only non-positive root of the equation $(2)$.

In view of $(1)$, equation $(2)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-h/n}=0, $$ and it can be easily solved numerically if the set $Z$ is not too large.

Actually, Bernstein's inequality does not really require boundedness of the i.i.d. random summands; a finite exponential moment of the absolute value of a random summand will suffice. However, here we can just use Markov's inequality.

Let $X,X_1,\dots,X_n$ be independent identically distributed random variables (i.i.d. r.v.'s) such that $P(X=z)=\mu(z)\in(0,1)$ for all $z$ in a finite set $Z$, with $\sum_z\mu(z)=1$. Let $Y:=-\ln\mu(X)$, $Y_i:=-\ln\mu(X_i)$, and $S_n:=\frac1n\,\sum_1^n Y_i$. Then $$ES_n=EY=-\sum_z\mu(z)\ln\mu(z)=:H(\mu)>0 $$ and $$Ee^{hY}=\sum_z\mu(z)^{1-h},\quad Ee^{hS_n}=(Ee^{hY/n})^n \tag{1} $$ for all real $h$. Note also that $$-\max_z\ln\mu(z)=\min Y<EY=H(\mu)<\max Y=-\min_z\ln\mu(z).$$

Take now any real $t$ such that $H(\mu)=EY\le t<\max Y$. For all real $h\ge0$, by Markov's inequality, $$P(S_n\ge t)\le\exp\{-ht+\ln Ee^{hS_n}\}=\exp\{-ht+n\ln Ee^{hY/n}\}. \tag{2} $$ The derivative of the exponent $-ht+n\ln Ee^{hY/n}$ in $h$ is $-t+\frac{EYe^{hY/n}}{Ee^{hY/n}}$, which strictly and continuously increases from $-t+EY\le 0$ to $-t+\max Y\ge0$ as $h$ increases from $0$ to $\infty$, and so, the upper bound $\exp\{-ht+n\ln Ee^{hY/n}\}$ on the right-tail probability $P(S_n\ge t)$ is minimized when $h=h_{t,+}$ is the only nonnegative root of the equation $$\frac{EYe^{hY/n}}{Ee^{hY/n}}=t. \tag{3} $$

Similarly, for any real $t$ such that $H(\mu)=EY\ge t>\min Y$, the best upper exponential bound on the left-tail probability $P(S_n\le t)$ is $\exp\{-ht+n\ln Ee^{hY/n}\}$, where now $h=h_{t,-}$ is the only non-positive root of the equation $(2)$.

In view of $(1)$, equation $(3)$ can be rewritten as $$\sum_z(t+\ln\mu(z))\mu(z)^{1-h/n}=0, $$ and it can be easily solved numerically if the set $Z$ is not too large.