Random walks on a union of finite groups

Abstract

Random walks are time-homogeneous Markov chains whose transition probabilities are adapted to the underlying state space. It is a topic and a method in graph theory, combinatorics, probability and harmonic analysis.

In this thesis we consider random walks on some finite graphs, which can explain the probabilistic properties of combinatorial problems, such as network or road congestion problems. Considered are unions of finite groups which are not directly induced by some finite groups, but can be decomposed into several finite graphs of finite groups. Using group representations of finite groups, we derive the explicit formulas of the probability generating functions of the first hitting time, which is defined as the minimum number of steps that it takes to reach an element starting from another element.

A probability on a finite group induces a directed graph in a way that an element is regarded as adjacent to another element if the difference between them, in the sense of group operation, has a positive probability. It also determines random walks on the group. In Chapter 2 we formulate the probability generating function of the first hitting time on a finite group by adapting Diaconis`s formula based on group representations of finite groups.

In Chapter 3 and Chapter 4 we consider two directed graphs, respectively induced by two finite groups with probabilities. We combine the two directed graphs in a way that they meet at one or two elements. Random walks are determined by the rule based on the probabilities on the groups: the uniform distribution is given at the combining elements. We construct some examples on a union of two cyclic groups, a union of two hypercubes and a union of two symmetric groups. In Chapter 5 we consider other graphs, such as a cross, a lollipop and dumbbells, and consider the simple random walk which moves from an element to one of its adjacent elements with equal probability.