Normal forms of random braids

作者：Gebhardt Volker^*; Tawnl Stephen

来源：Journal of Algebra, 2014, 408: 115-137.

DOI：10.1016/j.jalgebra.2013.10.008

• Random braids
• Garside monoid
• Normal form
• Penetration distance
• Expected value
• Regular language

Analysing statistical properties of the normal forms of random braids, we observe that, except for an initial and a final region whose lengths are uniformly bounded (that is, the bound is independent of the length of the braid), the distributions of the factors of the normal form of sufficiently long random braids depend neither on the position in the normal form nor on the lengths of the random braids. Moreover, when multiplying a braid on the right, the expected number of factors in its normal form that are modified, called the expected penetration distance, is uniformly bounded.
We explain these observations by analysing the growth rates of two regular languages associated to normal forms of elements of Garside groups, respectively to the modification of a normal form by right multiplication.
A universal bound on the expected penetration distance in a Garside group yields in particular an algorithm for computing normal forms that has linear expected running time.

• 出版日期2014-6-15