Why does the generator returned by `fst (Random.split gen)` sometimes produce the same results as `gen`?

user_9540958 0
Viewed 88

I'm trying to create random permutations of a list. I'm new to randomness in functional languages and don't have a full grasp on monads yet, but I have used Random.newStdGen and Random.Shuffle.shuffle' in a way that I believe should be working.

The problem I'm running into, is I'm getting a lot of duplicate permutations to the point where it seems that I'm incorrectly using or incorrectly understanding the split function for generators.

The relevant functions are here:

doGenerateInput :: [[Int]] -> System.Random.StdGen -> Int -> Int -> [[Int]]
doGenerateInput acc gen n 0 = acc
doGenerateInput acc gen n k =
  doGenerateInput
    (System.Random.Shuffle.shuffle' [1 .. n] n gen : acc) accumulator
    (fst (System.Random.split gen))
    n
    (k -1)

generateInput :: Int -> Int -> IO [[Int]]
generateInput n k = do
  gen <- System.Random.newStdGen
  return (doGenerateInput [] gen n k)

Here generateInput should create k random permutation of [1..n]. It splits the generator before passing it to the next level of recursion, so each of the permutations should be statistically unrelated to each other. However the actual results I'm getting include a ton of duplicates. Usually returning the same permutation twice in a row. Sometimes even three times in a row. Does anyone have any suggestions on what I might be doing wrong?

Here is an output I received from it.

8 18 1 6 17 19 7 9 15 2 11 12 20 16 10 5 4 14 13 3
12 11 8 20 1 6 19 7 9 17 2 13 14 18 10 5 4 16 15 3
3 13 12 9 1 2 8 10 11 19 4 15 16 20 14 7 6 18 17 5
3 13 12 9 1 2 8 10 11 19 4 15 16 20 14 7 6 18 17 5
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
7 8 3 15 14 16 20 11 1 2 10 12 13 5 4 19 6 18 17 9
8 6 9 10 7 11 3 19 18 20 15 1 2 14 17 16 4 12 5 13
18 8 6 9 10 7 11 3 20 19 15 1 2 14 17 16 4 12 5 13
8 11 5 13 15 4 20 18 16 14 10 3 12 1 19 7 9 6 2 17
16 8 11 5 13 6 15 18 4 19 17 12 3 14 1 9 10 7 2 20
2 17 9 12 6 14 7 16 19 5 20 18 13 4 15 1 8 11 3 10
7 2 18 10 6 14 8 16 9 19 5 20 15 4 17 1 11 13 3 12
17 7 2 19 13 10 6 15 8 18 9 5 14 11 16 3 1 20 4 12
11 4 19 8 2 6 16 13 9 18 10 12 20 3 7 15 5 1 17 14
17 11 4 20 13 10 8 2 6 19 15 9 3 14 5 18 16 7 1 12
17 11 4 20 13 10 8 2 6 19 15 9 3 14 5 18 16 7 1 12
12 18 11 4 1 15 13 9 3 7 17 10 5 16 6 20 19 8 2 14
12 18 11 4 1 15 13 9 3 7 17 10 5 16 6 20 19 8 2 14

Based on the documentation for split, I would expect that the two generators returned from split are not correlated. But the rate of duplicates seems to indicate that generating a random number with fst (split gen) produces the same result as gen about half the time.

Returns two distinct pseudo-random number generators. Implementations should take care to ensure that the resulting generators are not correlated.

https://hackage.haskell.org/package/random-1.2.1/docs/System-Random.html#v:split

I have found a solution, but I don't understand why it works

If I use snd (split gen) instead of fst (split gen), I do not get any repeats. However based on the documentation, I'm unsure of why. It doesn't make any notes of a difference between the first and second generators returned.

Any insight would be appreciated.

haskell
2 Answers

There's something of an assumption in the design of random that a RandomGen value is only used once. When you reuse them, weird things can happen. I don't know how RandomGen's split is implemented to give you this outcome, but I can tell you it's assuming you're not going to do what you're doing. Passing gen to both split and shuffle' is using it twice. The intended way to use split for your use case would be to call split up front, and then pass one of its return values to shuffle' and the other to the recursive call.

user_3832000

You do not need to use split, which is only required typically in arborescent structures.

You could generate the permutations like this:

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 ...
 λ> 
 λ> import System.Random
 λ> import Control.Monad
 λ> import Control.Monad.Random
 λ> import System.Random.Shuffle
 λ> 
 λ> :type replicateM
 replicateM :: Applicative m => Int -> m a -> m [a]
 λ> 
 λ> :type shuffleM
 shuffleM :: MonadRandom m => [a] -> m [a]
 λ> 
 λ> action n k = replicateM k (shuffleM [1..n])
 λ> 
 λ> :type  action 10 6
 action 10 6 :: (MonadRandom m, Num a, Enum a) => m [[a]]
 λ> 
 λ> randomSeed = 42
 λ> gen0 = mkStdGen randomSeed
 λ> 
 λ> (xss,gen1) = runRand (action 10 6) gen0
 λ> 
 λ> printAsLines zs = mapM_  (putStrLn . show)  zs
 λ> 
 λ> printAsLines xss
 [10,7,4,6,3,9,1,8,2,5]
 [4,1,3,2,7,8,10,9,6,5]
 [2,8,6,9,1,5,7,4,3,10]
 [7,10,5,2,9,1,6,4,8,3]
 [3,7,4,10,8,1,2,5,6,9]
 [9,1,2,4,3,8,7,6,5,10]
 λ>
user_112824040
Related