The seeds generated by split are not independent

[idontgetoutmuch]

See - https://ghc.haskell.org/trac/ghc/ticket/3620 (and also https://ghc.haskell.org/trac/ghc/ticket/3575) I just ran the example https://ghc.haskell.org/trac/ghc/attachment/ticket/3620/RandomnessTest2.hs and got

Generated 2000 pairs of numbers from 0 to 1 -- 1299 pairs contained equal numbers and we expected about 1000.
Generated 3000 pairs of numbers from 0 to 2 -- 187 pairs contained equal numbers and we expected about 1000.
Generated 4000 pairs of numbers from 0 to 3 -- 101 pairs contained equal numbers and we expected about 1000.
Generated 5000 pairs of numbers from 0 to 4 -- 271 pairs contained equal numbers and we expected about 1000.
Generated 6000 pairs of numbers from 0 to 5 -- 359 pairs contained equal numbers and we expected about 1000.
Generated 7000 pairs of numbers from 0 to 6 -- 1401 pairs contained equal numbers and we expected about 1000.
Generated 8000 pairs of numbers from 0 to 7 -- 158 pairs contained equal numbers and we expected about 1000.
Generated 9000 pairs of numbers from 0 to 8 -- 53 pairs contained equal numbers and we expected about 1000.
Generated 10000 pairs of numbers from 0 to 9 -- 535 pairs contained equal numbers and we expected about 1000.
Generated 11000 pairs of numbers from 0 to 10 -- 0 pairs contained equal numbers and we expected about 1000.
Generated 12000 pairs of numbers from 0 to 11 -- 70 pairs contained equal numbers and we expected about 1000.
Generated 13000 pairs of numbers from 0 to 12 -- 0 pairs contained equal numbers and we expected about 1000.
Generated 14000 pairs of numbers from 0 to 13 -- 0 pairs contained equal numbers and we expected about 1000.
Generated 15000 pairs of numbers from 0 to 14 -- 783 pairs contained equal numbers and we expected about 1000.

On the other hand the example from http://publications.lib.chalmers.se/records/fulltext/183348/local_183348.pdf now seems to work

> quickCheckWith stdArgs { maxSuccess = 10000 } prop_shouldFail
*** Failed! Falsifiable (after 2 tests): 
((),Int14 13)
Int14 13

[idontgetoutmuch]

I just tried the same test but using https://hackage.haskell.org/package/tf-random

module Main where

import Control.Monad
import System.Random.TF.Gen
import System.Random.TF.Instances

