Computability of entropy and pressure for Markov systems

马尔可夫系统的熵和压力的可计算性

• 批准号: RGPIN-2017-04550
• 负责人: Marcus, Brian
• 金额: $ 2.04万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711125
• 关键词: Computability; entropy; pressure; Markov; systems

The concept of entropy is central to many areas of modern science and technology. Entropy is a quantitative measure of information content of a corpus of data or a statistical process. It is also used as a primary component in the computation of channel capacity, which is the optimal rate at which data can be transmitted over a communication channel, such as a network of cellular phones or computers, or stored in a data recording device, such as a computer disk drive or DVD. For some channels and devices, in order to improve reliability, it is necessary to restrict the sequences that can be transmitted or stored. This motivated the concept of an input-constrained channel. The capacity of such a channel determines the optimal data rate and in many cases is characterized in terms of optimal entropies of processes known as hidden Markov processes (HMPs). There is no known general formula for the entropy of an HMP. In Part I of this proposal we seek to develop methods to prove existence of efficient schemes to approximate entropies of HMPs and capacity of input-constrained channels. The capacity of an input-constrained channel incorporates the information content of the set of input-constrained sequences itself as well as the noise inherent in the channel. The former is quantified by the so-called noiseless capacity. Sets of constrained input sequences are of a type nearly identical to those used in the theory of dynamical systems to model chaotic systems. In dynamical systems, these sets are known as shifts of finite type (SFTs), and in this setting noiseless capacity is known as topological entropy of the SFT. There is an explicit, general and extremely useful formula known for the topological entropy of an SFT. Input constraints arise in two dimensions as well as one dimension, i.e., arrays instead of sequences, in applications such as holographic recording. There is a corresponding notion of SFT and topological entropy. In contrast to one dimension, there is no general formula for this entropy in two dimensions. However, the topological entropies of some two-dimensional SFTs can be approximated efficiently. In Part II of this proposal, we focus on methods of proving existence of efficient approximation schemes to compute topological entropy for certain two-dimensional SFTs. The methods make use of a representation of topological entropy in terms of a maximal entropy statistical process compatible with the SFT. In this way, under certain conditions, the topological entropy can be expressed as an average of a function of a few samples of this process, each of which can be computed efficiently. The methods naturally generalize to efficient approximation of the so-called topological pressure of interactions that are of interest in statistical physics, in particular for such classical models as the Ising model and hard core model.

熵的概念是现代科学和技术的许多领域的核心。熵是数据或统计过程的语料库的信息内容的定量度量。它也被用作计算信道容量的主要组成部分，信道容量是数据可以通过通信信道（如蜂窝电话或计算机网络）传输或存储在数据记录设备（如计算机磁盘驱动器或DVD）中的最佳速率。 对于某些信道和设备，为了提高可靠性，有必要限制可以传输或存储的序列。 这激发了输入受限渠道的概念。 这种信道的容量决定了最佳数据速率，并且在许多情况下，其特征在于被称为隐马尔可夫过程（HMP）的过程的最佳熵。HMP的熵没有已知的通用公式。在本提案的第一部分中，我们寻求开发方法来证明存在有效的方案，以近似熵的HMP和输入受限的信道的容量。 输入受限信道的容量包含输入受限序列本身的集合的信息内容以及信道中固有的噪声。 前者由所谓的无噪声容量量化。 约束输入序列集的类型几乎与动力系统理论中用来模拟混沌系统的那些类型相同。 在动力系统中，这些集合被称为有限型移位（SFT），在这种情况下，无噪声容量被称为SFT的拓扑熵。 有一个明确的，一般的和非常有用的公式已知的拓扑熵的SFT。 输入约束出现在二维和一维中，即，阵列而不是序列，在应用中，如全息记录。 有一个相应的概念SFT和拓扑熵。 与一维相反，二维中的熵没有通用公式。 然而，一些二维SFT的拓扑熵可以有效地近似。 在本建议的第二部分，我们专注于证明有效的近似方案的存在性，以计算某些二维SFT的拓扑熵的方法。该方法利用与SFT兼容的最大熵统计过程中的拓扑熵的表示。 这样，在某些条件下，拓扑熵可以表示为该过程的几个样本的函数的平均值，每个样本都可以有效地计算。这些方法自然地推广到统计物理中感兴趣的所谓的相互作用的拓扑压力的有效近似，特别是对于诸如伊辛模型和硬核模型的经典模型。