Is ScalaCheck's Gen.pick really random?

Question

I observed the following unexpected behaviour when using ScalaCheck's Gen.pic, which (for me) indicates that its picking is not quite random, even though its documentation says so: ``` /** A generator that picks a given number of elements from a list, randomly */ ``` I ran the below three little programs in order (in a span of 2 days, at different times, as it might matter) after setting ``` implicit override val generatorDrivenConfig = PropertyCheckConfig( maxSize = 1000, minSize = 1000, minSuccessful = 1000) ``` to get a decent sample size. Program #1 ``` val set = Set(1,2,3,4,5,6,7,8,9,10, 11,12,13,14,15,16,17,18,19,20, 21,22,23,24,25,26,27,28,29,30, 31,32,33,34,35,36,37,38,39,40, 41,42,43,44,45,46,47,48,49,50) // Thanks to @Jubobs for the solution // See: http://stackoverflow.com/a/43825913/4169924 val g = Gen.pick(3, set).map { _.toList } forAll (g) { s => println(s) } ``` Out of the 3000 numbers generated at 2 different runs I got a surprisingly similar, and quite non-random dis…

Accepted Answer

Although @ashawley answer is already accepted I don't think it is correct. I think that this is actually a bug and it was introduced by erik-stripe's commit on Sep 1, 2016 and the bug is actually in the line

```
      val i = (x & 0x7fffffff).toInt % n
```

and it was supposed to be

```
      val i = (x & 0x7fffffff).toInt % count
```

which is still not quite correct.

I also expect that your 33% for the last value is actually 100% and you didn't take into account the fact that you select 3 elements so all your statistics should be multiplied by 3. So for 3-element selection the last element is selected 100% of the time, the previous one - 66.6% and so on, which is even worse than you expected.

Here is again an excerpt from the code:

```
else gen { (p, seed0) =>
  val buf = ArrayBuffer.empty[T]
  val it = l.iterator
  var seed = seed0
  var count = 0
  while (it.hasNext) {
    val t = it.next
    count += 1
    if (count <= n) {
      buf += t
    } else {
      val (x, s) = seed.long
      val i = (x & 0x7fffffff).toInt % n
      if (i < n) buf(i) = t
      seed = s
    }
  }
  r(Some(buf), seed)
}
```

So what this code is supposed to do and what it actually does? The `if (count <= n)` branch fills the output `buf` with first `n` elements and after that always the `else` branch works. To make it more clear I changed the `while` moving `if` outside to the following code:

```
  for (i <- 0 until  n) {
    val t = it.next
    buf += t
  }
  while (it.hasNext) {
    val t = it.next
    val (x, s) = seed.long
    val i = (x & 0x7fffffff).toInt % n
    if (i < n) buf(i) = t
    seed = s
  }
```

So now it becomes obvious that the `else` branch should at the same time decide if the current element should be added to the output `buf` AND which element there it should replace. Obviously, current code always selects each element because `if (i < n)` is always true given that `i` is calculated as `something % n`. And this is why you see such a huge skew to the last elements.

Obviously the plan was to use a modified version of Fisher–Yates shuffle that selects only first `n` elements of the shuffle and to do it properly you need to select random numbers in the range [0, `count`) and this is probably why the code is written the way it is written i.e. preserving `counter` inside `while` loop.

Using `% count` is still not quite correct because such a simple way doesn't produce uniform distribution when `count` is not a power of 2. To be more fair something like

```
    val c0 = choose(0, count-1)
    val rt: R[Int] = c0.doApply(p, seed)        
    seed = rt.seed      
    val i = rt.retrieve.get // index to swap current element with. Should be fair random number in range [0, count-1], see Fisher–Yates shuffle
    if (i < n) buf(i) = t
```

or some other way to create `i` as a fair uniformly distributed random number in such a range should be used.

Update (Why just `% count` is wrong)

You can look at java.util.Random.nextInt(int) implementation or org.scalacheck.Choose.chLng for an example of how it should be done. It is more complicated than just `% count` and there is a good reason for it. To illustrate it consider following example. Let's assume that your source random generator generates uniformly random 3-bit values i.e in range just [0, 7] and you want to get ranadom number in range `[0, 2]` and you do it by simply doing

```
srcGenerator.nextInt() % 3
```

Now consider mapping of values in range `[0, 7]` to your range `[0, 2]`:

- `0, 3, 6` will be mapped to `0` (i.e. 3 values are mapped)

- `1, 4, 7` will be mapped to `1` (i.e. 3 values are mapped)

- `2, 5` will be mapped to `2` (i.e. only 2 values are mapped)

So if you do just `% 3` your distribution will be 0 - 3/8, 1 - 3/8, 2 - 2/8 which is obviously not uniform. This is why those implementations I referenced earlier use some kind of a loop and discard some values generated by the source generator. It is required to produce unifrom distribution.

Is ScalaCheck's Gen.pick really random?

Solution

Problem

Related problems