AN EFFICIENT IMPLEMENTATION OF THE EXACT ENUMERATION METHOD FOR RANDOM WALKS ON SIERPINSKI CARPETS

Abstract

In the following, we present a highly efficient algorithm to iterate the master equation for random walks on effectively infinite Sierpinski carpets, i.e. without surface effects. The resulting probability distribution can, for instance, be used to get an estimate for the random walk dimension, which is determined by the scaling exponent of the mean square displacement versus time. The advantage of this algorithm is a dynamic data structure for storing the fractal. It covers only a little bit more than the points of the fractal with positive probability and is enlarged when needed. Thus the size of the considered part of the Sierpinski carpet need not be fixed at the beginning of the algorithm. It is restricted only by the amount of available computer RAM. Furthermore, all the information which is needed in every step to update the probability distribution is stored in tables. The lookup of this information is much faster compared to a repeated calculation. Hence, every time step is speeded up and the total computation time for a given number of time steps is decreased.