TOPICS
Search

Borel-Tanner Distribution


BorelTannerDistribution

Let S_n be the set of permutations of {1, 2, ..., n}, and let sigma_t be the continuous time random walk on S_n that results when randomly chosen transpositions are performed at rate 1. Let d(sigma_t) be the distance from the identity I at time t, i.e., the minimum number of transpositions needed to return to I. Then as n->infty, d(sigma_(nc/2))/n->u(c), where

 u(c)=1-sum_(k=1)^infty(k^(k-2))/(ck!)(ce^(-c))^k

(Berestycki 2004; Berestycki and Durrett 2004), where u(c) is known as the Borel-Tanner distribution (Trott 2006, p. 284).

BorelTannerDistributionReIm

The Borel-Tanner distribution for complex c is plotted above in the complex plane (Trott 2006, p. 284).

Interestingly, this function has the value c/2 for 0<=c<=1 (Berestycki 2004; Trott 2006, p. 284).


Explore with Wolfram|Alpha

References

Berestycki, N. "The Hyperbolic Geometry of Random Transpositions." 31 Oct 2004. http://arxiv.org/abs/math.PR/0411011.Berestycki, N. and Durrett, R. "A Phase Transition in the Random Transposition Random Walk." Probab. Theor. Rel. Fields 136, 203-233, 2006.Haight, F. A. and Breuer, M. A. "The Borel-Tanner Distribution." Biometrika 47, 143-150, 1960.Trott, M. The Mathematica GuideBook for Numerics. New York: Springer-Verlag, 2006. http://www.mathematicaguidebooks.org/.

Referenced on Wolfram|Alpha

Borel-Tanner Distribution

Cite this as:

Weisstein, Eric W. "Borel-Tanner Distribution." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Borel-TannerDistribution.html

Subject classifications