Rate-Reliability Tradeoff for Deterministic Identification

We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>, controlled by reliability exponents <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$E_{1}, E_{2}&gt;0$</tex>. We find that, in contrast to the case of slowly vanishing errors where the identifiable message length scales as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Theta(n \log n)$</tex>, here linear scaling is restored, now as a function of the reliability exponents. We give upper and lower bounds on the ensuing ratereliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$E_{1}, E_{2}&gt;0$</tex> are bounded below and above in terms of the product of the Minkowski dimension and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log \min \left\{E_{1}, E_{2}\right\}$</tex>. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms.