Springe direkt zu Inhalt

Claas Fandré:

Bounds on the mixing time of Catalan structures


Analyzing a theoretical problem often involves a single structure with multiple arrangements, like a binary tree with a fixed number of nodes where the tree structure can be different or the permutations of a fixed number of playing cards. Sampling random elements from these arrangements can be complex, especially if that structure has an exponential number of elements. In contrast, a definition of a local operation switching randomly between the arrangements is relatively easy, like the rotation of a tree or a shuffle of the cards.

We can use that if we start at one specific configuration and perform the operation until we get a random arrangement. The mixing time is the expected number of local operations we must perform to get from the fixed element to a random one.

We go through the main theory for deriving this mixing time, by A. Sinclair. For Catalan structures, a family of structures growing by following a specific sequence, we illustrate several techniques to derive bounds for that mixing time. These are analyzed, and the results are compared. Also, we give an outlook for applications in other contexts.

Master of Science (M.Sc.)