At what rate does the entropy of shuffled cards converge? Consider a somewhat primitive method of shuffling a stack of $n$ cards: In every step, take the top card and insert it at a uniformly randomly selected one of the $n$ possible positions above, between or below the remaining $n-1$ cards.
Start with a well-defined configuration, and then track the entropy of the distribution over the possible permutations of the stack as these shuffling steps are applied. It starts off at $0$. Initially most moves will lead to unique permutations, so we should have roughly $n^k$ equiprobable states after $k$ steps, so the entropy should initially increase as $k\log n$. For $k\to\infty$ it should converge to the entropy corresponding to perfect shuffling, $\log n!\approx n(\log n-1)$.
What I'd like to know is how this convergence takes place. I have no idea how to approximate the distribution as it approaches perfect shuffling. I computed the entropy for $n=8$ for $k$ up to $50$; here's a plot of the natural logarithm of the deviation from the perfect shuffling entropy $\log n!$:

The red crosses show the computed entropy; the green line is a linear fit to the last $30$ crosses, with slope about $-0.57$. So the entropy converges to its maximal value roughly as $\exp (-0.57k)$. For $n=7$, the slope is about $-0.67$, and for $n=9$ it's about $-0.50$. How can we derive this behaviour?
 A: 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)$$
