Identification Over Permutation Channels

We study message identification over a noiseless <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-ary uniform permutation channel, where the transmitted vector is permuted by a permutation chosen uniformly at random. The channel is noiseless in the sense that the channel only rearranges the symbols in a different order, without changing the symbol values. For discrete memoryless channels (DMCs), the number of identifiable messages grows doubly exponentially. Identification capacity, the maximum second-order exponent, is known to be the same as the Shannon capacity of the DMC. Permutation channels support reliable communication of only polynomially many messages. A simple achievability result shows that message sizes growing as 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ϵ_<i>n</i><i>n</i>^<i>q</i>−1</sup> are identifiable for any ϵ<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i></sub> → 0. We prove two converse results. A “soft” converse shows that for any <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i> > 0, there is no sequence of identification codes with message size growing as 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>R_n</i>^<i>q</i>−1</sup> with a power-law decay (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−μ</sup>) of the error probability. We also prove a “strong” converse showing that for any sequence of identification codes with message size 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>R</i>_<i>n</i><i>n</i>^<i>q</i>−1</sup>, where R<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i></sub> → ∞, the sum of Type I and Type II error probabilities approaches at least 1 as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> → ∞. To prove the soft converse, we use a sequence of steps to construct a new identification code with a simpler structure which relates to a set system, and then use a lower bound on the normalized maximum pairwise intersection of a set system. To prove the strong converse, we use results on approximation of distributions. The achievability and converse results are generalized to the case of coding over multiple blocks. We also show that under deterministic encoding, the number of messages that can be identified per block is the number of types, i.e., (<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>n</i>+<i>q</i>−1</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i>−1</sub>), and this is same as the message size for reliable communication. We finally study message identification over a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-ary uniform permutation channel in the presence of causal block-wise feedback from the receiver, where the encoder receives an entire <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>-length received block after the transmission of the block is complete. We show that in the presence of feedback, the maximum number of identifiable messages grows doubly exponentially even under deterministic encoding, and we present a two-phase achievability scheme.