On an identification algorithm of transition probabilities and eigenvalues of transition matrix

马尔可夫信息源在将研究对象建模为随机过程中发挥着重要作用，例如分组密码、语音识别、DNA中人类基因的识别以及著名的Shannon通信系统模型。本研究项目的主要目的是研究如何通过仅观察由源生成的符号序列来识别具有转移矩阵$P$的马尔可夫信息源。考虑一个N态简单马尔可夫源，其转移矩阵P取S（1,2，…，N）中的符号。通过使用长度为2的可能字符串的N^2直方图，可以直接估计P中所有元素p_<ij>, （i,j=1，…，N）。然而，如果状态N的数量变大，这种方法需要太多的直方图。由于马尔可夫源产生的序列的统计量主要由P的特征值控制，因此识别源的一种简单方法是估计P的特征值。在本研究中，我们给出了一种简单的方法来确定要观察的符号序列，这些符号序列给出了数目为n的直方图。此外，我们导出了一个线性方程形式的非对称Toeplitz系统（或称为Wiener-Hopf方程）。其系数矩阵和常数是直方图均值和方差的函数。此外，还证明了该线性方程的解可以确定p的特征多项式。数值模拟表明，该方法可以成功地识别出两态马尔可夫链；但是三态的就不是。由此得出结论，基于最小直方图数的算法还需要进一步研究，存在一些问题。

Markov information sources play an important role in modeling subjects to be studied as a stochastic process, e.g., block cipher, speech recognition, recognition of human genes in DNA as well as the well-known Shannon's model of a communication system. The main purpose of this research project is to study how to identify a Markov information source with transition matrix $P$ by only observing a sequence of symbols generated by the source.Consider an N-state simple Markov source with transition matrix P which takes symbols in S (1, 2, …, N). It is natural to estimate directly all the elements p_<ij>, (i,j=1, …, N) in P by using N^2 histograms of possible strings of length 2. This method, however, requires too many histograms if the number of states N becomes large. Since statistics of sequences generated by the Markov sources are primarily governed by eigenvalues of P, one of simple ways to identify the source is to estimate eigenvalues of P.In this research we give a simple method to determine sequences of symbols to be observed which give histograms whose number is in the order of N. Furthermore, we derive a nonsymmetric Toeplitz system (or referred to as the Wiener-Hopf equation), in the linear equation form, whose coefficient matrix and constants are functions of means and variances of the histograms. In addition, the solution of this linear equation is shown to determine a characteristic polynomial of P. Numerical simulations show that the identification of 2-state Markov chains are successful ; but the one of 3-state are not. Thus we get a conclusion that further investigation is needed and problems remain on algorithm based on the minimum number of histograms.