  In this paper, we formally define and analyze the class of noisy permutation
channels. The noisy permutation channel model constitutes a standard discrete
memoryless channel (DMC) followed by an independent random permutation that
reorders the output codeword of the DMC. While coding theoretic aspects of this
model have been studied extensively, particularly in the context of reliable
communication in network settings where packets undergo transpositions, and
closely related models of DNA based storage systems have also been analyzed
recently, we initiate an information theoretic study of this model by defining
an appropriate notion of noisy permutation channel capacity. Specifically, on
the achievability front, we prove a lower bound on the noisy permutation
channel capacity of any DMC in terms of the rank of the stochastic matrix of
the DMC. On the converse front, we establish two upper bounds on the noisy
permutation channel capacity of any DMC whose stochastic matrix is strictly
positive (entry-wise). Together, these bounds yield coding theorems that
characterize the noisy permutation channel capacities of every strictly
positive and "full rank" DMC, and our achievability proof yields a conceptually
simple, computationally efficient, and capacity achieving coding scheme for
such DMCs. Furthermore, we also demonstrate the relation between the output
degradation preorder over channels and noisy permutation channel capacity. In
fact, the proof of one of our converse bounds exploits a degradation result
that constructs a symmetric channel for any DMC such that the DMC is a degraded
version of the symmetric channel. Finally, we illustrate some examples such as
the special cases of binary symmetric channels and (general) erasure channels.
Somewhat surprisingly, our results suggest that noisy permutation channel
capacities are generally quite agnostic to the parameters that define the DMCs.
