# Maximum Entropy Discrete Distribution

In Pattern Recognition and Machine Learning the author uses Lagrange multipliers to find the discrete distribution with maximum entropy.

Entropy is defined by;

$$H=-\sum_i p(x_i)\ln(p(x_i))$$

and the constraint used in the optimisation is that the probabilities sum to 1.

Therefore the Lagrangian is defined as

$$\widetilde{H}=-\sum_i p(x_i)\ln(p(x_i))+\lambda(\sum_i p(x_i)-1)$$

Taking the first partial derivative and setting it equal to zero gives $$p(x_i)=1/M$$, where $$M$$ is the number of values that $$x_i$$ takes on.

For the first partial derivative I got $$\frac{\partial \widetilde{H}}{\partial p(x_i)}=-\sum_i [\ln(p(x_i))+1]+\lambda M$$

The author then states that to verify the stationary point is a maximum we evaluate the second partial derivative which gives;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)}=-I_{ij}\frac{1}{p_(x_i)}$$

where $$I_{ij}$$ are the elements of the identity matrix.

I would like to know why this is the second partial derivative (how to derive it) and why it means that the stationary point is a maximum.

I think the author may be talking about the hessian not the second partial derivative since they give a matrix not a function.

Following this line of reasoning if I take the second derivative I get;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_i)}=-\sum_i \frac{1}{p(x_i)}$$

If I take the second partial derivative wrt $$j$$ for $$i\ne j$$ I get;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)}=0 \quad \quad (i \ne j)$$

Therefore;

$$\frac{\partial^2 \widetilde{H}}{\partial p(x_i) \partial p(x_j)} = -I_{ij} \sum_i \frac{1}{p(x_i)}$$

But the summation is missing in the given expression for the hessian.

You have to keep in mind that the index in the summation is a "dummy index", it is only a placeholder for $$1,2,3,\cdots$$. Therefore, it is not the same $$i$$ that appears in the derivative! We can clarify our notation by writing the indices with different letters:

$$\tilde H=-\sum_k p(x_k)\ln p(x_k) +\lambda\left(\sum_k p(x_k)-1\right)$$

Now, we differentiate on $$p(x_i)$$. The terms $$k\neq i$$ vanish because they don't depend on $$p(x_i)$$, so we only have to differentiate the the term with $$k=i$$:

$$\frac{\partial\tilde H}{\partial p(x_i)}=-1-\ln p(x_i)+\lambda$$

Now, if we differentiate on $$p(x_i)$$ again, we get:

$$\frac{\partial^2\tilde H}{\partial p(x_i)^2}=-\frac{1}{p(x_i)}$$

On the other hand, if we differentiate on $$p(x_j)$$ where $$j\neq i$$:

$$\frac{\partial^2\tilde H}{\partial p(x_i)\partial p(x_j)}=0$$

We can express this compactly as:

$$\frac{\partial^2\tilde H}{\partial p(x_i)\partial p(x_j)}=-I_{ij}\frac{1}{p(x_i)}$$

The matrix with elements given by this formula is, as you said, the hessian matrix of this function. Since it's a diagonal matrix with negative entries only, this is a negative-definite matrix, which implies that this functions achieves a global maximum whenever its gradient is zero.

• Why does setting the gradient equal to zero give $p(x_i)=1/M$? I get $p(x_i)=e^{\lambda - 1}$. Wait since $\lambda$ is a constant I think this means the $p(x_i)$ are all equal and since there are M of them and they sum to one they are all $p(x_i)=1/M$ May 25, 2021 at 10:37
• @tail_recursion You are 100% correct. The answer $p(x_i)=e^{-\lambda-1}$ is a function of the Lagrange multiplier $\lambda$, which you have to find by imposing the restriction $\sum_i p(x_i)=1$. And a shortcut to this is noticing that $p(x_i)$ is constant and adds up to one, as you did. May 25, 2021 at 14:00