Cómo minimizar $\sum p_b \ln{p_b}$?

Question

Tengo un conjunto múltiple $A = \{a_1,\dots,a_n\}$ de los números enteros. Deje $q = P(a_i = a_j)$ al $i$ $j$ son elegidos de forma independiente y de manera uniforme de $\{1,\dots, n\}$. Deje $B$ el conjunto de los números enteros en $A$. Sabemos que $|B| \leq n$. Por último vamos a $p_b = P(a_i = b)$ al $i$ es elegido de manera uniforme de $\{1,\dots, n\}$.

Cómo lata pequeña de $-\sum_{b \in B} p_b \ln{p_b}$ ser como una función de la $q$$n$?

Answer 1

Sólo para hacer contacto con la wikipedia, voy a notar que $S=-\sum p_b \ln p_b$ es la entropía y $q$ es el índice de Simpson. Como otros han señalado, hay algún problema con la existencia de sólo ciertos permitió $(n,q)$ pares, por lo que para evitar esto vamos a suponer que $n$ es grande y $q$ no está demasiado cerca de 0 o 1.

Para maximizar la entropía, que desea extender la distribución tanto como sea posible, sin tener los Simpson índice de caída por debajo de $q$. La distribución que hace esto tiene $p_1 \approx \sqrt{q}$, $p_i=1/n$ para $i=2,\ldots,\sim n(1-\sqrt{q})$. (Obviamente, para un finito $n$, $p_1$ tendrá que ser ligeramente menor que $\sqrt{q}$.) Esto le da a $S\sim (1-\sqrt{q})\ln n$.

Para minimizar la entropía, usted quiere concentrarse en la distribución tanto como sea posible, sin tener los Simpson índice de ir por encima de $q$. Para ello, vamos a $|B|=\lceil 1/q\rceil$, y ha $p_1, \ldots, p_{\lfloor 1/q \rfloor}$ cerca de $q$, $p_{\lceil 1/q\rceil}$ llegar el pequeño resto de la probabilidad. Esto le da a $S\sim -\ln q$.

Tenga en cuenta que esto también funciona a la inversa, dado $n$$S$, estas mismas distribuciones de dar el máximo y el mínimo posible de los valores de $q$.

Answer 2

Un principio:

En primer lugar, un conjunto $B:=[m]$ es dado, y para cada una de las $k\in B$ tenemos una multiplicidad $f(k)\in{\mathbb N}_{\geq1}$. El par $(B,f)$ constituye el conjunto múltiple $A$ en su pregunta.

Poner $\sum_{k=1}^m f(k)=:n$. Entonces la probabilidad de que usted elija el valor de $k$ en la elección de un elemento aleatorio de$A$${f(k)\over n}=:p_k$, y la probabilidad de $q$ que usted elija dos valores iguales en dos decisiones independientes está dada por $$q={1\over n^2}\sum_{k=1}^m f^2(k)=\sum_{k=1}^m p_k^2\ .$$ De ello se sigue que hemos de maximizar/minimizar la función $$H(p):=-\sum_{k=1}^m p_k\>\log p_k$$ dentro de las limitaciones $$p_k\geq0,\quad \sum_{k=1}^m p_k=1,\quad \sum_{k=1}^m p_k^2=q\ .$$ Consideramos esto como un continuo problema de optimización. Dependiendo del valor de $q$, la esfera de $\sum_k p_k^2=q$ pueden cruzar el simplex $p_k\geq0$, $\>\sum_k p_k=1$ en una forma complicada, y el establecimiento de un simple multiplicador de Lagrange esquema no se tomen la atención de la situación global, tanto más, cuanto que llevará a la trascendental ecuaciones. Pero parece que el siguiente Lema es cierto: Al $H$ es extremal en un admisibles ${\bf p}$, entonces no podemos tener tres valores de $p_1>p_2>p_3>0$. Esto es corroborado por la siguiente figura que muestra las líneas de nivel de $H$ en un subsimplex $p_1+p_2+p_3=s$ $s=0.4$ y en la red de una curva de $p_1^2+p_2^2+p_3^2={\rm const.}\ $. Uno puede ver que la curva roja es tangente a las líneas de nivel de $H$ sólo en los puntos donde dos de las $p_k$ son iguales.

Por lo tanto, habría que hacer lo siguiente: Para todas las opciones posibles de $m_1\geq0$, $m_2\geq0$ con $m_1+m_2\leq m$ resolver $$m_1p_1+m_2p_2=1,\qquad m_1p_1^2+m_2p_2^2=q$$ para$p_1$$p_2$. Cuando la admisibilidad de una solución existe calcular el correspondiente $$H({\bf p})=-m_1\> p_1\log p_1-m_2\>p_2\log p_2\ .$$ El más pequeño y el más grande de los valores encontrados en este camino son los extremal valores de $H$ bajo ciertas restricciones.