Card riffle shuffling
Consider a deck of $N$ cards labelled $1,......, N.$
Find the probability that the card in position $N$ remains in position N following a binomial riffle shuffle where the cut position is $k \sim \text{Binomial}(N, 1/2)$.
Assume that the deck is now well-shuffled, in other words, every permutation has equal probability $1/N!$ (i.e. the uniform distribution on SN. SN is the set of permutations of the set $\{1,2,3,..........,N\})$. However, the deck becomes compromised, that is, the card on the bottom is seen to be card $i$.
Find the total variation distance to uniformity of the compromised deck in the specific case $N=3.$
Find the distance to uniformity of the compromised deck in the general case $N.$
Lanx1594
14
Answer
Answers can only be viewed under the following conditions:
- The questioner was satisfied with and accepted the answer, or
- The answer was evaluated as being 100% correct by the judge.
Alessandro Iraci
1.7K
The answer is accepted.
Join Matchmaticians Affiliate Marketing
Program to earn up to a 50% commission on every question that your affiliated users ask or answer.
Can you define the distance?
Also I don't understand what you mean by Binomial(N, 1/2). I mean, I do have a definition for that thing but it doesn't make sense in the context I think.
Sorry, I will clarify. AWhen doing the riffle shuffle, there are two piles of cards. If cut from other card position, then the first pile has k cards, second pile has (n-k) cards. Therefore, k~ Binomial(N, 1/2) and the probability of having k cards in the first pile is “ (n choose k) times 2^(-N). I hope I made it clear.
Sorry, The previous one has typo. When doing the riffle shuffle, there are two piles of cards. If cut from k-th card position, then the first pile has k cards, second pile has (n-k) cards. Therefore, k~ Binomial(N, 1/2) and the probability of having k cards in the first pile is “ (n choose k) times 2^(-N). I hope I made it clear
Sorry, I don't understand. You mean that k is not fixed but has its own probability distribution, which is the one you wrote? If that is the case, you have to multiply (N-k)/N by (N choose k)*2^{-N} and sum over k, which gives you 1/2.
Couls you shows how did you get 1/2 please? I cannot get that result.
((N-k)/N) * (N choose k) = (N-1 choose k), so if you sum over k you get 2^(N-1) and if you multiply by 2^-N you get 1/2.