On Multiple Hypotheses LAO Testing by Informed Statistician for Arbitrarily Varying Markov Source and on Such Source Coding Reliability Function


  • Naira M. Grigoryan State Engineering University of Armenia (Polytechnic)


In this paper the problem of multiple hypotheses testing for arbitrarily varying Markov source (AVMS) with state sequence known to the statistician is solved from the point of view of logarithmically asymptotically optimal (LAO) testing. The matrix
of asymptotic interdependencies of all possible pairs of the error probability exponents
(reliabilities) in optimal testing for this model is studied. The LAO test, assuming that exponents of some number of the error probabilities are given, ensure the best asymptotic exponents for the rest of them. We ¯nd LAO test and the corresponding
matrix of all error probability exponents. As an application to information theory, the E-optimal rate R(E) (the minimum rate R of the source sequences compression when the decoding error probability is less than exp{–NE}, E > 0) and the reliability function E(R) of AVMS coding are determined.


W.Hoeffding, “Asymptotically optimal tests for multinomial distributions," Ann. Math. Statist., vol. 36, pp. 369-401, 1965.

I.Csiszár and G.Longo, “On the error exponent for source coding and for testing simple statistical hypotheses, "Studia Scientiarum Mathem. Hung., vol. 6, pp. 181-191, 1971.

L. Birgé, “Vitess maximals de déroismence des erreurs et tests optimaux associes". Z. Wahrsch. verw. Gebiete, vol. 55, pp. 261-173, 1981.

E.A. Haroutunian, “Logarithmically asymptotically optimal testing of multiple statistical hypotheses", Problems of Control and Information Theory, vol. 19, no. 5-6, pp. 413-421, 1990.

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

F.-W. Fu and S.-Y. Shen, “Hypothesis testing for arbitrarily varying source with exponential-type constraint", IEEE Trans. Inform. Theory, vol. 44, no. 2, pp. 892-895, 1998. 7. E.A. Haroutunian, “On asymptotically optimal testing of hypotheses concerning Markov chain", (in Russian), Izvestiya Akademii Nauk Armenii, Mathematika, vol. 23, no. 1, pp. 76-80, 1988.

E.A. Haroutunian, “On asymptotically optimal criteria for Markov chains", (in Russian), The first World Congress of Bernoulli Society, section 2, vol. 2, no. 3, pp. 153-156, 1989.

E.A. Haroutunian, “Asymptotically optimal testing of many statistical hypotheses concerning Markov chain", (in Russian), 5th Intern. Vilnius Conference on Probability Theory and Mathem. Statistics, vol. 1 (A-L), pp. 202-203, 1989.

R.F. Ahlswede, E.V. Aloyan and E.A. Haroutunian, “On logarithmically asymptotically optimal hypothesis testing for arbitrary varying source with side information", Lecture Notes in Computer Science, Volume 4123, "General Theory of Information Transfer and Combinatorics", Springer, pp. 457-461, 2004.

E.A. Haroutunian and P.M. Hakobyan, “On Multiple hypothesis testing by informed statistician for arbitrarily varying object and application to sourcecoding", Mathematical Problems of Computer Science, vol. 23, pp. 36-46, 2004.

E.A. Haroutunian, M.E. Haroutunian and A.N. Harutyunyan, “Realability criteria in information theory and in statistical hypotheses testing", Foundation and Trends in Communications and Information Theory, vol. 4, no. 2-3, 2008.

E.A. Haroutunian and N.M. Grigoryan, “On reliability approach for testing of many distributions for pair of Markov chains", Mathematical Problems of Computer Science, vol. 29, pp. 89-96, 2007.

I. Csiszár and J.Körner, “Information theory, coding theorems for discrete memoryless systems", Academic Press, New York, 1981.

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

P. Jacket and W. Szpankovksi, “Markov types and minimax redundancy for Markov sources, "IEEE Trans. Inform. Theory, vol. 50, no. 7, pp. 1393-1402, 2004.

K. Marton, “Error exponent for source coding with a fiedelity criterion, "IEEE Trans. Inform. Theory, vol. 20, no. 2, pp. 197-199, 1974.




How to Cite

Grigoryan, N. M. . (2008). On Multiple Hypotheses LAO Testing by Informed Statistician for Arbitrarily Varying Markov Source and on Such Source Coding Reliability Function. Mathematical Problems of Computer Science, 31, 60–72. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/392