Finite-Blocklength Analysis for Noisy Permutation Channels
Provides the first finite-blocklength analysis for noisy permutation channels with lower-dimensional output polytopes, advancing information-theoretic understanding for this channel model.
The paper derives finite-blocklength achievability and converse bounds for noisy permutation channels, showing that the strong converse term scales with the affine dimension of the reachable output polytope (d log sqrt(n)), and the achievability bound is refined via a geometric reduction to d(d+1) one-dimensional events.
We study finite-blocklength bounds for noisy permutation channels whose reachable output polytope may be lower-dimensional than the output simplex. Existing Gaussian achievability analyses focus on strictly positive full-rank square DMC transition matrices. The capacity result for arbitrary strictly positive DMCs is established through a weak converse, while available strong converse bounds in the lower-dimensional setting can scale with the dimension of the output simplex rather than with that of the reachable output polytope. On the achievability side, messages are placed on a simplex lattice in affine coordinates, and decoding is performed by projecting the empirical output distribution onto the reachable affine hull followed by Euclidean nearest-neighbor decoding. Writing $d$ for the affine dimension of the reachable output polytope, a geometric reduction converts decoding errors into $d(d+1)$ one-dimensional transfer events, yielding a refined Gaussian achievability lower bound based on averaged local coordinate variances and a relative volume ratio. On the converse side, a modified meta-converse, a Kullback--Leibler divergence covering, and a local binary-testing bound yield a strong converse whose blocklength-dependent term is $d\log\sqrt n$, up to a bounded additive remainder.