Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

The University of British Columbia

$50,000.00

Topics in Symbolic Dynamics on the Interface with Information Theory, Ergodic Theory and Statistical Physics

FY 2023-24

Summary
Information is transmitted over noisy channels in many settings: cell phones, deep space probes, computer networks, data storage devices, etc. A major problem is that the transmitted information is distorted by various sources of noise, some random and some deterministic. In information theory, a channel is a mathematical model of the transmission of information (such as broadcast by a radio station), reception of the information (such as reception by a radio) and a precise description of the noise. The capacity Cap of a channel is the maximum rate at which information can be transmitted faithfully through the channel, i.e., with arbitrarily small probability of error. Computation of the exact capacity is very difficult, and in some cases impossible, for all but the simplest channels. An added complication is that some channels are input-constrained, meaning that there is a constraint on the allowed sequences that can be transmitted through the channel. We are particularly interested in the case of input-constrained channels. Even in cases where the noise model and description of the input constraint are very simple, the channel is surprisingly complicated, and computation of the channel capacity is very difficult. The k-th order capacity Cap_k is the maximum rate at which a Markov chain of memory k can be transmitted faithfully through the channel. The sequence Cap_1, Cap_2, . . . is an increasing sequence of lower bounds that converges to C. In earlier work, we developed algorithms for rigorously approximating Cap_k for special channels. We focus on the case of input-constrained deterministic channels. Here, information is transmitted with a fixed distortion, depending on the input, instead of random noise. In this special case it is easy to compute Cap, but not so easy to compute Cap_k. A major part of our program is the problem of determining for each input-constrained deterministic channel when Markov capacity achieves capacity, i.e., Cap= Cap_k for some k.  When this happens, we obtain a simple description, namely a Markov chain, of the input process that achieves capacity. To solve this problem, we turn to symbolic dynamics. For a special class of input-constrained deterministic channels, we have a complete checkable necessary and sufficient symbolic dynamics condition that guarantees that Markov capacity achieves capacity. A central problem in this program is to prove the converse, that is if Markov capacity achieves capacity, does the symbolic dynamics condition hold? In another program, we propose to solve a generalization of the road colouring theorem, a major graph-theoretic result that first arose in ergodic theory.  Finally, we propose to continue our program on Gibbs measures and equilibrium measures and, in particular, characterize when the information function of a Gibbs measure is continuous; this is of substantial interest in statistical physics.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-04495
Name nom
Marcus, Brian
Department département
Mathematics
Organization id
2
Institution établissement
The University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
50000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1510
Committee name en
Electrical and Computer Engineering
Committee name fr
Génie électrique et informatique
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2507
Research subject group en
Electrical and electronic engineering
Research subject group fr
Communications systems
Research subject en
Génie électrique et électronique
Research subject fr
Systèmes de télécommunications
Application title
Topics in Symbolic Dynamics on the Interface with Information Theory, Ergodic Theory and Statistical Physics
Keyword
channel capacity; directed graph; entropy; factor map; Gibbs measure; g measure; Markov chain; road colouring problem; shift of finite type; topological pressure
Application summary
Information is transmitted over noisy channels in many settings: cell phones, deep space probes, computer networks, data storage devices, etc. A major problem is that the transmitted information is distorted by various sources of noise, some random and some deterministic. In information theory, a channel is a mathematical model of the transmission of information (such as broadcast by a radio station), reception of the information (such as reception by a radio) and a precise description of the noise. The capacity Cap of a channel is the maximum rate at which information can be transmitted faithfully through the channel, i.e., with arbitrarily small probability of error. Computation of the exact capacity is very difficult, and in some cases impossible, for all but the simplest channels. An added complication is that some channels are input-constrained, meaning that there is a constraint on the allowed sequences that can be transmitted through the channel. We are particularly interested in the case of input-constrained channels. Even in cases where the noise model and description of the input constraint are very simple, the channel is surprisingly complicated, and computation of the channel capacity is very difficult. The k-th order capacity Cap_k is the maximum rate at which a Markov chain of memory k can be transmitted faithfully through the channel. The sequence Cap_1, Cap_2, . . . is an increasing sequence of lower bounds that converges to C. In earlier work, we developed algorithms for rigorously approximating Cap_k for special channels. We focus on the case of input-constrained deterministic channels. Here, information is transmitted with a fixed distortion, depending on the input, instead of random noise. In this special case it is easy to compute Cap, but not so easy to compute Cap_k. A major part of our program is the problem of determining for each input-constrained deterministic channel when Markov capacity achieves capacity, i.e., Cap= Cap_k for some k.  When this happens, we obtain a simple description, namely a Markov chain, of the input process that achieves capacity. To solve this problem, we turn to symbolic dynamics. For a special class of input-constrained deterministic channels, we have a complete checkable necessary and sufficient symbolic dynamics condition that guarantees that Markov capacity achieves capacity. A central problem in this program is to prove the converse, that is if Markov capacity achieves capacity, does the symbolic dynamics condition hold? In another program, we propose to solve a generalization of the road colouring theorem, a major graph-theoretic result that first arose in ergodic theory.  Finally, we propose to continue our program on Gibbs measures and equilibrium measures and, in particular, characterize when the information function of a Gibbs measure is continuous; this is of substantial interest in statistical physics.
The University of British Columbia - $50,000 Grant (2… | Canada Spends