A PAC-bound on the Channel Capacity of an Observed Discrete Memoryless Channel

Abstract

This paper presents a method to compute the channel capacity of an observed (partially known) discrete memoryless channel (DMC) using a probably approximately correct (PAC) bound. Given N independently and identically distributed (i.i.d.) input-output sample pairs, we define a compound DMC with convex sublevel-sets to constrain the channel output uncertainty with high probability. Then we numerically solve an ‘K-way’ convex optimization to determine an achievable information rate RL(N) across the channel that holds with a specified high probability. Our approach provides the non-asymptotic ‘worst-case’ convergence RL(N) to channel capacity C at the rate of O(√log(log(N))/N) .