Using a noncommutative generating walks to enumerate special walks

We study the area distribution of closed walks of length n, starting and ending at the origin. Based on a slight modification of the concept of algebraic area of a walk in the square lattice, we use a noncommutative generating function to study these walks according to their areas. Then a polynomial time algorithm for calculating the exact distribution of such walks for a given length is discussed. The presented algorithm takes advantage of the Chinese remainder theorem to overcome the problem of arithmetic with large integers. Finally, the results of the implementation are given for n = ۳۲, ۶۴, ۱۲۸.

کلیدواژه ها:

square lattice ، random walk ، algebraic area ، distribution