Un límite superior de la entropía binaria

Question

La entropía binaria viene dada por $$H_{\mathrm b}(p) = -p \log_2 p - (1 - p) \log_2 (1 - p), \hspace{6 mm} p \le \frac{1}{2}$$ ¿Cómo puedo demostrar que $$H_{\mathrm b}(p) \le 2 \sqrt{p(1-p)}$$

Answer 1

Dado $I=(0,1)$ para cualquier $x\in I$ dejar $g(x)=-x\log x$ y $f(x)=g(x)+g(1-x)$ .

Obviamente $f\in C^{\infty}(I)$ , $\,f(x)=f(1-x)$ , $\,f>0$ y $$ \lim_{x\to 0^+}f(x)=\lim_{x\to 1^-}f(x) = 0. $$ Tenemos $f'(x)=\log(1-x)-\log(x)$ Por lo tanto:

$$\begin{eqnarray*} \frac{d}{dx}\frac{f(x)^2}{x(1-x)}&=&f(x)\cdot\frac{-x\log x+(1-x)\log(1-x)}{x^2(1-x)^2}\\&=&\frac{g(x)^2-g(1-x)^2}{x^2(1-x^2)}.\tag{1}\end{eqnarray*}$$ Desde $g(x)>g(1-x)$ en $J=\left(0,\frac{1}{2}\right)$ (la prueba de este hecho viene después), la función $\frac{f(x)^2}{x(1-x)}$ está aumentando sobre $J$ Por lo tanto:

$$ f(x)\leq 2\cdot f\left(\frac{1}{2}\right)\cdot\sqrt{x(1-x)}=\color{blue}{\left(2\log 2\right)}\sqrt{x(1-x)} \tag{2}$$

sigue. Volviendo a la parte que falta: obviamente $g(x)-g(1-x)$ se desvanece en $0,\frac{1}{2},1$ . Para demostrar que estos puntos son los únicos ceros, basta con comprobar que $h(x)=g(x)-g(1-x)$ es cóncavo sobre $J$ . Bastante fácil:

$$ \frac{d^2}{dx^2}h(x) = \frac{2x-1}{x(1-x)}.\tag{3} $$ La prueba se termina observando que $f(p)=\log(2)\cdot H_{\mathrm b}(p)$ .

---

Una aproximación muy ajustada para la función de entropía binaria viene dada por:

$$ H_{\mathrm{b}}(p) \approx \left(4p(1-p)\right)^{\frac{3}{4}}.\tag{4}$$

No se mantiene como límite superior o inferior, el valor absoluto de la diferencia entre el lado derecho y el lado izquierdo es siempre menor que $8\cdot 10^{-3}$ .

Answer 2

Puede utilizar la desigualdad $\ln(x)\le \sqrt{x-1}$ para cualquier $x\ge 1$ . Precisamente, hay que tener en cuenta que \begin{equation} \begin{aligned} H(p)&=p\ln\frac{1}{p} +(1-p)\ln\frac{1}{1-p} \\ &\le p\sqrt{\frac{1}{p}-1} +(1-p)\sqrt{\frac{1}{1-p}-1}\\ &= 2\sqrt{p(1-p)} \end{aligned} \end{equation} Aquí el logaritmo es a base de exp. natural.

Answer 3

En realidad, esta desigualdad no es trivial. He aquí un esquema de la prueba. Sabemos que hay tres casos de igualdad, así que para deshacernos de los de los extremos tomamos $\frac{H(p)}{2\sqrt{p(1-p)}}$ . Al diferenciar con respecto a $p$ y analizando lentamente el resultado (álgebra elemental más la desigualdad $x-\frac{1}{2}x^2 \le \ln(1+x) \le x$ para $x \ge 0$ ) es posible demostrar que es decreciente para $p > \frac{1}{2}$ que por simetría significa que es máxima cuando $p = \frac{1}{2}$ . No es tan difícil pero no es elegante.

Answer 4

Otras respuestas han dado una prueba de la desigualdad. Lo que encuentro problemático en estos casos no es la prueba de algo ya dado (aunque es importante, por supuesto), sino cómo se llegó a esta afirmación, que entonces requiere una prueba.

Entonces, ¿cómo se llega a algo así en primer lugar?

$$H_{\mathrm b}(p) \le 2 \sqrt{p(1-p)}$$

y luego tratar de demostrarlo.

Mi respuesta inicial (borrada) intentaba trabajar de esa manera. No tengo una prueba de esta manera (todavía), pero puedo ofrecer algo más en este punto (que también puede conducir a una prueba).

Verá, cuando uno sabe lo que espera, puede manipular y llegar a una demostración (un método muy utilizado por Arquímedes, por ejemplo, en el tratado "Teoremas mecánicos"). Pero cómo llegar a este enunciado inicialmente. Una forma de hacerlo es la siguiente:

1. Tenga en cuenta que cada lado es un media (generalizada)
2. Se sabe que las medias (generalizadas) tienen ciertas desigualdades entre ellas
3. reordenar: $H_{\mathrm b}(p)/2 \le \sqrt{p(1-p)}$
4. set $x = -p\log p$ , $y = -q\log q$ , $p+q=1$ , $f(x) = -x\log x$ es convexo para $0 \le x \le 1$
5. $\frac{x+y}{2} \le \sqrt{pq}$
6. o la media aritmética de $x,y$ $AM(x,y)$ en relación con la media geométrica de $p,q$ $GM(p,q)$
7. alternativamente se puede ver la propia función de entropía como una media (generalizada), a veces referida como media entrópica
8. observe la desigualdad GM-AM $GM(a,b) \le AM(a,b)$
9. así que tenemos esto

$$GM(x,y) \le AM(x,y) ?\le GM(p,q) \le AM(p,q) = \frac{1}{2}$$

donde vemos una secuencia de medios y su relación, faltando una parte (por demostrar). Pero esto da una pista de las desigualdades que hay que esperar y tratar de demostrar. En lugar de resultados prefabricados que sólo requieren verificación (incluso en forma de pruebas).

Para una referencia más amplia, véase esto hoja de trucos sobre desigualdades

Espero que sea útil.

P.D. Puede que publique una prueba en este sentido, hasta ahora no se me ha ocurrido ninguna, pero tampoco he buscado lo suficiente.

actualización ( intento erróneo )

Un esbozo de prueba. (nótese que podemos suponer $0 < p \le 1/2$ En cuanto a $p=0$ es fácil verificar la desigualdad)

Primero tenemos, (todos los logaritmos son de base $2$ ):

$\log x \le x-1$ , para $x > 0$ , $-p \log p \le -\log p \le 1$ , $0 < p \le 1/2$

Entonces:

$$\log \sqrt{pq} \le \sqrt{pq}-1 \tag{1}$$ $$1+\frac{\log p+\log q}{2} \le \sqrt{pq} \tag{2}$$ $$1-\frac{-\log p-\log q}{2} \le \sqrt{pq} \tag{3}$$

* de $(3)$ a $(4)$ La simetría se utiliza para $0 < p \le 1/2$ * de $(4)$ a $(5)$ desigualdad $-p \log p \le -\log p$ se utiliza