Biased random shuffle due to random number generators


  • 0
    W

    Random shuffle may be biased, even though built-in library is used or it is implemented correctly by one's own based on Fisher-Yates method. In fact, bias comes from the random number generators which have its own limitation.

    I am a python guy, so here I made an excerpt from Python 2.7 doc: random.shuffle(x[, random]) Shuffle the sequence x in place. The optional argument random is a 0-argument function returning a random float in [0.0, 1.0); by default, this is the function random(). Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

    Disclaimer: no disrespect to Python people, nor any other language/package designers, as we totally understand the issue here.


  • 0

    Um... no. You completely missed the point. Even though you even highlighted it. Please try again.

    It's btw obscene that you think the Python people not only made a stupid mistake but then instead of fixing it, made the documentation say that there's a stupid mistake. You can't be serious.

    (Update: That was about the original text, which isn't there anymore.)


  • 0
    W

    @StefanPochmann Come on, man. I did not mean that Python people made a stupid mistake. Actually, I do not even think it is a mistake. It causes bias just due to the mechanism of random.shuffle. People can use random.sample though (with all elements being sampled without duplicates).

    BTW, your word "obscene" is really obscene.

    (Update: same reason as above.)


  • 0

    Here's a hint: Python's random.shuffle uses the Fisher-Yates shuffle.

    And random.sample has the exact same issue.


  • 0
    W

    @StefanPochmann Thanks man. I finally got your point after some googling. Let me revise my post then.


  • 0

    It's better now :-). Though we've already seen that maybe not everybody will understand it, so I think it would be good to add an example. Like, pick some random number generator of some language and show what array size is enough to guarantee that not all permutations are possible with that generator.


  • 0
    W

    You are damn right man. Feel free to add the example if you'd like to.


  • 0

    @WKVictor Would be better if you added one yourself. It's your topic, you can edit the first post, and you'd probably learn more from it than I would. Plus it could convince me that you indeed totally understand the issue now :-P


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.