Minoration via Mixed Volumes and Cover's Problem for General Channels
share
We propose a method for establishing lower bounds on the supremum of processes in terms of packing numbers by means of mixed-volume inequalities (the Alexandrov-Fenchel inequality). A simple and general bound in terms of packing numbers under the convex distance is derived, from which some known bounds on the Gaussian processes and the Rademacher processes can be recovered when the convex set is taken to be the ball or the hypercube. However, the main thrust for our study of this approach is to handle non-i.i.d. (noncanonical) processes (correspondingly, the convex set is not a product set). As an application, we give a complete solution to an open problem of Thomas Cover in 1987 about the capacity of a relay channel in the general discrete memoryless setting.
READ FULL TEXT