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