This work was inspired by this tech report.

Contributions to a mixture of Gaussians puzzle

David MacKay (with Chris Williams)

The puzzle

Consider a mixture of spherical gaussians in d dimensions.

P(x) = sum   p_c   Normal( x ; mu_c, sigma_c )
what is the maximum number of maxima that P(x) can have? Clearly C maxima is easy; but can there be more than C maxima?

Prof Hans Duistermaat (Utrecht), a colleague of Chris Williams's, found a P(x) in two dimensions with C=3 gaussians and (4/3)C=4 maxima.

Here I show that it's possible (in two or more dimensions) to have of order (5/3)C maxima.

My Kekule solution

We place C gaussians on the points of a Kekule lattice. kekulegaussians0.3 For narrow diameters, such as shown above, there are C maxima.

For broader diameters (0.450486 is shown here, where the length of an edge in the lattice is 1), new maxima appear in the centres of the triangles, so there are roughly (5/3)C maxima (neglecting boundary effects). kekulegaussians As the size of the lattice increases, the size of the boundary increases only as sqrt(C) so asymptotically, the number of maxima approaches (5/3)C.

postscript file (0.3) postscript file (0.450486)

Thu 23/10/03 (c) David MacKay

David MacKay
Last modified: Fri Jan 16 12:44:55 2004