Límite más bajo de entropía en términos de $\ell_2$ norma

Question

Definir $$ \begin{align} H(p_1, \dots, p_n) &= \sum_{i=1}^n p_i\log1/p_i\\ &=\log n+\sum_{i=1}^n\sum_{k=2}^\infty (-1)^{k + 1} n^{k - 1} \frac{(p_i - 1/n)^k}{k (k - 1)}, \end{align} $$ donde $p_1,\dots,p_n\ge0$ suma $1$.

Luego tenemos el clásico de la desigualdad $H(p_1,p_2)\ge(\log2)(1-2((p_1-1/2)^2+2(p_2-1/2)^2))=(\log 2)(1-2\|p-1/2\|^2)$, y podemos preguntarnos si que puede ser ampliado por $n>2$. En particular, con algo como $$\begin{align} H(p_1,\dots,p_n)&\ge(\log n)(1-c_n\|p-1/n\|^2_2). \end{align}$$ A partir de experimentos con $n=3$, parece $c_n\ge\frac{2 n (\log n/2)}{(n-2) \log n}=2(1-O(1/\log n))$ es suficiente, pero no tengo una prueba de ello. Es también un poco incómodo que puede ir debajo de la $0$, algo que no era el caso con la $n=2$ caso.

Delimitación de los términos de forma individual, podemos obtener $H(p_1,\dots,p_n)\ge-2+4\sum_{i=1}^n\frac{p_i}{1+p_i}$, lo cual no es negativo, pero no como relacionable a la $\ell_2$ norma. También podemos enlazado $H\ge n/4-\|p-1/2\|_2^2$, pero de alguna manera delimitador centrado en $1/n$ parece más natural.

Hay una conocida límite inferior como este, relativo $H(p)$ con $\|p\|_2$? Idealmente, uno que es asintóticamente apretado en la $p_1=\dots=p_n=1/n$ y es siempre positiva.

Answer 1

Definición de <span class="math-container">$p_i=1/n+q_i$</span> obtenemos (usando NAT):

<span class="math-container">$$\begin{align} H({\bf p}) &=-\sum p_i \log(p_i)\ &=-\sum (1/n +q_i) \log(1/n +q_i)\ &=-\sum ( 1/n +q_i) [\log(1/n ) + \log(1+ n q_i )]\ &= \log(n) -\sum ( 1/n +q_i) \log(1+ n q_i)\ &\ge \log(n) -\sum ( 1/n +q_i) n q_i\ & = \log(n) - n\sum q_i^2\ & = \log(n) - n \, \lVert{\bf p}- 1/n\rVert^2_2\ \end {Alinee el} $$</span>

O si lo prefiere

<span class="math-container">$$ H({\bf p}) \ge \log(n)\left(1 - \frac{n}{\log n}\sum q_i^2 \right) $$</span>

Por supuesto, el límite es inútil si <span class="math-container">$\sum q_i^2\ge \frac{\log(n)}{n} $</span>.

Answer 2

Deje $(X,\upsilon)$ ser un número finito de medir el espacio. Deje $\sigma=\frac{\upsilon}{V}$ ser el uniforme de la distribución de probabilidad en $X$ ($V=\upsilon(X)$). Deje $\rho$ ser absolutamente una distribución de probabilidad continua con densidad de $p$. A continuación, la desigualdad $$\begin{align}-h(p)+\ln V&\leq V\lVert p-\tfrac{1}{V}\rVert_2^2\\ h(p)&\stackrel{\mathrm{def}}{=}-\int_X p(x)\ln p(x)\mathrm{d}\upsilon_{x}\\ \lVert p-q\rVert^2_2&\stackrel{\mathrm{def}}{=}\int_X\lvert p(x)-q(x)\rvert^2\mathrm{d}\upsilon_x \end{align}$$ es exactamente la desigualdad entre los $\chi^2$-divergencia y la divergencia KL $$\begin{align}D(\rho\parallel\sigma)&\leq \chi^2(\rho\parallel\sigma)\text{,}\\ D(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}\ln\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}+1\right)\mathrm{d}\sigma_x\\ \chi^2(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-1\right)^2\mathrm{d}\sigma_x\text{;} \end{align}$$ esta desigualdad en el turno de la siguiente manera $$t\ln t - t + 1 \leq (t-1)^2\text{.}$$

