What is an unbiased Shuffle algorithm?
Consider an array with distinct elements A[1 … n]
A perfectly unbiased shuffle algorithm would randomly shuffle all elements in the array such that after shuffling:
1.The probability that the shuffling operation would produce any particular permutation of the original array is the same for all permutations (i.e.) since there are n! permutations, the probability that the shuffle operation would produce any particular permutation is 1/n!
2.For any element e in the array and for any position j (1<= j <= n), the probability that the element would end up in position A[j] is 1/n
Consider two shuffling algorithms
SHUFFLE 1
shuffle(A[1 … n]) {
for i = 1 to n {
// Find a random integer between 1 and n inclusive
int rand= RANDOM(1,n);
swap A[i] with A[rand];
}
}SHUFFLE 2
shuffle(A[1 … n]) {
for i = 1 to n {
// Find a random integer between i and n inclusive
int rand= RANDOM(i,n);
swap A[i] with A[rand];
}
}How do these two shuffling algorithms compare against each other? Let’s simulate and find out.
Simulation of Shuffle 1
A simulation of Shuffle 2 with an array of is given below.
Count of permutations:
{1,2,3} – count 4
{1,3,2} – count 5
{2,1,3} – count 5
{2,3,1} – count 5
{3,1,2} – count 4
{3,2,1} – count 4
Conclusion: Shuffle 1 is biased
Simulation of Shuffle 2
A simulation of Shuffle 2 with an array {1,2,3} is given below.
Count of permutations:
{1,2,3} – count 1
{1,3,2} – count 1
{2,1,3} – count 1
{2,3,1} – count 1
{3,1,2} – count 1
{3,2,1} – count 1
Conclusion: Shuffle 2 is an unbiased perfect shuffling algorithm
Can we prove that Shuffle 2 will produce an unbiased shuffle in all cases?
For any element e, the probability that it will be shuffled into the first position
= probability that it is selected for swapping when i = 1
= 1/n
For any element e, the probability that it will be shuffled into the second position
= probability that it is NOT selected for the first position x probability that it is selected for swapping when i = 2
= (n-1)/n x 1/(n-1)
= 1/n
…
For any element e, the probability that it will be shuffled into any particular position = 1/n
This content was brought to you by Evalground Online Testing Platform. Evalground is an online assessment and test evaluation system focused on helping Recruiters in initial screening of potential candidates from an ocean of job seekers in an automated way.
Evalground supports Online Aptitude Tests, Spoken English Communication Skills Assessments, Coding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP. Evalground also supports Automated asynchronous interviews. Evalground Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.