At what rate does the entropy of shuffled cards converge?

Solution 1:

Such method of shuffling cards is essentially a random walk on the symmetric group $S_n$ with step distribution $X_i = (1, Y_i)$ and $Y_i$ is uniformly distributed on $\{1, ... , n\}$. Such process (as any other random walk on a finite group) is a finite-state Markov chain. Moreover, it is not hard to see, that this Markov chain is both aperiodic and recurrent. Therefore its distribution converges to the stationary one with speed $O(\lambda_2^k)$, where $\lambda_2$ is the transition matrix eigenvalue with second largest absolute value and k is the number of transition step.

It is not hard to see, that the stationary distribution under such shuffling is the uniform distribution on $S_n$. Moreover, according to the Theorem 4.1 from "Analysis of Top to Random Shuffles" by P. Diaconis, J.A. Fill and J. Pitman, the transition matrix of this process has eigenvalues $\{\frac{j}{n}| 0 \leq j \leq n-2 \} \cup \{1\}$, with second largest eigenvalue being $\frac{n-2}{n}$. Therefore on the step $k$ the probability our process reaching any given permutation will be $\frac{1}{n!} + O((\frac{n-2}{n})^k)$ for large $k$.

Now, knowing the distribution we can compute the entropy. It is:

$$-n!(\frac{1}{n!} + O((\frac{n-2}{n})^k))\ln(\frac{1}{n!} + O((\frac{n-2}{n})^k) = -\ln(\frac{1}{n!} + O((\frac{n-2}{n})^k)) + O((\frac{n-2}{n})^k) = \ln(n!) + O((\frac{n-2}{n})^k)$$