Answer 3

Para complementar Leon Bloy la respuesta y mostrar los dependientes de él (y K B Dave) obtenido no puede ser mejorado de forma (es decir, que $c_n = \Omega\!\left(\frac{n}{\log n}\right)$ es necesario): Fix $\varepsilon \in (0,1]$, y suponer sin pérdida de generalidad que $n=2m$ es incluso. Definir $\mathbf{p}^{(\varepsilon)}$ como la función de masa de probabilidad (más de $\{1,\dots,n\}$) tales que $$ \mathbf{p}^{(\varepsilon)}_i = \begin{cases} \frac{1+\varepsilon}{n} & \text{ if } i \leq m \\ \frac{1-\varepsilon}{n} & \text{ if } i > m \end{casos} $$ Tenga en cuenta que $$\begin{align} H(\mathbf{p}^{(\varepsilon)}) &= \sum_{i=1}^m \frac{1+\varepsilon}{n}\log \frac{n}{1+\varepsilon} + \sum_{i=m+1}^n \frac{1-\varepsilon}{n}\log \frac{n}{1-\varepsilon} \\ &= \log n - \frac{1}{2}\left((1+\varepsilon)\log(1+\varepsilon) + (1-\varepsilon)\log(1-\varepsilon)\right) \\ &= \log n - \frac{\varepsilon^2}{2} + o(\varepsilon^3) \tag{1} \end{align}$$ mientras $$ \lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2 = \frac{\varepsilon^2}{n} \etiqueta{2} $$ así que $$ H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - \left(1/2+o_\varepsilon(1)\right)\cdot\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right) \etiqueta{3} $$

Si usted quiere evitar el asymptotics como $\varepsilon \to 0$, todavía se puede arreglar $\varepsilon = 1$ (por ejemplo) y conseguir que $$H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - c'_\varepsilon\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right)$$ for some constant $c'_\varepsilon > 0$.

Answer 4

Esto es simplemente escribir algunas observaciones en los comentarios, para que sea más visible.

---

Como se observa por K B Dave, la desigualdad de leonbloy es una instancia de $\mathrm{KL} \le \chi^2.$ Esta por lo tanto puede ser mejorada mediante el uso de una mayor desigualdad de este formulario. Tenga en cuenta que el resultado de la desigualdad fue mencionado por Clemente en los comentarios originales.

Tenemos $$\mathrm{KL}(P\|Q) = \int \log \frac{\mathrm{d}P}{\mathrm{d}Q} \,\mathrm{d}P \le \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right) \,\mathrm{d}P = \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right)^2 \,\mathrm{d}Q = \log (1 + \chi^2(P\|Q)), $$ where the inequality follows by the concavity of $\registro de$ and Jensen's inequality. Applying the above to this case yields $$H(P) = \log n - \mathrm{KL}(P\|\mathbf{1}/n) \ge \log n - \log(1 + \sum_x \frac{(P_x - 1/n)^2}{1/n}) = \log n - \log (1 + n\|P - \mathbf{1}/n\|_2^2).$$

Tenga en cuenta que si $n\|P - \mathbf{1}/n\|_2^2 \ll 1,$ podemos usar $\log (1 + x) \approx x$ para valores pequeños de a$x$ para recuperar el original obligado.

Podemos, también, las de arriba enlazado en la siguiente forma equivalente: Observar que $1 + \chi^2(P\|Q) = \mathbb{E}_Q[ ({\mathrm{d}P}/{\mathrm{d}Q})^2].$ Nuevo de conectar $Q$ uniforme en $n$ letras de los rendimientos que el último expectativa es simplemente $n\|P\|_2^2,$ y obtenemos que

$$ H(P) \ge - \log \|P\|_2^2,$$ the form stated by Clement. Note that $\|P\|_2 \le 1$ for every distribution, so the form above makes it obvious that the inequalities are non-trivial (in that the RHS is $\ge$ 0) for every $P$.