even distribution with naive shuffle?

Question

I'm shuffling an array of 3 int, 6 millions times. I keep count of each permutation of the array in a map. Code is below using go.

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func randRange(min, max int) int {
    return rand.Intn(max-min+1) + min
}

func NaiveShuffle(arr *[3]int) {
    for i := 0; i < 3; i++ {
        e := randRange(0, 2)
        arr[e], arr[i] = arr[i], arr[e]
    }
}

func main() {
    rand.Seed(time.Now().UnixNano())
    m := make(map[[3]int]int, 6)
    arr := [3]int{-6,10,184}

    for i := 1; i <= 6000000; i++ {
        a := arr
        NaiveShuffle(&arr)
        m[a]++
    }

    for k, v := range m {
        fmt.Println(k, ":", v)
    }

}

Since I'm doing naive shuffle my understanding is it should not produce an even distribution of permutations. But this is what I get:

[184 -6 10] : 1000074
[184 10 -6] : 1000764
[-6 10 184] : 1000766
[10 184 -6] : 998090
[-6 184 10] : 1000479
[10 -6 184] : 999827

This shows each of the 6 possible permutations occurs about ~1M times. Why do I get what appears to be an even distribution ?

EDIT: changed code to only seed once. I now get:

[-6 184 10] : 999507
[184 -6 10] : 1000401
[10 -6 184] : 1002163
[10 184 -6] : 999236
[-6 10 184] : 999016
[184 10 -6] : 999677

EDIT2: Thanks to hobbs, I realized I made a silly mistake. I should shuffle a, not arr. I now get:

[10 -6 184] : 1111056
[-6 10 184] : 888442
[184 -6 10] : 888576
[10 184 -6] : 1109896
[-6 184 10] : 1113148
[184 10 -6] : 888882

Sure. Edited the code and posted new results. Still looks even to me. — user219820, Feb 13 '23 at 01:37
[as per docs](https://pkg.go.dev/math/rand#Source) Intn is likely to generated uniformly distributed random numbers. you may want to [try this](https://stackoverflow.com/questions/977354/generating-non-uniform-random-numbers) — Sushil, Feb 13 '23 at 07:16
I'm actually trying to generate non-uniform distribution. By the way, a simpler way to generate uniform distribution is use fisher yates shuffle. — user219820, Feb 13 '23 at 19:48
[this thread](https://stackoverflow.com/questions/977354/generating-non-uniform-random-numbers) about non-uniform distribution may help — Sushil, Feb 14 '23 at 03:15

score 1 · Accepted Answer · answered Feb 13 '23 at 01:45

1

You're shuffling arr over and over six million times without restoring it to its original state in between shuffles — in other words, your six million trials aren't independent. Even though each shuffle has an uneven distribution of permutations, composing those permutations on top of each other six million times results in a distribution that's quite close to uniform.

answered Feb 13 '23 at 01:45

hobbs

223,387
19
210
288

Right on. What a dumb mistake I made. – user219820 Feb 13 '23 at 01:52

score 0 · Answer 2 · answered Feb 13 '23 at 02:11

Even you restoring it to its original state. its not a random event:

let us list all cases:

    m := map[string]int{}
    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            for k := 0; k < 3; k++ {
                a := []string{"a", "b", "c"}
                a[i], a[0] = a[0], a[i]
                a[j], a[1] = a[1], a[j]
                a[k], a[2] = a[2], a[k]
                m[a[0]+a[1]+a[2]]++
                fmt.Printf("%v\n", a)
            }
        }
    }
    fmt.Printf("%v\n", m)

result:

map[abc:4 acb:5 bac:5 bca:5 cab:4 cba:4]

it have all 3*3*3 = 27 cases but only have C(3,1) = 6 result it must be not equal(4:5)..

This explains why it should be biased distribution but doesn't answer the question. My test is wrong and I have edited my post to explain what I did wrong. — user219820, Feb 13 '23 at 02:24

even distribution with naive shuffle?

2 Answers2