Opened 9 years ago
Closed 3 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)
Change History (7)
Changed 9 years ago by
Attachment: | RandomnessTest2.hs added |
---|
comment:1 Changed 9 years ago by
difficulty: | → Unknown |
---|
comment:2 Changed 9 years ago by
Milestone: | → _|_ |
---|
comment:3 Changed 7 years ago by
Owner: | set to rrnewton |
---|---|
Type of failure: | → None/Unknown |
comment:4 Changed 5 years ago by
Are there any plans to adopt the work out of Chalmers from the tf-random package on Hackage into System.Random?
comment:5 Changed 4 years ago by
Component: | libraries/random → Core Libraries |
---|---|
Owner: | changed from rrnewton to ekmett |
Moving over to new owning component 'Core Libraries'.
comment:6 Changed 3 years ago by
Resolution: | → duplicate |
---|---|
Status: | new → closed |
This is now being tracked in the random
bug tracker on Github: The seeds generated by split are not independent.
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