11
$\begingroup$

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!$:

entropy approaches that of perfect shuffling

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?

$\endgroup$
  • 6
    $\begingroup$ That's an interesting question to talk about with a Thanksgiving-dinner-drunk-uncle wanting to play cards :P $\endgroup$ – Patrick Da Silva Mar 5 '16 at 20:48
  • 2
    $\begingroup$ The (exponential) rate of convergence to uniform (in distribution/total variation) is governed by the second largest eigenvalue $\lambda_2$ of $n!\times n!$ the transition matrix $P$. Since entropy peaks (is maximized) around the uniform distribution, convergence of entropy would be governed by $\lambda_2^2$ (haven't computed it). Here is Diaconis's paper on top-to-random shuffle: statweb.stanford.edu/~cgates/PERSI/papers/randomshuff92.pdf and one by others dealing with entropy specifically:suu.edu/faculty/berri/pdf/sensem/farnswortharticle.pdf with many references. $\endgroup$ – A.S. Mar 5 '16 at 22:06
  • 1
    $\begingroup$ $\lambda_2=\frac {n-2}n$, hence the exponent is $2\ln (1-\frac 2 n)$ which matches your numerics. $\endgroup$ – A.S. Mar 6 '16 at 8:06
  • 1
    $\begingroup$ @A.S.: Thanks very much! I think that's good enough for an answer? $\endgroup$ – joriki Mar 6 '16 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.