Identification Over Noisy Permutation Channels

Abstract

We study message identification over the noisy permutation channel. For discrete memoryless channels (DMCs), the number of identifiable messages grows doubly exponentially, and the maximum second-order exponent is same as the Shannon capacity of the DMC. We consider a $q$-ary noisy permutation channel where the transmitted vector is first permuted by a permutation chosen uniformly at random, and then passed through a DMC with strictly positive entries in its transition probability matrix $U$. In an earlier work, we showed that over $q$-ary noiseless permutation channel, $2^{c_n{n}^{q-1}}$ messages can be identified if $c_n\to 0$, and a strong converse holds for $2^{c_n{n}^{q-1}}$ messages if $c_n\to \infty$. For the $q$-ary noisy permutation channel, we show that message sizes growing as $2^{R_n{\left(\frac{n}{\log n}\right)}^{(r-1)/2}}$, where $r$ be the rank of $U$, are identifiable for any $R_n\to 0$. We also prove a strong converse result showing that for any sequence of identification codes with $$2^{\left(R_n{n}^{(q-1)/2}(\log n{)}^{1+\frac{(q-1)(q-2)}{2}}\right)},$$ messages, where $R_n\to \infty$, the sum of Type-I and Type-II error probabilities approaches at least $1$ as $n\to \infty$. Our converse proof uses the idea of channel resolvability. We propose a novel deterministic quantization scheme for quantization of a distribution over the set of all compositions/types by an $M$-type input distribution when the distortion is measured on the output distribution in total variation distance. This plays a key role in the converse proof. We have also studied identification with deterministic encoder and decoder, and proved tight achievability, weak converse, and strong converse.

52 pages