![](images/spacer.gif) |
|
|
| | | | | |
|
|
|
|
|
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) .
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|