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 )
      c=1..C

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. 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). 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