Deeper Inside Finite-state Markov chains
Main Article Content
Abstract
A b s t r a c t . The eíĩective application o f Markov chains has been paid much attention, and it has
raised a lot of thcoreticaỉ and applied problems. In this paper, vve vvould like to approach One o f
these problems vvhich is íìnding the long-run behavior o f extremely huge-state Markov chains
according to the direction of investigating the structure o f
Markov Graph to reduce complexity
o f computation. We focus on the vvay to access to the íìnite-state Markov chain theory via
Graph theory. We suggested some basic knovvledge about State classiíìcation and a small project
o f modelling the structure and the moving process of the /inite-state Aíarkov Chain modeỉ. This
project based on the remark that il is impossible to study deeperly the finite-state Markov Chain
theory i f vve do not have the clear sense about the structure and the movement o f it.
References
U n i v e r s i t y T c c h n i c a ỉ Rc port. 1998.
| 2 Ị r C h u n g , L a p l a c i a n s and Ih c C h e c g c r i n c q u a l i t y f o r d i r c c t e d graphs, Annaỉs o f Combinatorics. t o appear.
[ 3 ) J. F a k c h a r o c n p h o l , A n I m p r o v c d V C - D i m c n s i o n B o u n d f o r F i n d i n g N e t \ v o r k Pai l u r e s , Master s thesis, B c r k c l c y U n i -
vcrsity o f Califormia, 2001.
| 4 ] T .H . í ỉavclÌNvala, S.D. K a m v a r , The se c o n d eigcrtvaluc o f the Googỉe niaỉrìx, S t a n í o r d U n i v c r s i t y T c c h n i c a í Rcporl,
2003.
|5Ị s. Kamvar, T. Haveliwala, c . Manning, G. Golub, Kxtrapolation melhods for accelcrating PagcRank compulations, ỉn
proceedings o f the Tvveựìh ỉnternaiional IVorỉd yvide Web Conference. 2 003.
[ 6 ] J. K l e i n b e r g , D c t c c t i n g a N c h v o r k F a i l u r e , Proc. 4 l s t Annuaỉ IEEE Symposium on Foundations o f Computer Science,
2002
[7ị p. Balđi, p. Frasconi, p. Smyth, Kíodeling the Internet and ihe Web% John Wilcy & Sons, Inc. New York, 2003.
[ 8 ] l i . B o l l o b á s , Random Grapìis, C a m b r i d g c U n i v e r s i t y Press, 2001.
[9] D. Callavvay, J. Hopcroíì, J. Klcinberg, M. Newman, s. Stragalz, Are r andomly grown g r a p h s realỉy random?
http://arxiv.org/abs/cond-maưO 104546 Voi 2 (2001) 1.
[ 1 0 ] D . M . M o u n t , Desìgn and Anaỉysis o f Computer A ỉgonthms, D ept. o f C o m p u t e r Science, U n i v c r s i t y o f Mar>'land, 2003.
[11] H. Tijms, p. Schram, O rstat: M CQ ue ue . A soíìwarc in Dept o f Economeưics and Operational Research 2000-2002.