权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

一种转移矩阵转移概率和特征值的辨识算法

基本信息

批准号：
11554004
负责人：
KOHDA Tohru
金额：
$ 4.03万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2001
项目状态：
已结题

项目摘要

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.

马尔可夫信息源在将待研究的主题建模为随机过程中起着重要作用，例如，分组密码、语音识别、DNA中人类基因的识别以及著名的香农通信系统模型。本研究的主要目的是研究如何通过观察一个具有转移矩阵P的马尔可夫信源产生的符号序列来识别该信源。通过<ij>使用长度为2的可能字符串的N^2个直方图来直接估计P中的所有元素p_i（i，j=1，.，N）是很自然的。然而，如果状态数N变大，则该方法需要太多的直方图。由于马尔可夫源产生的序列的统计量主要由P的特征值决定，识别源的简单方法之一是估计P的特征值。在这项研究中，我们给出了一个简单的方法来确定要观察的符号序列，这些符号序列给出了数量为N的直方图。此外，我们推导出一个非对称Toeplitz系统（或称为Wiener-Hopf方程），在线性方程的形式，其系数矩阵和常数的直方图的均值和方差的函数。数值模拟结果表明，该方法对2-状态马尔可夫链的辨识是成功的，而对3-状态马尔可夫链的辨识则是失败的。由此得出结论，基于最小直方图数的算法还需要进一步的研究和解决。