Application of LDT to Many Hypotheses Optimal Testing for Markov Chain


  • Leader NavaeI Payame Noor University (PNU)


The problem of many (L > 2) hypotheses testing on distributions of a finite state Markov chain is studied. We apply large deviations techniques (LDT). It is proved that this method of investigation in solving the problem of logarithmically asymptotically optimal (LAO) hypotheses testing is easier than the procedure that was introduced by Haroutunian. The matrix of exponents E = fEljmg; m; l = 1;L, of error probabilities of the LAO test Eljm(Á) = lim N!1¡ 1 N log ®ljm(ÁN); where ®Nl jm(ÁN) for l 6= m is the probability to accept the hypothesis l, when the hypothesis m is true, is determined.


Blahut R.E. “Principle and Practice of Information Theory", reading, MA, Addison-Wesley, 1987.

Csiszár I. and Shields P. “Information Theory and Statistics", Fundamentals and Trends in Communications and Information Theory, vol. 1, no. 4, 2004.

Csiszár I. and Körner J. “Information Theory: Coding Theorem for Discrete Memoryless Systems", Academic press, New York, 1981

Csiszár I. “Method of types", IEEE Trans. Inform. Theory, vol. 44. no. 6. pp. 2505-2523, 1998.

Dembo A. and Zeitouni O. “Large Deviations Techniques and Applications", Jons and Bartlet. Publishers, London, 1993.

Gutman M. “Asymptotically optimal classification for multiple test with empirically observed statistics", IEEE Trans. Inform. Theory, vol. 35, no. 2. pp. 401-408, 1989.

Haroutunian E.A. “On asymptotically optimal testing of hypotheses concerning Markov chain", (in Russian). Izvestia Acad. Nauk Armenian SSR. Seria Mathem. vol. 22, no. 1. pp. 76-80, 1988.

Haroutunian E.A, Haroutunian M.E and Harutyunyan A.N. “Reliability Criteria in Information Theory and in Statistical Hypothesis Testing", Foundations and Trends in Communications and Information Theory, vol. 4, no. 2-3, 2007.

Kullback S. “Information Theory and Statistics", Wiley, New York, 1959.

Natarajan S. “Large deviations, hypotheses testing, and source coding for finite Markov chain", IEEE Trans. Inform. Theory, vol. 31, no. 3, pp. 360-365, 1985.

Navaei L. “On many hypotheses LAO testing via the theory of large deviations", Far East Journal of Mathematical Sciences, vol. 25, no. 2, pp. 335-344, 2007.




How to Cite

NavaeI, L. . (2008). Application of LDT to Many Hypotheses Optimal Testing for Markov Chain. Mathematical Problems of Computer Science, 31, 73–78. Retrieved from