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.$

  • 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.

Answer

Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer
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.