
Boost Users : 
Subject: [Boostusers] Mersenne Twister 19937 suffers from "lattice effect"?
From: Matthias Nagel (matthias.nagel_at_[hidden])
Date: 20120126 13:57:02
Hello,
I tried to implement a twodimensional multimodal gaussian mixture and used the "mt19937" as the underlying generator. After I drew some samples (from the gaussian mixture) the outcome was not as I expected. After some bug tracking I suppose that the reason is something that is called "lattice effect" in German math literature. A pseudorandom generator suffers from a lattice effect, if one draws a sequence of samples, groups them together into Ndimensional vectors and these Ndimensional vectors are not uniformly distributed in the Ndimensional euclidean space. Does anybody know if the boost implementation has this problem?
In the following, I will present my problem (and my algorithm) more elaborately, especially how I implemented my multimodel gaussian that is the origin of my problem:
Lets assume we want a 2dimensial gaussian mixture with M gaussian.
1) Create three lists (stl vector objects in my case), each with M entries.
The first list stores the weight of each gaussian. The weights sum up to 1.
The second list stores the mean value of each gaussian, i.e. a twodimensional vector (in the mathematical sense, not the stl vector).
The third list stores a 2by2 covariance matrix for each gaussian
2) Create a "mt19937" object, a "discrete_distribution" object and a "normal_distribution" object
The "mt19937" is the common source of randomness for "discrete_distribution" and "normal_distribution".
The "discrete_distribution" produces integers between 0 and M (number of gaussians) according the the given weights
The "normal_distribution" is parameteized with mean = 0 and variance = 1, i.e. it is the standard normal distribtion.
3) Drawing one sample from the gaussian mixture
 Draw one sample from the mt19937 and feed it into the discrete_distribution object. Denote the result by "index".
 Draw a second sample from the mt19937 and feed it into the normal_distribution object. Denote the result by "u".
 Draw a third sample from the mt19937 and feed it into the normal_distribution object. Denote the result by "v".
 Pick up the mean vector and covariance matrix from the lists with respect to "index"
 Transform the vector (u,v) according to the selected mean vector and covariance matrix. Denote the result "(x,y)".
 Return (x,y)
Lets remark that three samples are drawn from mt19937 to obtain one sample from the gaussian mixture.
The result of this algorithm depends on the numbers of gaussians that build the mixture.
1) If M equals 1, the result looks fine. The (x,y) samples form an ellipsoid in the 2dimensional euclidean space
2) If M equals 2, one gaussian looks like an ellipsoid, but it is too small. The second "gaussian" looks like a torus. Obviously all samples (u,v) with large coordinates are assigned to one gaussian, all (u,v) near zero are assigned to the other gaussian
3) If M equals 3, the "gaussians" look like segments of an ellipsoid. In each ellipsoid one third is missing.
4) For higher M the result is not correct either, but not as vivid and easily to explain as the "small" cases.
As soon as I switch to random_device instead of mt19937 the phenomena disappears.

Matthias Nagel
WillyAndreasAllee 1, Zimmer 506
76131 Karlsruhe
Telefon: +49 721 86951506
Telefax: +49 721 86954506
Mobil: +49 151 15998774
eMail: matthias.nagel_at_[hidden]
ICQ: 499797758
Skype: nagmat84
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net