splitN :: (RandomGen g) => Int -> g -> ([g], g)
splitN 0 g = ([], g)
splitN n g = (g1:l, g')
  where
  (l, g') = splitN (n-1) g2
  (g1, g2) = split g

-- The funny splitting operation.
split' :: (RandomGen g) => g -> (g, g)
split' g = (g12, g21)
  where
  (g1, g2) = split g
  (_, g12) = split g1
  (g21, _) = split g2

-- This test checks if generators created by calling split 2 times are independent.
-- It generates pairs of integers from 0 to n-1, using split' to
-- generate both numbers using one seed. Then it counts how often the
-- two numbers are equal.
test :: (RandomGen g) => Int -> Int -> g -> Int
test numTests n g = equals
  where
  (gs, _) = splitN numTests g
  equals = count id $ map single gs
  count p l = length $ filter p l
  single g' = (fst $ randomR (0, n-1) g1) == (fst $ randomR (0, n-1) g2)
    where
    (g1, g2) = split' g'

main = do
  let g = seedTFGen (42, 42, 42, 42)
  forM_ [2..15] $ \i -> do
    let actual = test (i * 1000) i g
    putStrLn $ "Generated " ++ show (i * 1000)
      ++ " pairs of numbers from 0 to " ++ show (i - 1)
      ++ " -- " ++ show actual ++ " pairs contained equal numbers "
      ++ "and we expected about 1000."

and this gives what seems to be a correct result

Generated 2000 pairs of numbers from 0 to 1 -- 1013 pairs contained equal numbers and we expected about 1000.
Generated 3000 pairs of numbers from 0 to 2 -- 977 pairs contained equal numbers and we expected about 1000.
Generated 4000 pairs of numbers from 0 to 3 -- 1016 pairs contained equal numbers and we expected about 1000.
Generated 5000 pairs of numbers from 0 to 4 -- 996 pairs contained equal numbers and we expected about 1000.
Generated 6000 pairs of numbers from 0 to 5 -- 988 pairs contained equal numbers and we expected about 1000.
Generated 7000 pairs of numbers from 0 to 6 -- 967 pairs contained equal numbers and we expected about 1000.
Generated 8000 pairs of numbers from 0 to 7 -- 976 pairs contained equal numbers and we expected about 1000.
Generated 9000 pairs of numbers from 0 to 8 -- 975 pairs contained equal numbers and we expected about 1000.
Generated 10000 pairs of numbers from 0 to 9 -- 992 pairs contained equal numbers and we expected about 1000.
Generated 11000 pairs of numbers from 0 to 10 -- 986 pairs contained equal numbers and we expected about 1000.
Generated 12000 pairs of numbers from 0 to 11 -- 991 pairs contained equal numbers and we expected about 1000.
Generated 13000 pairs of numbers from 0 to 12 -- 973 pairs contained equal numbers and we expected about 1000.
Generated 14000 pairs of numbers from 0 to 13 -- 990 pairs contained equal numbers and we expected about 1000.
Generated 15000 pairs of numbers from 0 to 14 -- 996 pairs contained equal numbers and we expected about 1000.

[idontgetoutmuch]

Here's the example from http://kenta.blogspot.co.nz/2014/02/rzzllapd-nonrandomness-of-first-random.html (slightly modified to use the histogram-fill package)

{-# OPTIONS_GHC -Wall                      #-}
{-# OPTIONS_GHC -fno-warn-name-shadowing   #-}
{-# OPTIONS_GHC -fno-warn-type-defaults    #-}
{-# OPTIONS_GHC -fno-warn-unused-do-bind   #-}
{-# OPTIONS_GHC -fno-warn-missing-methods  #-}
{-# OPTIONS_GHC -fno-warn-orphans          #-}

module Main where

import System.Random (StdGen, mkStdGen, randomR);

import qualified Data.Vector.Unboxed as V
import Data.Histogram ( asList )
import Data.Histogram.Fill
import Data.Histogram.Generic ( Histogram )

rollDice :: StdGen -> (Int, StdGen)
rollDice = randomR (1,6)

get_first :: Int -> Int
get_first seed = fst $ rollDice $ mkStdGen seed

hb :: HBuilder Int (Histogram V.Vector BinI Int)
hb = forceInt -<< mkSimple (binI 1 6)

hist :: Histogram V.Vector BinI Int
hist = fillBuilder hb (map get_first [0..53667])

main :: IO ()
main = mapM_ print $ asList hist

*Main> main
(1,0)
(2,0)
(3,0)
(4,0)
(5,0)
(6,53668)

Not really very random, Dilbert notwithstanding: http://dilbert.com/strip/2001-10-25.

[cartazio]

Sounds like weve got some work to do
On Mar 29, 2015 10:53 AM, "idontgetoutmuch" [email protected]
wrote:

Here's the example from
http://kenta.blogspot.co.nz/2014/02/rzzllapd-nonrandomness-of-first-random.html
(slightly modified to use the histogram-fill package)

{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_GHC -fno-warn-name-shadowing #-}
{-# OPTIONS_GHC -fno-warn-type-defaults #-}
{-# OPTIONS_GHC -fno-warn-unused-do-bind #-}
{-# OPTIONS_GHC -fno-warn-missing-methods #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

module Main where

import System.Random (StdGen, mkStdGen, randomR);

import qualified Data.Vector.Unboxed as V
import Data.Histogram ( asList )
import Data.Histogram.Fill
import Data.Histogram.Generic ( Histogram )

rollDice :: StdGen -> (Int, StdGen)
rollDice = randomR (1,6)

get_first :: Int -> Int
get_first seed = fst $ rollDice $ mkStdGen seed

hb :: HBuilder Int (Histogram V.Vector BinI Int)
hb = forceInt -<< mkSimple (binI 1 6)

hist :: Histogram V.Vector BinI Int
hist = fillBuilder hb (map get_first [0..53667])

main :: IO ()
main = mapM_ print $ asList hist

*Main> main
(1,0)
(2,0)
(3,0)
(4,0)
(5,0)
(6,53668)

Not really very random, Dilbert notwithstanding:
http://dilbert.com/strip/2001-10-25.

—
Reply to this email directly or view it on GitHub
#25 (comment).

[cartazio]

I kinda suspected the current splitting design had this sort of problem but
it's good we now have evidence!
On Mar 29, 2015 11:49 AM, "Carter Schonwald" [email protected]
wrote:

Sounds like weve got some work to do
On Mar 29, 2015 10:53 AM, "idontgetoutmuch" [email protected]
wrote:

Here's the example from
http://kenta.blogspot.co.nz/2014/02/rzzllapd-nonrandomness-of-first-random.html
(slightly modified to use the histogram-fill package)

{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_GHC -fno-warn-name-shadowing #-}
{-# OPTIONS_GHC -fno-warn-type-defaults #-}
{-# OPTIONS_GHC -fno-warn-unused-do-bind #-}
{-# OPTIONS_GHC -fno-warn-missing-methods #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

module Main where

import System.Random (StdGen, mkStdGen, randomR);

import qualified Data.Vector.Unboxed as V
import Data.Histogram ( asList )
import Data.Histogram.Fill
import Data.Histogram.Generic ( Histogram )

rollDice :: StdGen -> (Int, StdGen)
rollDice = randomR (1,6)

get_first :: Int -> Int
get_first seed = fst $ rollDice $ mkStdGen seed

hb :: HBuilder Int (Histogram V.Vector BinI Int)
hb = forceInt -<< mkSimple (binI 1 6)

hist :: Histogram V.Vector BinI Int
hist = fillBuilder hb (map get_first [0..53667])

main :: IO ()
main = mapM_ print $ asList hist

*Main> main
(1,0)
(2,0)
(3,0)
(4,0)
(5,0)
(6,53668)

Not really very random, Dilbert notwithstanding:
http://dilbert.com/strip/2001-10-25.

—
Reply to this email directly or view it on GitHub
#25 (comment).

[gbaz]

This splitting design has been known to have this problem for the past six years going by those tickets -- I think longer. And the guarantees made by the random library have never suggested otherwise. So I think a better random should have better splitting but I also think that this is not an immediate "must fix" bug, but a property that should inform our selection of a new random algorithm in the coming future.

[cartazio]

agreed, and i think its worth burning some time on

1. building some infrastructure to compare different algorithms in both
   quality of randomness AND in performance

2. exploring preexisting algorithms, and experimenting with new approaches
   informed by preexisting work AND buttressed by having a really good quality
   RNG testing infrastructure that we can be systematic about

On Sat, Apr 4, 2015 at 2:54 PM, gbaz [email protected] wrote:

This splitting design has been known to have this problem for the past six
years going by those tickets -- I think longer. And the guarantees made by
the random library have never suggested otherwise. So I think a better
random should have better splitting but I also think that this is not
an immediate "must fix" bug, but a property that should inform our
selection of a new random algorithm in the coming future.

—
Reply to this email directly or view it on GitHub
#25 (comment).

[idontgetoutmuch]

@gbaz by "guarantees made by the random library have never suggested otherwise" do you mean the haddock comment

but very little work has been done on statistically robust implementations of split ([System.Random,System.Random] are the only examples we know of)

or the comment in the actual implementation

-- no statistical foundation for this!

or is there something I am missing?

[gbaz]

The result of repeatedly using next should be at least as statistically robust as the Minimal Standard Random Number Generator described by [System.Random, System.Random]. Until more is known about implementations of split, all we require is that split deliver generators that are (a) not identical and (b) independently robust in the sense just given.

This makes clear to me that there was never a promise of statistical independence between split generators -- just that independently each generator is robust.

So this is well documented behaviour. (Which doesn' t mean it is good behaviour, and doesn't mean we shouldn't replace it with better behaviour now that we have new research and implementations).

[cartazio]

agreed. And some effort and time this summer should be spent exploring the
choices

On Thu, Apr 9, 2015 at 9:28 PM, gbaz [email protected] wrote:

The result of repeatedly using next should be at least as statistically
robust as the Minimal Standard Random Number Generator described by
[System.Random, System.Random]. Until more is known about implementations
of split, all we require is that split deliver generators that are (a) not
identical and (b) independently robust in the sense just given.

This makes clear to me that there was never a promise of statistical
independence between split generators -- just that independently each
generator is robust.

So this is well documented behaviour. (Which doesn' t mean it is good
behaviour, and doesn't mean we shouldn't replace it with better behaviour
now that we have new research and implementations).

—
Reply to this email directly or view it on GitHub
#25 (comment).

[idontgetoutmuch]

The second example I gave, rolling a die and getting 53668 sixes and no other numbers, does not use split just randomR.

[idontgetoutmuch]

Some old related discussion: https://mail.haskell.org/pipermail/haskell-cafe/2010-November/thread.html#85959

[gbaz]

The second example doesn't just use randomR -- it calls mkStdGen for each roll individually, which creates a new generator. As far as I know, mkStdGen in turn calls split.

Regardless, it is never considered the case that making new generators without introducing explicit randomness should somehow guarantee that the sequence of generators you make are mutually uncorrelated.

If you change the example to share the same generator, the problem does not exist. We could perhaps improve the documentation to more clearly warn against this bad usage pattern.

[dolio]

The second example doesn't just use randomR -- it calls mkStdGen for each roll individually, which creates a new generator. As far as I know, mkStdGen in turn calls split.

I don't think it even does that. It just creates a new generator from a specific seed. The complaint is that seeding with N doesn't differ from seeding with (N+1) when generating a single number from 1 to 6.

[idontgetoutmuch]

I believe some comparison work has been done. I am recording these links below for information.

https://github.com/nkartashov/SplitMix
https://github.com/nkartashov/prng-test
https://github.com/nkartashov/prng-bench
https://github.com/nkartashov/htestu

[cartazio]

Yup. We should both work through running validation benchmarks from those
repos / audit the statistical and performance benchmarks that the student
worked on.
On Sep 17, 2015 4:01 AM, "idontgetoutmuch" [email protected] wrote:

I believe some comparison work has been done. I am recording these links
below for information.

https://github.com/nkartashov/SplitMix
https://github.com/nkartashov/prng-test
https://github.com/nkartashov/prng-bench
https://github.com/nkartashov/htestu

—
Reply to this email directly or view it on GitHub
#25 (comment).

[Blaisorblade]

After seeing split docs, I wanted to mention a library designed for parallel Monte Carlo: http://www.sprng.org/. This page describes the algorithms used and the docs also describe the performed testing; the library was also published on ACM ToMS with 275 citations. It also doesn't use cryptographic-strength PRNGs, unlike the ones mentioned in the 2010 haskell-cafe thread (https://mail.haskell.org/pipermail/haskell-cafe/2010-November/thread.html#85959),
and the docs mention TestU01 (the standard benchmark mentioned also in https://github.com/nkartashov/htestu).

I haven't validated the library myself, but it was recommended by my professor in Monte Carlo methods and random number generation, and he wanted to use it for his own publications. Since physicists know their stats, it looks promising.

The actual algs aren't so much math (though the validation work isn't going to be trivial). Anyone want to take a stab at this?

[cartazio]

thanks for sharing this, I"ll take a look soon! (i've some summer projects
with september deadlines hot on my tail, but i'm keen to give random some
much needed love this fall)

On Wed, Aug 31, 2016 at 4:44 PM, Paolo G. Giarrusso <
[email protected]> wrote:

After seeing split docs, I wanted to mention a library designed for
parallel Monte Carlo: http://www.sprng.org/. This page
http://www.sprng.org/Version5.0/generators.html describes the
algorithms used and the docs also describe the performed testing; the
library was also published on ACM ToMS with 275 citations. It also
doesn't use cryptographic-strength PRNGs, unlike the ones mentioned in
the 2010 haskell-cafe thread (https://mail.haskell.org/
pipermail/haskell-cafe/2010-November/thread.html#85959),
and the docs mention TestU01 (the standard benchmark mentioned also in
https://github.com/nkartashov/htestu).

I haven't validated the library myself, but it was recommended by my
professor in Monte Carlo methods and random number generation, and he
wanted to use it for his own publications. Since physicists know their
stats, it looks promising.

The actual algs aren't so much math (though the validation work isn't
going to be trivial). Anyone want to take a stab at this?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#25 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAAQwvFuQ2EeOJC_3ENfrjuvD9OpDySBks5qleeqgaJpZM4D2pzO
.

[tom-bop]

Any news on this front?

[cartazio]

yup, https://github.com/cartazio/random/tree/v1.2.0 (plus some commits i've locally that i really should push) is progressing to a release

@tom-bop whats your needs/ context?

[cartazio]

(i do need to figure out what the major versioning / migrration path will be, 1.2 is gonna try to be mostly drop in compatible, with minimal fix ups, some later versions will have more machinery / better apis
)

[idontgetoutmuch]

@tom-bop my recommendation is not to use this library. If you really want independent generators then use either https://hackage.haskell.org/package/tf-random or https://hackage.haskell.org/package/splitmix.

[cartazio]

@idontgetoutmuch : http://www.pcg-random.org/posts/bugs-in-splitmix.html :)

[idontgetoutmuch]

@cartazio excellent - that will teach me to trust people who told me it was the greatest thing since sliced bread - I will have to read the article in more depth

[cartazio]

Yeah ... there’s some differences between the jdk version and reference etc. Tf random also had some issues when I ran those test harnesses. Though I think you rightfully pointed out there’s some issues on interpretation. So I’m trying to make sure we have a range of tools. And easy ways to build sampling strategies of various flavors based on desired quality and perf targets.

…

On Fri, Feb 16, 2018 at 10:12 AM idontgetoutmuch ***@***.***> wrote: @cartazio <https://github.com/cartazio> excellent - that will teach me to trust people who told me it was the greatest thing since sliced bread - I will have to read the article in more depth — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#25 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAAQwmL2w2mka0oD2-LtZSmECXcqVAxvks5tVZrigaJpZM4D2pzO> .

[idontgetoutmuch]

https://alexey.kuleshevi.ch/blog/2019/12/21/random-benchmarks/

[cartazio]

Yup! Agreed. Been getting vector into a good place the past few weeks (hope you like the new release!). This whole backlog is next.

…

On Tue, Feb 4, 2020 at 8:44 AM idontgetoutmuch ***@***.***> wrote: https://alexey.kuleshevi.ch/blog/2019/12/21/random-benchmarks/ — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#25?email_source=notifications&email_token=AAABBQSNYBTR6C4QA7GLAMDRBFWKVA5CNFSM4A62TTHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKXVHGY#issuecomment-581915547>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABBQQWYCNQNCITGKTXGVDRBFWKVANCNFSM4A62TTHA> .

[peteroupc]

For your information:

I have written notes on how to test PRNGs and hash functions for appropriate randomness in "Testing PRNGs for High-Quality Randomness". As relevant here, there are many kinds of hash functions that could serve as the basis for a good-quality splittable RNG construction (not just Threefry), and there are at least four kinds of sequences that are suitable for testing splittable RNGs.