New Upper Bounds for Noisy Permutation Channels
<|reference_start|>New Upper Bounds for Noisy Permutation Channels: The noisy permutation channel is a useful abstraction introduced by Makur for point-to-point communication networks and biological storage. While the asymptotic capacity results exist for this model, the characterization of the second-order asymptotics is not available. Therefore, we analyze the converse bounds for the noisy permutation channel in the finite blocklength regime. To do this, we present a modified minimax meta-converse for noisy permutation channels by symbol relaxation. To derive the second-order asymptotics of the converse bound, we propose a way to use divergence covering in analysis. It enables the observation of the second-order asymptotics and the strong converse via Berry-Esseen type bounds. These two conclusions hold for noisy permutation channels with strictly positive matrices (entry-wise). In addition, we obtain computable bounds for the noisy permutation channel with the binary symmetric channel (BSC), including the original computable converse bound based on the modified minimax meta-converse, the asymptotic expansion derived from our subset covering technique, and the {\epsilon}-capacity result. We find that a smaller crossover probability provides a higher upper bound for a fixed finite blocklength, although the {\epsilon}-capacity is agnostic to the BSC parameter. Finally, numerical results show that the normal approximation shows remarkable precision, and our new converse bound is stronger than previous bounds.<|reference_end|>
@article{feng2024new,
    title={New Upper Bounds for Noisy Permutation Channels},
    author={Lugaoze Feng, Baoji Wang, Guocheng Lv, Xvnan Li, Luhua Wang, and Ye
  jin},
    journal={arXiv preprint arXiv:2406.15031},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15031},
    primaryClass={cs.IT math.IT}
}