PIMS - UBC Ergodic Theory Seminar: Chengyu Wu

  • Date: 04/03/2023
Chengyu Wu, UBC

University of British Columbia


Markov Capacity for Factor Codes with an Unambiguous Symbol


For a noisy channel, the stationary capacity is the supremum of information rates achievable by stationary input processes.
The Markov capacity of a given order is the supremum of information rates achievable by stationary Markov input processes of the given order. Although Markov capacity asymptotically (as the order increases) achieves stationary capacity under mild assumptions, it is believed that the stationary capacity is not achieved by a finite-order stationary Markov process. In this talk, I will focus on input-constrained deterministic channels, which can be characterized as factor codes defined on subshifts. In this case, a sufficient condition for the stationary capacity to be achieved by a finite-order stationary Markov process is the existence of a subshift of finite type in the domain restricted to which the corresponding code is finite-to-one and onto. I will first give a characterization of this stronger condition for standard factor codes defined on a spoke graph. Then, I will introduce our conjecture that for such a code, the finite-to-one and onto property is indeed equivalent to the existence of a finite-order stationary Markov chain that achieves the capacity of the corresponding deterministic channel. Finally, I will give a necessary and sufficient condition for a more general class of codes to admit a subshift of finite type restricted to which the code is one-to-one and onto. Joint work with Guangyue Han and Brian Marcus.

This event is hybrid (if in person, please wear a mask)

Other Information: 

Location: ESB 4133

Join Zoom Meeting:


Meeting ID: 667 4289 0307

Passcode: 137029