Non-Markovian card shuffling processes: The random-to-cyclic transposition process is a non-Markovian card shuffling process, which at time t, exchanges the card at position L_t := t mod n with a random card. Mossel, Peres and Sinclair (2004) showed a lower bound of (0.0345+o(1))n*log(n) for the mixing time of the random-to-cyclic transposition process. They also considered a generalization of this process where the choice of L_t is adversarial, and proved an upper bound of C n*log(n) + O(n) (with C ≅ 4*10⁵) on the mixing time. We reduce the constant to 1 by showing that the random-to-top transposition chain (a Markov Chain) has robust mixing time ≤ n*log(n) + O(n) when the adversarial strategies are limited to holomorphic strategies, i.e. those strategies which preserve the symmetry of the underlying Markov Chain. We also show a O(n*log²(n)) bound on the robust mixing time of the lazy random-to-top transposition chain when the adversary is not limited to holomorphic strategies.

Reversible liftings: Chen, Lovász and Pak showed that for a reversible ergodic Markov Chain P, any reversible lifting Q of P must satisfy T(P) ≤ T(Q)*log(1/π_*) where π_* is the minimum stationary probability. Looking at a specific adversarial strategy allows us to show that T(Q) ≥ r(P) where r(P) is the relaxation time of P. This gives an alternate proof of the reversible lifting result and helps identify cases where reversible liftings cannot improve the mixing time by more than a constant factor.

1. Aldous, David; Diaconis, Persi. Shuffling cards and stopping times. Amer. Math. Monthly 93 (1986), no. 5, 333--348. MR0841111 (88a:60021)
2. Lee, Tzong-Yow; Yau, Horng-Tzer. Logarithmic Sobolev inequality for some models of random walks. Ann. Probab. 26 (1998), no. 4, 1855--1873. MR1675008 (2001b:60090)
3. Ivona Bezakova and Daniel Stefankovic. Convex combinations of markov chains and sampling linear orderings. In preparation.
4. Fang Chen, Laszlo Lovasz, and Igor Pak. Lifting markov chains to speed up mixing. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 275--281, New York, NY, USA, 1999. ACM Press. MR1798046
5. Deepak Dhar. The abelian sandpile and related models. PHYSICA A, 263:4, 1999.
6. Diaconis, P.; Saloff-Coste, L. Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 (1996), no. 3, 695--750. MR1410112 (97k:60176)
7. Diaconis, Persi. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes---Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069 (90a:60001)
8. Diaconis, Persi; Saloff-Coste, Laurent. Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131--2156. MR1245303 (95a:60009)
9. Diaconis, Persi; Saloff-Coste, Laurent. Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 (1993), no. 3, 696--730. MR1233621 (94i:60074)
10. Diaconis, Persi; Shahshahani, Mehrdad. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159--179. MR0626813 (82h:60024)
11. Gao, Fuqing; Quastel, Jeremy. Exponential decay of entropy in the random transposition and Bernoulli-Laplace models. Ann. Appl. Probab. 13 (2003), no. 4, 1591--1600. MR2023890 (2005a:60155)
12. Goel, Sharad. Analysis of top to bottom-$k$ shuffles. Ann. Appl. Probab. 16 (2006), no. 1, 30--55. MR2209335 (Review)
13. Hoeffding, Wassily. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 1963 13--30. MR0144363 (26 #1908)
14. Horn, Roger A.; Johnson, Charles R. Topics in matrix analysis. Cambridge University Press, Cambridge, 1991. viii+607 pp. ISBN: 0-521-30587-X MR1091716 (92e:15003)
15. Miclo, Laurent. Remarques sur l'hypercontractivité et l'évolution de l'entropie pour des chaînes de Markov finies. (French) [Remarks on hypercontractivity and evolution of entropy in finite Markov chains] Séminaire de Probabilités, XXXI, 136--167, Lecture Notes in Math., 1655, Springer, Berlin, 1997. MR1478724 (99b:60104)
16. Mironov, Ilya. (Not so) random shuffles of RC4. Advances in cryptology---CRYPTO 2002, 304--319, Lecture Notes in Comput. Sci., 2442, Springer, Berlin, 2002. MR2054828 (2004m:94068)
17. Ravi Montenegro. Duality and evolving set bounds on mixing times.
18. Ravi Montenegro and Prasad Tetali. Mathematical Aspects of Mixing Times in Markov Chains, volume 1 of Foundations and Trends in Theoretical Computer Science. NOW Publishers, Boston-Delft, 2006.
19. Elchanan Mossel, Yuval Peres, and Alistair Sinclair. Shuffling by semi-random transpositions. In Proceedings of FOCS 2004, volume 00, pages 572--581, Los Alamitos, CA, USA, 2004. IEEE Computer Society.
20. Saloff-Coste, Laurent. Random walks on finite groups. Probability on discrete structures, 263--346, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023654 (2004k:60133)