randmomR produces only even values

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

randmomR produces only even values

Martin Drautzburg
Hello all


When I read:

mkStdGen :: Int -> StdGen

The function mkStdGen provides an alternative way of producing an initial generator, by mapping an Int into a generator.
Again, distinct arguments should be likely to produce distinct generators.

I thought, that

> fst $ R.randomR (1,10) (R.mkStdGen s)

should get me a random value between 1 and 10 and that I get different values depending on the seed s. But this

> length $ filter even $ map (\s -> fst $ randomR (1::Int,10) (mkStdGen s))[1..1000]

gives my 1000, i.e. all random numbers are even numbers.

However, when I use random instead of randomR

> length $ filter even $ map (\s -> fst $ random (mkStdGen s) ::Int)[1..1000]

I get 499 (okay)

Why is that so?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Lyndon Maydwell
I've replicated this and it does seem very strange, and possibly even a bug.

I would guess that most people don't encounter this issue as a generator is usually only seeded once, then threaded throughout generation. Not seeded for once for every random output. The other common practice is that generators are usually seeded on far more random input values than a list of ascending ints.

Seed behaviour:

    main = mapM_ print (map p l)
    p  x = length $ filter even $ map (\s -> fst $ randomR (1::Int,10) (mkStdGen s)) x
    l    = map ls [1..10]
    ls x = map (\y -> x * y * 10) [1..1000]

    1000
    1000
    1000
    1000
    1000
    894
    766
    670
    596
    536


Still, I am very surprised by this behaviour. I couldn't find any reference to this behaviour in[1], which is supposedly what the System.Random implementation is based on.

Does anyone else have an explanation?


 - Lyndon



On Sat, Oct 31, 2015 at 5:43 AM, martin <[hidden email]> wrote:
Hello all


When I read:

mkStdGen :: Int -> StdGen

The function mkStdGen provides an alternative way of producing an initial generator, by mapping an Int into a generator.
Again, distinct arguments should be likely to produce distinct generators.

I thought, that

> fst $ R.randomR (1,10) (R.mkStdGen s)

should get me a random value between 1 and 10 and that I get different values depending on the seed s. But this

> length $ filter even $ map (\s -> fst $ randomR (1::Int,10) (mkStdGen s))[1..1000]

gives my 1000, i.e. all random numbers are even numbers.

However, when I use random instead of randomR

> length $ filter even $ map (\s -> fst $ random (mkStdGen s) ::Int)[1..1000]

I get 499 (okay)

