Opened 8 years ago

Closed 2 years ago

#3620 closed bug (duplicate)

The seeds generated by split are not independent

Reported by: NickSmallbone Owned by: ekmett
Priority: normal Milestone:
Component: Core Libraries Version: 6.11
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Suppose we split a seed into two like this:

split' :: StdGen -> (StdGen, StdGen)
split' g = (g12, g21)
  where (_, g12) = split g1
        (g21, _) = split g2
        (g1, g2) = split g

Since g1 and g2 are independent, g12 and g21 ought to be too. But they're not! If we use both of g12 and g21 to generate a random number in the range [0..10], then the two numbers ought to be equal 1/11 of the time. In fact, they're never equal. Here is a test program that ought to return True 1/11 of the time but actually always returns False:

sample :: StdGen -> (Int, Int)
sample g = (fst (randomR (0, 10) g1),
            fst (randomR (0, 10) g2))
   where (g1, g2) = split' g
test :: StdGen -> Bool
test g = fst (sample g) == snd (sample g)

I attached a program that prints the distribution of values from test for other ranges than [0..10]. The distribution is always quite bad no matter what the range is.

The upshot of all this is that the following QuickCheck (version 2) property always passes, even though it's false:

import Test.QuickCheck
import Text.Show.Functions

newtype Eleven = Eleven Int deriving Eq

instance Arbitrary Eleven where
  arbitrary = fmap Eleven (choose (0, 10))

prop :: (Int -> Eleven) -> Bool
prop f = f 5 /= f 6

Attachments (1)

RandomnessTest2.hs (1.2 KB) - added by NickSmallbone 8 years ago.

Download all attachments as: .zip

Change History (7)

Changed 8 years ago by NickSmallbone

Attachment: RandomnessTest2.hs added

comment:1 Changed 8 years ago by simonpj

difficulty: Unknown

Indeed that looks bad.

This is a Random library problem, like #3575. Can anyone help fix it, please? It would make sense to tackle #3575 at the same time.

Simon

comment:2 Changed 8 years ago by igloo

Milestone: _|_

comment:3 Changed 6 years ago by rrnewton

Owner: set to rrnewton
Type of failure: None/Unknown

comment:4 Changed 4 years ago by nfrisby

Are there any plans to adopt the work out of Chalmers from the tf-random package on Hackage into System.Random?

comment:5 Changed 3 years ago by thoughtpolice

Component: libraries/randomCore Libraries
Owner: changed from rrnewton to ekmett

Moving over to new owning component 'Core Libraries'.

comment:6 Changed 2 years ago by thomie

Resolution: duplicate
Status: newclosed

This is now being tracked in the random bug tracker on Github: The seeds generated by split are not independent.

Note: See TracTickets for help on using tickets.