Skip to content

The seeds generated by split are not independent #25

Closed
#62
#61
Closed
The seeds generated by split are not independent#25
#62
#61
Milestone
1.2.0

Description

@idontgetoutmuch
idontgetoutmuch
opened on Mar 29, 2015

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

Activity

  1. idontgetoutmuch commented on Mar 29, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Mar 29, 2015
    MemberAuthor

    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.

  2. idontgetoutmuch commented on Mar 29, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Mar 29, 2015
    MemberAuthor

    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.

  3. cartazio commented on Mar 29, 2015

    @cartazio
    cartazio
    on Mar 29, 2015
    Contributor

    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).

  4. cartazio commented on Mar 29, 2015

    @cartazio
    cartazio
    on Mar 29, 2015
    Contributor

    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).

  5. idontgetoutmuch
    added a commit that references this issue on Apr 4, 2015

    Add some tests demonstrating #25.

    5af0c12

  6. gbaz commented on Apr 4, 2015

    @gbaz
    gbaz
    on Apr 4, 2015

    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.

  7. cartazio commented on Apr 4, 2015

    @cartazio
    cartazio
    on Apr 4, 2015
    Contributor

    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).

  8. idontgetoutmuch commented on Apr 9, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Apr 9, 2015
    MemberAuthor

    @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?

  9. gbaz commented on Apr 10, 2015

    @gbaz
    gbaz
    on Apr 10, 2015

    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).

  10. cartazio commented on Apr 10, 2015

    @cartazio
    cartazio
    on Apr 10, 2015
    Contributor

    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).

  11. idontgetoutmuch commented on Apr 16, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Apr 16, 2015
    MemberAuthor

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

  12. idontgetoutmuch commented on Apr 16, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Apr 16, 2015
    MemberAuthor

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

  13. gbaz commented on Apr 16, 2015

    @gbaz
    gbaz
    on Apr 16, 2015

    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.

  14. dolio commented on Apr 16, 2015

    @dolio
    dolio
    on Apr 16, 2015

    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.

  15. idontgetoutmuch commented on Sep 17, 2015

    @idontgetoutmuch
    idontgetoutmuch
    on Sep 17, 2015
    MemberAuthor

    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

  16. 17 remaining items

  17. cartazio
    added a commit that references this issue on May 19, 2020

    Merge pull request #25 from idontgetoutmuch/export-uniform

    5ee879b
  18. curiousleo
    added 3 commits that reference this issue on May 26, 2020

    parent cfdfe6f

    2879ad4

    parent cfdfe6f

    a01df83

    Fix quality and performance issues, add monadic API

    b48b6c0
  19. lehins
    added 3 commits that reference this issue on May 27, 2020

    Fix quality and performance issues, add monadic API

    cf2c518

    Fix quality and performance issues, add monadic API

    80ef577

    Fix quality and performance issues, add monadic API

    5773379
  20. curiousleo
    added 6 commits that reference this issue on Jun 15, 2020

    Fix quality and performance issues, add monadic API

    d3b4bb4

    Fix quality and performance issues, add monadic API

    0337556

    Fix quality and performance issues, add monadic API

    64fa9bb

    Fix quality and performance issues, add monadic API

    51e1a74

    Fix quality and performance issues, add monadic API

    8d51546

    Fix quality and performance issues, add monadic API

    b45bd28
  21. idontgetoutmuch
    closed this as completedin #62on Jun 23, 2020
  22. lehins
    added this to the 1.2.0 milestone on Jan 23, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions