How to prove this Gaussian Mixture inequality? (Fitting/Overfitting) Let f[x] be a Gaussian Mixture pdf with n terms of uniform weight, means $\{\mu_{1},...,\mu_{n}\}$, and corresponding variances $\{\sigma_{1},...,\sigma_{n}\} $:
$$f(x)\equiv\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\sqrt{2\pi\sigma_{i}^{2}}}e^{-\frac{(x-\mu_{i})^{2}}{2\sigma_{i}^{2}}}$$
It seems intuitive that the log-liklihood sampled at the n Gaussian centers would be greater than (or equal to) the mean log-liklihood:
$$\frac{1}{n}\sum_{j=1}^{n}ln(f(\mu_{j}))\geq\int f(x)ln(f(x))dx$$
This is obviously true for small variances (each $\mu_{i}$ is on top of a narrow Gaussian) and for very large variances (all the $\mu_{i}$'s are atop one broad Gaussian together), and it's been true for every set of $\mu_i$'s and $\sigma_i$'s I've generated and optimized, but I can't figure how to prove that it's always true.  Help?
 A: This is more of an extended comment, so take it as such.
Define:
$$
f(x) \equiv \frac{1}{n} \sum_{i = 1}^n \mathcal{N}\left(x | x_i, \sigma_i^2 \right)
$$
(I am using the standard notation for Gaussian distributions).
You want to prove that:
$$
\frac{1}{n} \sum_{i = 1}^n \log f(x_i) - \int f(x) \log f(x) dx \ge 0
$$
which is
$$
\left\{\frac{1}{n} \sum_{i = 1}^n \log f(x_i)\right\} + \mathcal{H}[f] \ge 0.
$$
Due to Jensen's inequality (see for example Huber et al., On Entropy Approximation for Gaussian Mixture Random Vectors, 2008),
$$
\mathcal{H}[f] \ge -\frac{1}{n} \sum_{i = 1}^n \log \int f(x) \mathcal{N}(x | x_i, \sigma_i^2) dx
= -\frac{1}{n} \sum_{i = 1}^n \log g_i(x_i)
$$
with $g_i(x) \equiv \frac{1}{n} \sum_{j = 1}^n \mathcal{N}\left(x | x_j, \sigma_i^2 + \sigma_j^2 \right)$, which comes from the convolution of two Gaussian densities. So we get:
$$
\left\{\frac{1}{n} \sum_{i = 1}^n \log f(x_i) \right\} + \mathcal{H}[f] \ge 
\frac{1}{n} \sum_{i = 1}^n \log \frac{f(x_i)}{g_i(x_i)}.
$$
Interestingly, the $g_i$ are still mixtures of Gaussians with component means equal to the ones in $f$, but each component of $g_i$ has a strictly larger variance than its corresponding component in $f$.
Can you do anything with this?
A: I think I got it. It only takes elementary steps, although you need to combine them right.
Let's denote by $f_i$ the density of $i$-th Gaussian, that is $\frac{1}{\sqrt{2\pi \sigma_i^2}}e^{\frac{(x-\mu_i)^2}{2\sigma_i^2}}$
We  start off with Jensen's Inequality.
The function $g(x) = x log(x) $ is convex, hence we have:
$f(x) \log(f(x)) \leq \frac{1}{n}\sum_{i=1}^n f_i(x) \log(f_i(x))$. After integrating we get:
$$
\int f(x)\log(f(x)) dx \leq \frac{1}{n} \sum_{i=1}^n \int f_i(x) \log(f_i(x)) dx 
$$
Edit: The inequality below is wrong and so is the solution itself
Now the RHS. For all $i$ we have $f \geq f_i$, so:
$$log(f(\mu_i)) \geq log(f_i(\mu_i))$$ 
Hence:
$$
\frac{1}{n} \sum_{i=1}^n log(f(\mu_i)) \geq \frac{1}{n}\sum_{i=1}^n log(f_i(\mu_i))
$$
We are left to prove:
$$
\frac{1}{n}\sum_{i=1}^n log(f_i(\mu_i)) \geq \frac{1}{n}\sum_{i=1}^n f_i(x) \log(f_i(x))
$$
But we have:
$$
log(f_i(\mu_i)) = \int f_i(x) log(f_i(\mu_i)) dx \geq \int f_i(x) log(f_i(x)) dx
$$
Summing over $i$ and dividing by $n$ we get what we needed
