Stein's Lemma

Suppose are IID with distribution either or on a discrete alphabet . Suppose where is the Relative Entropy

There are decision regions such that as and for all where

If is any sequence of decision regions such that

then there is some such that

eventually.

Remark

The decision regions above are sufficient to identify asymptotically optimal behaviour but they are not optimal for finite . The optimal tests are given by the Neumann-Pearson Regions

Proof

Suppose are IID . Then the likelihood region

so

…

Set

Then

and hence

Also

Suppose

so but so as So eventually