Random walks on a union of finite groups = 유한군 합에서 멋대로 걷기

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.
Advisors
Choe, Geon-Horesearcher최건호researcher
Publisher
한국과학기술원
Issue Date
2001
Identifier
169543/325007 / 000985002
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 수학전공, 2001.8, [ viii, 84 p. ]

Keywords

확률생성함수; random walks; probability generating functions; first hitting times; 최초도착시간; 멋대로 걷기; group representations; 군표현론

URI
http://hdl.handle.net/10203/41840
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=169543&flag=t
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 53
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0