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

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