I analyzed shuffling in a million games of MtG Arena

Re:I analyzed shuffling in a million games of MtG Arena by senkora on Sunday January 15, 2023 @07:40AM (#34388965)

This feels like it should work from a clear induction argument.

Base case: n=1. Obvious.

Inductive step: n>1. The nth element swaps to itself w/ prob 1/n, and to any other element w/ prob 1/n. By induction the other elements have been uniformly shuffled. Any of those elements is swapped to the nth place w/ prob 1/n.

[ Parent | on HN ]

Re:I analyzed shuffling in a million games of MtG Arena by afiori on Sunday January 15, 2023 @07:48AM (#34389000)

I don't think you can apply this proof to the described algorithm.

This proves that

    for i in range(min_key,max_key):
        swap(arr, i, choice(i, max_key))

works as a shuffle, by growing a random sub-array.*

The first algorithm was

    for i in range(min_key,max_key):
        swap(arr, i, choice(min_key, max_key))

which has different biases.

* I am not actually sure that this actually works.

[ Parent | on HN ]

Re:I analyzed shuffling in a million games of MtG Arena by senkora on Sunday January 15, 2023 @07:56AM (#34389047)

Ah, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.

[ Parent | on HN ]

Re:I analyzed shuffling in a million games of MtG Arena by mananaysiempre on Sunday January 15, 2023 @07:59AM (#34389065)

Your first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)

[ Parent | on HN ]

Re:I analyzed shuffling in a million games of MtG Arena by LudwigNagasena on Sunday January 15, 2023 @08:12AM (#34389146)

If your n-1 elements are uniformly shuffled, swapping with them would undo that. So to preserve the uniformity invariant, you have not to touch elements that were already shuffled, which leads you to Fisher–Yates.

[ Parent | on HN ]