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

**Question:**

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

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