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" notifications@github.com
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" carter.schonwald@gmail.com
wrote:

Sounds like weve got some work to do
On Mar 29, 2015 10:53 AM, "idontgetoutmuch" notifications@github.com
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 notifications@github.com 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 notifications@github.com 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