Near-optimal Sampling to Optimize Communication Over Discrete Memoryless Channels

Abstract

This paper develops a strategy to minimize the number of channel probes required to recover the components of the channel law and maximize the reliable communication rate across a discrete memoryless channel (DMC). Based on the aggregate set of observed input-output pairs over time, the algorithm sequentially probes subsets of channel input values. We leverage a non-asymptotic probably approximately correct (PAC) bounds to establish the rate of convergence towards channel capacity as O(√log(log(N)) log(N)/N), where N is the number of channel probes. For a discrete channel with |X| input values and |Y| output values, the sampling strategy may reduce the sample complexity by a factor of nearly min (|X|/|Y|,1) relative to previous methods.