Computability of entropy and pressure for Markov systems

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

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.