Random Permutations Consider the following approach for shuffling a deck of n cards: Apply the following procedure for i
Posted: Fri Jul 01, 2022 5:43 am
Random Permutations
Consider the following approach for shuffling a deck of ncards:
Apply the following procedure for i = 1, . . . , n:
• Choose a random card in the deck.
• Swap the i-th card in the deck with the randomly-selectedcard.
We say that a deck is perfectly shuffled if after applying theshuffling algorithm to any initial configuration of the cards, allpossible orderings of the deck are equally likely.
1. Describe a shuffling algorithm that perfectly shuffles anydeck of n cards in O(n) swaps. Prove that all possible orderings ofthe deck are equally likely using your algorithm (Hint: allorderings will be equally likely if every element has a 1/nprobability of ending up at any arbitrary index).
Consider the following approach for shuffling a deck of ncards:
Apply the following procedure for i = 1, . . . , n:
• Choose a random card in the deck.
• Swap the i-th card in the deck with the randomly-selectedcard.
We say that a deck is perfectly shuffled if after applying theshuffling algorithm to any initial configuration of the cards, allpossible orderings of the deck are equally likely.
1. Describe a shuffling algorithm that perfectly shuffles anydeck of n cards in O(n) swaps. Prove that all possible orderings ofthe deck are equally likely using your algorithm (Hint: allorderings will be equally likely if every element has a 1/nprobability of ending up at any arbitrary index).