Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 10 (2005) > Paper 26 open journal systems 


Stein's Method and Descents after Riffle Shuffles

Jason Fulman, University of Pittsburgh, USA


Abstract
Abstract. Berestycki and Durrett used techniques from random graph theory to prove that the distance to the identity after iterating the random transposition shuffle undergoes a transition from Poisson to normal behavior. This paper establishes an analogous result for distance after iterates of riffle shuffles or iterates of riffle shuffles and cuts. The analysis uses different tools: Stein's method and generating functions. A useful technique which emerges is that of making a problem more tractable by adding extra symmetry, then using Stein's method to exploit the symmetry in the modified problem, and from this deducing information about the original problem.


Full text: PDF

Pages: 901-924

Published on: July 14, 2005


Bibliography

    1. Aldous, D., Random walks on finite groups and rapidly mixing Markov chains. Seminar on probability, XVII, 243-297, Lecture Notes in Math., 986, Springer, Berlin, 1983. MR0770418 (86j:60156) .

    2. Barbour, A. D., Holst, L., and Janson, S., Poisson approximation. Oxford Studies in Probability, 2. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992. x+277 pp. MR1163825 (93g:60043) .

    3. Bayer, D., and Diaconis, P., Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2 (1992), no. 2, 294-313. MR1161056 (93d:60014) .

    4. Berestycki, N. and Durrett, R., A phase transition in the random transposition walk. Paper math.PR/0403259 at http://xxx.lanl.gov. Math. Review number not available.

    5. Bourque, G. and Pevzner, P., Genome-scale evolution: reconstructing gene orders in ancestral species, Genome Research. 12 , 26-36. Math. Review number not available.

    6. Carlitz, L., Kurtz, D. C., Scoville, R., and Stackelberg, O. P. Asymptotic properties of Eulerian numbers. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 23 (1972), 47-54. MR0309856 (46 #8961) .

    7. Chatterjee, S., An abstract Berry-Esseen theorem, preprint (2005).

    8. Chatterjee, S., Diaconis, P., and Meckes, E., Exchangeable pairs and Poisson approximation. Probab. Surv. 2 (2005), 64-106 (electronic). MR2121796 .

    9. Diaconis, Persi. Mathematical developments from the analysis of riffle shuffling. Groups, combinatorics & geometry (Durham, 2001), 73-97, World Sci. Publishing, River Edge, NJ, 2003. MR1994961 (2005a:60016) .

    10. Durrett, R., Genome rearrangement: recent progress and open problems, (2003), available at http://www.math.cornell.edu/~durrett. Math. Review number not available.

    11. Eriksson, H., Eriksson, K., Sjostrand, J., Expected number of inversions after a sequence of random adjacent transpositions, Formal power series and algebraic combinatorics (Moscow, 2000), 677-685, Springer, Berlin, 2000. MR1798262 (2001i:05018) .

    12. Feller, W., An introduction to probability theory and its applications. Vol. I. Third edition, John Wiley & Sons, Inc., New York-London-Sydney 1968 xviii+509 pp. MR0228020 (37 #3604) .

    13. Foata, D., and Schutzenberger, M.. Theorie geometrique des polynmatics, Lecture Notes in Mathematics, Vol. 138 Springer-Verlag, Berlin-New York 1970 v+94 pp. MR0272642 (42 #7523) .

    14. Fulman, J., Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting. J. Algebra 231 (2000), no. 2, 614-639. MR1778162 (2001j:05121) .

    15. Fulman, J., Stein's method and non-reversible Markov chains, in Stein's method: expository lectures and applications, 69-77, IMS Lecture Notes Monogr. Ser., 46, Inst. Math. Statist., Beachwood, OH, 2004. MR2118603 .

    16. Fulman, J., A card shuffling analysis of deformations of the Plancherel measure of the symmetric group. Electron. J. Combin. 11 (2004), no. 1, Research Paper 21, 15 pp. (electronic). MR2035315 (2005d:05007) .

    17. Frobenius, Ueber die Bernoullischen zahlen und die Eulerschen polynome, Sitz. Ber. Preuss. Akad. Wiss. (1910), 808-847. Math. Review number not available.

    18. Gradshteyn, I. S. and Ryzhik, I. M., Table of integrals, series, and products. Sixth edition. Academic Press, Inc., San Diego, CA, 2000. xlvii+1163 pp. MR1773820 (2001c:00002) .

    19. Hannenhalli, S. and Pevzner, P., Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46 (1999), no. 1, 1-27. MR1692509 (2000j:92013) .

    20. Hardy, G., Littlewood, J., and Polya, G., Inequalities 2d ed. Cambridge, at the University Press, 1952. xii+324 pp. MR0046395 (13,727e) .

    21. Leeming, D., The real zeros of the Bernoulli polynomials. J. Approx. Theory 58 (1989), no. 2, 124-150. MR1006328 (90k:33029) .

    22. Mann, B., Shuffling n cards with cn^(3/2) hands gives asymptotically normal rising sequences, Unpublished, undated manuscript from mid 1990's.

    23. Rinott, Y. and Rotar, V., On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics. Ann. Appl. Probab. 7 (1997), no. 4, 1080-1105. MR1484798 (99g:60050) .

    24. Stark, D., Ganesh, A., and O'Connell, N., Information loss in riffle shuffling. Combin. Probab. Comput. 11 (2002), no. 1, 79-95. MR1888184 (2002m:62015) .

    25. Stein, C., Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes---Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. iv+164 pp. MR0882007 (88j:60055) .

    26. Tanny, S. A probabilistic interpretation of Eulerian numbers. Duke Math. J. 40 (1973), 717-722. MR0340045 (49 #4802) .

















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489