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~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.
Answer
Answers can be viewed only if
- The questioner was satisfied and accepted the answer, or
- The answer was disputed, but the judge evaluated it as 100% correct.
The answer is accepted.
Join Matchmaticians Affiliate Marketing
Program to earn up to 50% commission on every question your affiliated users ask or answer.
- answered
- 350 views
- $15.00
Related Questions
- Statistics Probability
- Quantitative reasoning
- Topic: Large deviations, in particular: Sanov's theorem
- Probability and Statistics question please help
- Pulling balls out of a bin
- Trying to figure out probability problem for a series
- Probability of choosing the bakery with the best bread
- foundations in probability
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.