  Suppose a string $X_1^n=(X_1,X_2,...,X_n)$ generated by a memoryless source
$(X_n)_{n\geq 1}$ with distribution $P$ is to be compressed with distortion no
greater than $D\geq 0$, using a memoryless random codebook with distribution
$Q$. The compression performance is determined by the ``generalized asymptotic
equipartition property'' (AEP), which states that the probability of finding a
$D$-close match between $X_1^n$ and any given codeword $Y_1^n$, is
approximately $2^{-n R(P,Q,D)}$, where the rate function $R(P,Q,D)$ can be
expressed as an infimum of relative entropies. The main purpose here is to
remove various restrictive assumptions on the validity of this result that have
appeared in the recent literature. Necessary and sufficient conditions for the
generalized AEP are provided in the general setting of abstract alphabets and
unbounded distortion measures. All possible distortion levels $D\geq 0$ are
considered; the source $(X_n)_{n\geq 1}$ can be stationary and ergodic; and the
codebook distribution can have memory. Moreover, the behavior of the matching
probability is precisely characterized, even when the generalized AEP is not
valid. Natural characterizations of the rate function $R(P,Q,D)$ are
established under equally general conditions.
