Fu, Wang and Lou（2002） present an exact and large deviation approximation for the distribution of the longest run in a sequence of multi-state Markov dependent trials with order k<=1 . In this thesis, we extend their results to general order k and, in addition, we derive the distribution of any pattern. As an application, we derived the distribution of the frequency of n -words in DNA sequences. The finite Markov chain imbedding technique by Fu and Koutras, (1994) is used to obtain the exact distributions. For k>=2 , numerical comparisons between the exact distributions and approximations of the frequency of n -words in DNA sequences are provided to illustrate the theoretical results. Furthermore, the distributions of the longest run statistics in DNA sequences are demonstrated through real data analysis. The results obtained in the thesis can be applied to protein sequences with minor modifications.

Chapter 1Introduction 1
1.1 DNA sequence 2
1.2Run Statistics 3
1.3Literature Review 5
Chapter 2Exact Distribution 7
2.1Markov chain imbedding technique7
2.2Notations for DNA sequences 8
2.3Distribution of the frequency of n-words9
Chapter 3Large Deviation Approximation 14
Chapter 4Data Analysis 17
4.1Real Data Analysis 17
4.2Longest runs 20
Chapter 5Conclusion and Further Research 24
Reference 25

Amir Dembo and Ofer Zeitouni（1998）, Large deviations techniques and applications. 2nd ED. New York: Springer-Verlag
Chao, M.T. and Fu, J.C.（1989）, “A limit theorem of certain repairable systems”, Annals of the Institute of Statistical Mathematics, 41, 809-811
──（1991）, “The reliability of large series systems under Markov structure”, Advances in Applied Probability, 23, 894-908.
Feller, W.（1968）, An introduction to Probability Theory and Its Applications, Vol. I（3rd）, New York: John Wiley.
Fu, J.C.（1986）, “Reliability of consecutive-k-out-of-n: F systems with (k-1)-step Markov dependence”, IEEE Transactions on Reliability, R35, 602-606
──（1996）, “Distribution theory of runs and patterns associated with a sequence of multi-state trials”, Statistica Sinica 6, 957-974.
Fu, J.C. and Hu, B.（1987）, “On reliability of a large consecutive-k-out-of-n: F systems with (k-1)-step Markov dependence”, IEEE Transactions on Reliability, R36, 75-77.
Fu, J. C. and Koutras, M. V.（1994）, “Distribution theory of runs: a Markov chain approach”, Journal of the American Statistical Association, Vo.89, 1050-1058.
Fu, James C., Wang, Liqun and Lou, W.Y. Wendy（2003）, “On exact and large deviation approximation for the distribution of the longest run in a sequence of two-state Markov dependent trials”, Journal of Applied Probability 40, no. 2, 346-360
Gibbons, J.D.（1971）, Nonparametric Statistical Inference, New York: McGraw-Hill
Ling, K.D.（1988）, “On binomial distributions of runs”, Statistics and Probability Letters, 6, 247-250.
Mood, A.M.（1940）, “The distribution theory of runs”, Annals of Mathematical Statistics, 11, 367-392.
Mosteller , F.（1941）, “Note on an application of runs to quality control charts”, Annals of Mathematical Statistics, 12, 228-232.
Schwager , S.J.（1983）, “Run probabilities in sequences of Markov-dependent trials”, Journal of the American Statistical Association, 78, 168-175.
Wu, Tiee-Jian, Hsieh, Ya-Ching and Li, Lung-An（2001）, “Statistical Measures of DNA sequence dissimilarity under Markov chain models of base composition”, Biometrics 57, 441-448.
Wald A. and Wolfowitz, J.（1940）, “On a test whether two population are from the same population”, Journal of Mathematical Statistics, 11, 147-162
Walsh, J.E.（1965）, Handbook of Nonparametric statistics, New York: D. Van Nostrand.
Wolfowitz , J.（1943）, “On the theory of runs with some applications to quality control”, Annals of Mathematical Statistics, 14, 280-288.