  A packing lemma is proved using a setting where the channel is a binary-input
discrete memoryless channel $(\mathcal{X},w(y|x),\mathcal{Y})$, the code is
selected at random subject to parity-check constraints, and the decoder is a
joint typicality decoder. The ensemble is characterized by (i) a pair of fixed
parameters $(H,q)$ where $H$ is a parity-check matrix and $q$ is a channel
input distribution and (ii) a random parameter $S$ representing the desired
parity values. For a code of length $n$, the constraint is sampled from $p_S(s)
= \sum_{x^n\in {\mathcal{X}}^n} \phi(s,x^n)q^n(x^n)$ where $\phi(s,x^n)$ is the
indicator function of event $\{s = x^n H^T\}$ and $q^n(x^n) =
\prod_{i=1}^nq(x_i)$. Given $S=s$, the codewords are chosen conditionally
independently from $p_{X^n|S}(x^n|s) \propto \phi(s,x^n) q^n(x^n)$. It is shown
that the probability of error for this ensemble decreases exponentially in $n$
provided the rate $R$ is kept bounded away from $I(X;Y)-\frac{1}{n}I(S;Y^n)$
with $(X,Y)\sim q(x)w(y|x)$ and $(S,Y^n)\sim p_S(s)\sum_{x^n} p_{X^n|S}(x^n|s)
\prod_{i=1}^{n} w(y_i|x_i)$. In the special case where $H$ is the parity-check
matrix of a standard polar code, it is shown that the rate penalty
$\frac{1}{n}I(S;Y^n)$ vanishes as $n$ increases. The paper also discusses the
relation between ordinary polar codes and random codes based on polar
parity-check matrices.
