Capacity of Noisy Permutation Channels
Jennifer Tang, Yury Polyanskiy
Abstract
We establish the capacity of a class of communication channels introduced by Makur. The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> -letter input from a finite alphabet is passed through a discrete memoryless channel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$P_{Z|X}$ </tex-math></inline-formula> and then the output <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> -letter sequence is uniformly permuted. We show that the maximal communication rate (normalized by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log n$ </tex-math></inline-formula> ) equals <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\frac{1}{ 2}} ( \textsf {rank}(P_{Z|X})-1)$ </tex-math></inline-formula> whenever <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$P_{Z|X}$ </tex-math></inline-formula> is strictly positive. This is done by establishing a converse bound matching the achievability of Makur. The two main ingredients of our proof are: 1) a sharp bound on the Kullback-Leibler divergence of a uniformly sampled vector from a type class and observed through a DMC to an iid vector; and 2) the covering <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula> -net of a probability simplex with Kullback-Leibler divergence as a metric. In addition to strictly positive DMC we also find the noisy permutation capacity for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> -ary erasure channels, the Z-channel and others.