Fisher yates algorithm is not yielding unbiased results

Question

Fisher yates algorithm as described on wikipedia is

The algorithm produces an unbiased permutation: every permutation is equally likely.

I went through some articles that explains how a naive and fisher yates algorithm can produce biased and unbiased combination of items in a set.

Link to the articles

Fisher-Yates Shuffle – An Algorithm Every Developer Should Know

Randomness is hard: learning about the Fisher-Yates shuffle algorithm & random number generation

The articles goes on to show graphs of almost unbiased and very biased results with both these two algorithms. I tried to reproduce the probabilities but i can't seem to produce the difference.

Here is my code

import java.util.*

class Problem {
    private val arr = intArrayOf(1, 2, 3)
    private val occurrences = mutableMapOf<String, Int>()
    private val rand = Random()

    fun biased() {
        for (i in 1..100000) {
            for (i in arr.indices) {
                val k = rand.nextInt(arr.size)
                val temp = arr[k]
                arr[k] = arr[i]
                arr[i] = temp
            }


            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Naive:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }

    /**
    * Fisher yates algorithm - unbiased
    */
    fun unbiased() {
        for (i in 1..100000) {
            for (i in arr.size-1 downTo 0) {
                val j = rand.nextInt(i + 1)
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }

            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Fisher Yates:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }
}

fun main() {
    Problem().biased()
    Problem().unbiased()
}

This produces the following result

Naive:
312: 16719
213: 16654
231: 16807
123: 16474
132: 16636
321: 16710
Fisher Yates:
123: 16695
312: 16568
213: 16923
321: 16627
132: 16766
231: 16421

My results are not very different in both cases. My question is, is my implementation wrong? Or my understanding is wrong?

score 3 · Answer 1 · answered May 15 '21 at 11:28

Your implementation of both algorithms has a mistake that smooths out the bias introduced by the naive shuffling. You don't start over with the same permutation for each shuffle, but with the one produced by the last shuffle. A simple fix is to reset the array to be [1, 2, 3] each time:

import java.util.*

class Problem {
    private var arr = intArrayOf(1, 2, 3)
    private val occurrences = mutableMapOf<String, Int>()
    private val rand = Random()

    fun biased() {
        for (i in 1..100000) {
            arr = intArrayOf(1, 2, 3)  // reset arr before each shuffle
            for (i in arr.indices) {
                val k = rand.nextInt(arr.size)
                val temp = arr[k]
                arr[k] = arr[i]
                arr[i] = temp
            }


            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Naive:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }

    /**
    * Fisher yates algorithm - unbiased
    */
    fun unbiased() {
        for (i in 1..100000) {
            arr = intArrayOf(1, 2, 3)  // reset arr before each shuffle
            for (i in arr.size-1 downTo 0) {
                val j = rand.nextInt(i + 1)
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }

            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Fisher Yates:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }
}

fun main() {
    Problem().biased()
    Problem().unbiased()
}

Output:

Naive:
213: 18516
132: 18736
312: 14772
321: 14587
123: 14807
231: 18582
Fisher Yates:
321: 16593
213: 16552
231: 16674
132: 16486
123: 16802
312: 16893

Not a Kotlin-programmer, so there's probably a more elegant way to do this, but it's good enough, I guess.

Thanks! Yeah that did it. Although i am still wondering why did the order of array made the difference? Suppose in real life, a set of items wont be sorted each time we shuffle. — f_i, May 15 '21 at 11:47
@f_i If you always start with the elements ordered as `[1, 2, 3]`, the output represents the way the elements were shuffled. If you start with a preshuffled array you'll have to "subtract" the preshuffling to get the actual permutation. So the output isn't a representation of the performed permutation anymore. So basically the difference isn't that the bias isn't present anymore, but that it isn't visible in the output. — , May 15 '21 at 13:36

Fisher yates algorithm is not yielding unbiased results

1 Answers1