[random] Bias in boost::random generators?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, I'm experiencing a bug with the boost::random library. Apparently, most generators, together with uniform_int<>, produce heavily biased sequences. I'm sending attached a small test program which generates several random walks on a lattice, starting from the center, and counts how many times a site has been visited. It uses both the boost::random generators, and the tr1::random generators from GCC 4.3, and writes the separate counts in the files "bcount" and "tcount", respectively. A plot of the output with boost::random can be seen here: http://dl.getdropbox.com/u/280654/boost_random.png There is an obvious tendency towards the (0,0) corner of the lattice... With tr1::random, everything looks normal: http://dl.getdropbox.com/u/280654/tr1_random.png Not to mention I used the same generator (mt19937) with the same seed value in both cases, which should have given the exact same sequence! I obtain similar results with other generators, except with minstd_rand, where the sequences from both libraries are the same. This lead me to conclude that the problem is with the generators themselves, not with uniform_int<>. More info on my end: platform: x86_64 intel, GNU/Linux GCC: 4.3.3 Boost: 1.37 Best regards, Tiago -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkoXu/8ACgkQBNxGHvNv411+4QCfSfgo1Mu1lROQhwPnGxtEoq51 C1MAn1GJi0BYVtyExFmfdsxvtpKOM/fk =CsWe -----END PGP SIGNATURE-----
AMDG Tiago de Paula Peixoto wrote:
I'm experiencing a bug with the boost::random library. Apparently, most generators, together with uniform_int<>, produce heavily biased sequences.
I'm sending attached a small test program which generates several random walks on a lattice, starting from the center, and counts how many times a site has been visited. It uses both the boost::random generators, and the tr1::random generators from GCC 4.3, and writes the separate counts in the files "bcount" and "tcount", respectively.
A plot of the output with boost::random can be seen here:
http://dl.getdropbox.com/u/280654/boost_random.png
There is an obvious tendency towards the (0,0) corner of the lattice...
With tr1::random, everything looks normal:
http://dl.getdropbox.com/u/280654/tr1_random.png
Not to mention I used the same generator (mt19937) with the same seed value in both cases, which should have given the exact same sequence!
I obtain similar results with other generators, except with minstd_rand, where the sequences from both libraries are the same. This lead me to conclude that the problem is with the generators themselves, not with uniform_int<>.
The problem is in uniform_int<>. The behavior of uniform_int depends on the range of the generator. In Christ, Steven Watanabe
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Steven Watanabe wrote:
I obtain similar results with other generators, except with minstd_rand, where the sequences from both libraries are the same. This lead me to conclude that the problem is with the generators themselves, not with uniform_int<>.
The problem is in uniform_int<>. The behavior of uniform_int depends on the range of the generator.
It is true, I don't see this problem when using a uniform_real<> distribution. But I do see it with uniform_smallint<> as well. In any case, uniform_int<> and uniform_smallint<> are quite broken, if they can't be uniform for such a small range. Cheers, Tiago -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkoY+h8ACgkQBNxGHvNv413UNwCfRMG87zLMCGTHFwCTZwf5lO3Q LGUAnRXGPnGiR+0TglZ2Fau0Y9j4n2rX =iL6U -----END PGP SIGNATURE-----
Tiago de Paula Peixoto:
In any case, uniform_int<> and uniform_smallint<> are quite broken, if they can't be uniform for such a small range.
They are (quite broken). http://lists.boost.org/Archives/boost/2008/01/132347.php http://lists.boost.org/Archives/boost/2006/03/102027.php http://lists.boost.org/Archives/boost/2004/08/70611.php http://lists.boost.org/Archives/boost/2006/08/108839.php Unfortunately, Jens Maurer has stopped maintaining Boost.Random, and random numbers are tricky enough so noone else with the sufficient expertise has taken over.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Peter Dimov wrote:
Tiago de Paula Peixoto:
In any case, uniform_int<> and uniform_smallint<> are quite broken, if they can't be uniform for such a small range.
They are (quite broken).
http://lists.boost.org/Archives/boost/2008/01/132347.php http://lists.boost.org/Archives/boost/2006/03/102027.php http://lists.boost.org/Archives/boost/2004/08/70611.php http://lists.boost.org/Archives/boost/2006/08/108839.php
Unfortunately, Jens Maurer has stopped maintaining Boost.Random, and random numbers are tricky enough so noone else with the sufficient expertise has taken over.
Well, I'll use tr1::random from now on, but I think there should be at least a big red warning in the documentation website about this, specially if no one will address these problems in the near future... I've been using this library for quite some time, and I had no idea that it was unmaintained. Cheers, Tiago -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkoZSNoACgkQBNxGHvNv413DZgCgwRXLhGJgeM42ndIaJLlp3DSA rIEAn2O+vxernuTzV1jTyZhRohwHlmoi =wG/5 -----END PGP SIGNATURE-----
AMDG Tiago de Paula Peixoto wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Peter Dimov wrote:
Tiago de Paula Peixoto:
In any case, uniform_int<> and uniform_smallint<> are quite broken, if they can't be uniform for such a small range.
They are (quite broken).
http://lists.boost.org/Archives/boost/2008/01/132347.php http://lists.boost.org/Archives/boost/2006/03/102027.php http://lists.boost.org/Archives/boost/2004/08/70611.php http://lists.boost.org/Archives/boost/2006/08/108839.php
Unfortunately, Jens Maurer has stopped maintaining Boost.Random, and random numbers are tricky enough so noone else with the sufficient expertise has taken over.
Well, I'll use tr1::random from now on, but I think there should be at least a big red warning in the documentation website about this, specially if no one will address these problems in the near future...
uniform_int is now fixed in the trunk. In Christ, Steven Watanabe
AMDG Tiago de Paula Peixoto wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Steven Watanabe wrote:
I obtain similar results with other generators, except with minstd_rand, where the sequences from both libraries are the same. This lead me to conclude that the problem is with the generators themselves, not with uniform_int<>.
The problem is in uniform_int<>. The behavior of uniform_int depends on the range of the generator.
It is true, I don't see this problem when using a uniform_real<> distribution. But I do see it with uniform_smallint<> as well.
In any case, uniform_int<> and uniform_smallint<> are quite broken, if they can't be uniform for such a small range.
In uniform_smallint, the bias is intentional. You should only use it if you are willing to accept the bias to gain performance. For such a small range, they are both "close" to being uniform, but because of the way you are using it, the bias is magnified. If you just counted the number of each value, the difference should not be huge. In Christ, Steven Watanabe
participants (3)
-
Peter Dimov -
Steven Watanabe -
Tiago de Paula Peixoto