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.
그래프에서 멋대로 걷기는 상태공간의 확률분포에 따른 추이확률을 가지는 시불변 마코프 연쇄를 말하며 그래프이론, 조합론, 확률론, 조화해석학 등에서 연구된다.
이 논문에서는 네트워크나 도로망과 같은 조합론의 문제를 반영한 멋대로 걷기 모델을 구체화하고 이를 이용하여 효율적인 확률 알고리듬을 개발하고자 한다. 유한군으로 부터 직접 유도 되지는 않지만 유한군들 몇 개로 분해할 수 있는 유한군 합을 고려한다. 그래프위의 한 꼭지점에서 다른 꼭지점으로 도착하는데 걸리는 최소 시간을 최초도착시간으로 정의 한다. 유한군의 군표현론을 이용하여 최초도착시간에 대한 확률생성함수의 양적인 공식을 유도한다.
유한군에 정의된 확률은 유향 그래프를 유도하며 그래프에서 멋대로 것기 규칙을 결정한다. 두 원소의 군 이항연산차가 양수 확률 값을 가질 때 두 원소는 서로 이웃하며 두 원소 사이의 추이확률은 군 이항연산차의 확률 값으로 정의된다. 제 2 장에서는 유한군의 군표현론을 바탕으로 한 다이아코니스의 식을 이용하여 최초도착시간에 대한 확률생성함수의 양적인 공식을 몇개 유도한다. 순환군과 대칭군에서 멋대로 걷기를 보기로 제시한다.
제 3 장과 제 4 장 에서는 두 유한군에 정의된 각각의 확률에 의해 유도되는 두 유향 그래프를 한 점 또는 두 점에서 만나도록 연결한 유한군 합 그래프를 고려한다. 멋대로 걷기 규칙은 각각의 군에 정의된 확률을 따르며 두 유향 그래프의 연결점에서는 균등분포를 따른다. 순환군 합과 대칭군 합에서 멋대로 걷기를 보기로 제시한다. 제 5 장에서는 십자형, 막대사탕형과 아령형 그래프에서 균등 확률분포를 따르는 단순 멋대로 걷기를 고려한다.