Why is that so?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Martin Drautzburg
I filed an issue on github (https://github.com/haskell/random/issues). Maybe the authors can shed some light on this.

Am 10/30/2015 um 11:40 PM schrieb Lyndon Maydwell:

> I've replicated this and it does seem very strange, and possibly even a bug.
>
> I would guess that most people don't encounter this issue as a generator is usually only seeded once, then threaded
> throughout generation. Not seeded for once for every random output. The other common practice is that generators are
> usually seeded on far more random input values than a list of ascending ints.
>
> Seed behaviour:
>
>     main = mapM_ print (map p l)
>     p  x = length $ filter even $ map (\s -> fst $ randomR (1::Int,10) (mkStdGen s)) x
>     l    = map ls [1..10]
>     ls x = map (\y -> x * y * 10) [1..1000]
>
>     1000
>     1000
>     1000
>     1000
>     1000
>     894
>     766
>     670
>     596
>     536
>
>
> Still, I am very surprised by this behaviour. I couldn't find any reference to this behaviour in[1], which is supposedly
> what the System.Random implementation is based on.
>
> Does anyone else have an explanation?
>
>
>  - Lyndon
>
>
> [1] - https://en.wikipedia.org/wiki/Linear_congruential_generator
>
> On Sat, Oct 31, 2015 at 5:43 AM, martin <[hidden email] <mailto:[hidden email]>> wrote:
>
>     Hello all
>
>
>     When I read:
>
>     mkStdGen :: Int -> StdGen
>
>     The function mkStdGen provides an alternative way of producing an initial generator, by mapping an Int into a generator.
>     Again, distinct arguments should be likely to produce distinct generators.
>
>     I thought, that
>
>     > fst $ R.randomR (1,10) (R.mkStdGen s)
>
>     should get me a random value between 1 and 10 and that I get different values depending on the seed s. But this
>
>     > length $ filter even $ map (\s -> fst $ randomR (1::Int,10) (mkStdGen s))[1..1000]
>
>     gives my 1000, i.e. all random numbers are even numbers.
>
>     However, when I use random instead of randomR
>
>     > length $ filter even $ map (\s -> fst $ random (mkStdGen s) ::Int)[1..1000]
>
>     I get 499 (okay)
>
>     Why is that so?
>     _______________________________________________
>     Beginners mailing list
>     [hidden email] <mailto:[hidden email]>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Andrew Bernard
In reply to this post by Martin Drautzburg
According to the package documentation for System.Random:

This implementation uses the Portable Combined Generator of L'Ecuyer [System.Random] for 32-bit computers, transliterated by Lennart Augustsson.

The paper in question is given as:

Pierre L'Ecuyer, /Efficient and portable combined random number generators/, Comm ACM, 31(6), Jun 1988, pp742-749

Does anybody have a copy of this paper?

The use of an incrementing list of integers to seed each generation is definitely unusual, as Lyndon has pointed out, and is likely to be the root of the observed behaviour. Having the paper in question would probably clarify this.

Andrew


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Henk-Jan van Tuyl
On Sun, 01 Nov 2015 03:24:07 +0100, Andrew Bernard  
<[hidden email]> wrote:

> According to the package documentation for System.Random:
>
> This implementation uses the Portable Combined Generator of L'Ecuyer  
> [System.Random] for 32-bit computers, transliterated by Lennart  
> Augustsson.
>
> The paper in question is given as:
>
> Pierre L'Ecuyer, /Efficient and portable combined random number  
> generators/, Comm ACM, 31(6), Jun 1988, pp742-749
>
> Does anybody have a copy of this paper?

The first result of a search with startpage was:
   http://www.iro.umontreal.ca/~lecuyer/myftp/papers/cacm88.pdf

Regards,
Henk-Jan van Tuyl


--
Folding@home
What if you could share your unused computer power to help find a cure? In  
just 5 minutes you can join the world's biggest networked computer and get  
us closer sooner. Watch the video.
http://folding.stanford.edu/


http://Van.Tuyl.eu/
http://members.chello.nl/hjgtuyl/tourdemonad.html
Haskell programming
--
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Chaddaï Fouché
I really don't think this is much of a flaw. It may need to be reinforced that this package (and most random libraries) doesn't provide _any_ guarantee if you use it like that (restrain the first output with randomR of lots of random generators initialized by very particular seeds sequence).

The guarantee the paper will be talking about will be for a sequence of random numbers generated by one generator and this behave normally as shown by :

> (minimum &&& maximum) . map (length . filter even . take 1000 . randomRs (1,10) . mkStdGen) $ [1..1000]
(432,553)

In other words, if there's any problem it is only one of documentation (just a warning in the haddock ought to be sufficient).
--
Jedaï

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Dominic Steinitz-2
In reply to this post by Martin Drautzburg
> http://article.gmane.org/gmane.comp.lang.haskell.beginners/15925

I do think this is a flaw and catches many people out despite apparently
being well documented. And it's something one probably wants e.g. to run
multiple Markov Chain Monte Carlo simulations in parallel.

Some further information here:
https://github.com/haskell/random/issues/30#issuecomment-153647055

Dominic

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: randmomR produces only even values

Chaddaï Fouché
The System.Random is just not very good, you should not use it if you need something fast or cryptographically secure... But as a first choice for just a few random numbers it's good enough and it was chosen specifically for its capability to split a generator into two, so that's probably what you should be using if you're going to do simulations in parallel with System.Random. Or use random seeds at least !
This is specifically an interaction between random*R* and mkStdGen with low seeds (random don't seem to have this particular flaw), since we're still using a pseudo-random generator, we ought to be pretty careful in the way we use it (those have always been touchy beasts) and this particular usage seems to be a bad counter-example of what to do with a PRNG.

If we can improve System.Random to avoid this particular misbehavior we should but using a PRNG in this fashion and hoping for good randomness from the result is probably a bad idea in the first place.

Le mer. 4 nov. 2015 à 11:00, Dominic Steinitz <[hidden email]> a écrit :
> http://article.gmane.org/gmane.comp.lang.haskell.beginners/15925

I do think this is a flaw and catches many people out despite apparently
being well documented. And it's something one probably wants e.g. to run
multiple Markov Chain Monte Carlo simulations in parallel.

Some further information here:
https://github.com/haskell/random/issues/30#issuecomment-153647055

Dominic

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners