Non-existence of a certain finite-letter mutual information characterizations for time-invariant Markoff channels
dr. Mukul Agarwal
We provide a rigorous definition of a certain kind of characterization for capacity region of a family of Markoff channels which is based on optimization problems resulting out of calculating conditional mutual informations from a finite number of random variables, and by constraining these random variables in a certain way. This definition is motivated by the definition of single-letter characterizations in information theory. For a Markoff channel, we prove that approximating the solution to these characterizations within an additive constant is a computable problem. Based on previous undecidability results concerning capacities of finite state machine channels (FSMCs) belonging to a certain set, it will follow that there exists an example of a family of FSMCs for which given such a characterization based on conditional mutual informations based on a finite number of random variables and constraints, this characterization cannot represent the capacity of this family of FSMCs.