 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-224/1/a/solution

P, Q

β_{n} = Q^{\otimes n} (B_{n})

α_{n} = P^{\otimes n} (B_{n}^{c})

is eventually at most any fixed

ϵ \in (0, 1)

lim_{n \to \infty} - \frac{1}{n} lo g_{2} β_{n} = D (P ∥ Q) .

For the direct part, define the information-density typical region

B_{n} = {x_{1}^{n} : \frac{1}{n} lo g_{2} \frac{P ^{\otimes n} ( x _{1}^{n} )}{Q ^{\otimes n} ( x _{1}^{n} )} \geq D (P ∥ Q) - δ} .

P

gives

α_{n} \to 0

, while

β_{n} = x_{1}^{n} \in B_{n} \sum Q^{\otimes n} (x_{1}^{n}) \leq 2^{- n {D (P ∥ Q) - δ}} x_{1}^{n} \in B_{n} \sum P^{\otimes n} (x_{1}^{n}) \leq 2^{- n {D (P ∥ Q) - δ}} .

For the converse, let

C_{n} = {x_{1}^{n} : \frac{1}{n} lo g_{2} \frac{P ^{\otimes n} ( x _{1}^{n} )}{Q ^{\otimes n} ( x _{1}^{n} )} \leq D (P ∥ Q) + δ} .

Again

P^{\otimes n} (C_{n}) \to 1

. Any test with

P^{\otimes n} (B_{n}) \geq 1 - ϵ

satisfies

P^{\otimes n} (B_{n} \cap C_{n}) \geq 1 - ϵ - o (1) .

C_{n}

Q^{\otimes n} \geq 2^{- n (D + δ)} P^{\otimes n}

, hence

β_{n} \geq 2^{- n (D + δ)} {1 - ϵ - o (1)} .

Thus

lim sup_{n} - n^{- 1} lo g_{2} β_{n} \leq D + δ

. Letting

δ ↓ 0

proves optimality.

 New to topics? Read the docs here!