Let $Y$ denote a Gaussian random variable characterized by a mean $\mu$ and a variance $\sigma^2$. Consider $N$ independent and identically distributed (i.i.d.) copies of $Y$, denoted as $Y_1, Y_2, \ldots, Y_N$. Now, let's examine the number of $N$ for which the probability satisfies the inequality:

\begin{align} \mathbb{P}\left[\left|-\frac{1}{N}\sum_{i=1}^{N}\log f(Y_i)-h(Y)\right|\geq\delta\right]\leq\epsilon, \end{align}

Here, $f(y)$ represents the probability density function (pdf) of the Gaussian distribution, and $h(Y)$ represents the differential entropy of $Y$. It is worth noting that the expected value of the expression $-\frac{1}{N}\sum_{i=1}^{N}\log f(Y_i)$ is equal to $h(Y)$:

\begin{align} \mathbb{E}\left[-\frac{1}{N}\sum_{i=1}^{N}\log f(Y_i)\right] = h(Y). \end{align}

To analyze the probability inequality, we can employ a suitable concentration inequality. One approach is to consider the subgaussianity of the term $\log f(Y_i) = \frac12\log(2\pi\sigma^2) - \frac{(Y_i-\mu)^2}{2\sigma^2}$. Is considering the subgaussianity of $\log f(Y_i)$ a valid approach? If so, could you provide guidance on how to compute the precise value of the subgaussianity parameter for $-\frac{1}{N}\sum_{i=1}^{N}\log f(Y_i)$?


1 Answer 1


$\newcommand{\de}{\delta}\newcommand{\ep}{\epsilon}\newcommand{\si}{\sigma}\newcommand{\R}{\mathbb R}$We have \begin{equation*} L_i:=-\ln f(Y_i) = c+Z_i^2/2, \end{equation*} where $c:=\frac12\ln(2\pi\si^2)$ and $Z_i:=\frac{Y_i-\mu}\si$, so that the $Z_i$'s are independent standard normal random variables (r.v.'s).

Clearly, the r.v.'s $L_i$ are not sub-Gaussian, because for any real $s>0$ \begin{equation*} Ee^{L_i^2/s^2}=\int_\R dz\,\frac1{\sqrt{2\pi}}e^{(c+z^2/2)^2/s^2-z^2/2}=\infty, \end{equation*} since $e^{(c+z^2/2)^2/s^2-z^2/2}\to\infty$ as $z\to\infty$.

However, letting \begin{equation*} X_i:=2(L_i-EL_i)=Z_i^2-1, \end{equation*} for all real $h<1/2$ we have \begin{equation*} R(h):=Ee^{hX_i}=e^{-h}\int_\R dz\,\frac1{\sqrt{2\pi}}e^{hz^2-z^2/2}=\frac{e^{-h}}{\sqrt{1-2h}}. \tag{1}\label{1} \end{equation*} Note that for $h\in[0,1/2)$ \begin{equation*} R(-h)\le R(h), \tag{2}\label{2} \end{equation*} since for $g(h):=\ln\dfrac{R(-h)}{R(h)}$ we have $g(0)=0$ and $g'(h)=-\dfrac{8h^2}{1-4h^2}\le0$ for $h\in[0,1/2)$.

We want to find $n$ such that \begin{equation*} p_n:=P\Big(\Big|-\frac1n\sum_{i=1}^n\ln f(Y_i)-h(Y)\Big|\ge\de\Big)\le\ep. \tag{3}\label{3} \end{equation*} Note that \begin{equation*} p_n=P(|S_n|\ge2n\de), \end{equation*} where \begin{equation*} S_n:=\sum_{i=1}^n X_i. \end{equation*} So, we want to find $n$ such that \begin{equation*} P(|S_n|\ge2n\de)\le\ep, \end{equation*} where $\de\in(0,\infty)$ and $\ep\in(0,1)$. For all real $h\in[0,1/2)$, in view of \eqref{2} and \eqref{1}, \begin{equation*} \begin{aligned} P(|S_n|\ge2n\de)&=P(S_n\ge2n\de)+P(-S_n\ge2n\de) \\ &\le e^{-2n\de h}Ee^{hS_n}+e^{-2n\de h}Ee^{-hS_n} \\ &=e^{-2n\de h}R(h)^n+e^{-2n\de h}R(-h)^n \\ &\le2e^{-2n\de h}R(h)^n =2e^{nl(h)}, \end{aligned} \end{equation*} where $l(h):=-h\de-h-\frac12\ln(1-2h)$. Next, the minimum of $l(h)$ over $h\in[0,1/2)$ occurs at $h=h_\de:=\frac\de{2(1+\de)}$, and $e^{l(h_\de)}=q(\de):=e^{-\de/2}\sqrt{1+\de}<1$.

So, \eqref{3} will hold if $2q(\de)^n\le\ep$, that is, if \begin{equation} n\ge n_{\de,\ep}, \end{equation} where \begin{equation} n_{\de,\ep}=\frac{\ln(\ep/2)}{\ln q(\de)}, \end{equation} so that $n_{\de,\ep}$ is the root $n$ of the equation $2q(\de)^n=\ep$. One may also note that \begin{equation} n_{\de,\ep}\sim\frac{4\ln(2/\ep)}{\de^2} \end{equation} as $\de\downarrow0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.