James P. Jarvis

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: This paper surveys how graph-theoretic and algebraic considerations can be used to study finite-state Markov chains. This perspective is a useful complement to the standard, matrix-based analysis of these chains. In particular, the concept of an equivalence relation is useful in carrying out state classification and in determining periodicity. Also, certain of the Markov chain computations are most efficiently carried out using a depth-first search (state classification), while others involve a breadth-first search (determining the period of an irreducible chain) of the state transition diagram.

Key Words: Markov chain, periodicity, state transition diagram