$card riffle shuffling$

Question

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.

Probability Statistics Stochastic Analysis

Lanx1594

Report

Alessandro Iraci

Can you define the distance?
Alessandro Iraci

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

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

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
Alessandro Iraci

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

Couls you shows how did you get 1/2 please? I cannot get that result.
Alessandro Iraci

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

Alessandro Iraci

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

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

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
Alessandro Iraci

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

Couls you shows how did you get 1/2 please? I cannot get that result.
Alessandro Iraci

((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 1

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.

View the answer

The number of riffle shuffles with the cut in position $k$ is $\binom{N}{k}$. The number of riffle shuffles with the cut in position $k$, such that the card in position $N$ remains in position $N$ is the same as the number of riffle shuffles of a deck of $N-1$ cards where the cut is in position $k$ again, that is, $\binom{N-1}{k}$. We can think of this as removing the card from the bottom, shuffling, and putting it back in afterwards.

It follows that the probability for that card to remain in position $N$ is the ratio of these two numbers, that is, \[ \binom{N-1}{k} \binom{N}{k}^{-1} = \frac{N-1!}{(N-k-1)!k!} \frac{(N-k)!k!}{N!} = \frac{N-k}{N}. \]

If I understand correctly, the total variation distance on a countable set is half of the $\ell^1$ norm, that is, half of the sum of the absolute values of the difference between the probabilities of single events. In our case, every shuffling has probability $1/N!$ for the uniform distribution, while for the compromised deck, it is $1/(N-1)!$ if $i$ is the card at the bottom, and $0$ otherwise. So we have that our distance is \[ \frac{1}{2} \sum_{\sigma \in S_N} \left\lvert \frac{\chi(\sigma(N)=i)}{(N-1)!} - \frac{1}{N!} \right\rvert \] which we can rewrite, separating the permutations with $\sigma(N)=i$ from the others, as \[ \frac{(N-1)!}{2} \left(\frac{1}{(N-1)!} - \frac{1}{N!} \right) + \frac{N! - (N-1)!}{2} \frac{1}{N!} \] and simplifying the factorials, as \[ \frac{1}{2} \left( 1 - \frac{1}{N} \right) + \frac{1}{2} \frac{N-1}{N} = \frac{N-1}{N}. \]
If $N=3$, a simple substitution tells us that the distance is $2/3$.

I hope I got all the definitions right (probability is not my area of expertise), if not, let me know with a comment and I will fix it.

Alessandro Iraci

$card riffle shuffling$

Answer

Related Questions

Search