Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
added 39 characters in body
Source Link
Davide Giraudo
  • 4k
  • 2
  • 30
  • 42

I read about the Conditional Limit Theorem from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, second edition, page 371. I can't understand the last inference in the proof of the theorem.

The theorem is formulated as follows: Let $E$ be a closed convex subset of probability distributions and let $Q$ be a distribution not in $E$. Let $X_1,X_2,\dots,X_n$ be discrete random variables drawn i.i.d ~ $Q$. Let $P^*$ achieve $min_{P \in E}D(P||Q)$$\min_{P \in E}D(P||Q)$. Then: $$Pr(X_1 = a \big\vert P_{X^n} \in E) \rightarrow P^*(a)$$$$\mathrm{Pr}\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$$ in probability, as $n \rightarrow \infty$.

Note: In the formulation above, $P_{X^n}$ means the "type" of the sequence $X^n = (X_1,X_2,\dots,X_n)$.

The end of the proof contains the following statement:

Thus, $Pr\left(\left|P_{X^n}(a) - P^*(a)\right| \geq \epsilon \big\vert P_{X^n} \in E\right) \rightarrow 0$$\mathrm{Pr}\left(\left|P_{X^n}(a) - P^*(a)\right| \geq \epsilon \big\vert P_{X^n} \in E\right) \rightarrow 0$ as $n \rightarrow \infty$ (Here |.| is used to denote $L_1$ distance). Alternatively, this can be written as $Pr\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$$\mathrm{Pr}\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$ in probability, $a \in \chi$.

I don't understand how to conclude this last inference (in bold).

I read about the Conditional Limit Theorem from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, second edition, page 371. I can't understand the last inference in the proof of the theorem.

The theorem is formulated as follows: Let $E$ be a closed convex subset of probability distributions and let $Q$ be a distribution not in $E$. Let $X_1,X_2,\dots,X_n$ be discrete random variables drawn i.i.d ~ $Q$. Let $P^*$ achieve $min_{P \in E}D(P||Q)$. Then: $$Pr(X_1 = a \big\vert P_{X^n} \in E) \rightarrow P^*(a)$$ in probability, as $n \rightarrow \infty$.

Note: In the formulation above, $P_{X^n}$ means the "type" of the sequence $X^n = (X_1,X_2,\dots,X_n)$.

The end of the proof contains the following statement:

Thus, $Pr\left(\left|P_{X^n}(a) - P^*(a)\right| \geq \epsilon \big\vert P_{X^n} \in E\right) \rightarrow 0$ as $n \rightarrow \infty$ (Here |.| is used to denote $L_1$ distance). Alternatively, this can be written as $Pr\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$ in probability, $a \in \chi$.

I don't understand how to conclude this last inference (in bold).

I read about the Conditional Limit Theorem from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, second edition, page 371. I can't understand the last inference in the proof of the theorem.

The theorem is formulated as follows: Let $E$ be a closed convex subset of probability distributions and let $Q$ be a distribution not in $E$. Let $X_1,X_2,\dots,X_n$ be discrete random variables drawn i.i.d ~ $Q$. Let $P^*$ achieve $\min_{P \in E}D(P||Q)$. Then: $$\mathrm{Pr}\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$$ in probability, as $n \rightarrow \infty$.

Note: In the formulation above, $P_{X^n}$ means the "type" of the sequence $X^n = (X_1,X_2,\dots,X_n)$.

The end of the proof contains the following statement:

Thus, $\mathrm{Pr}\left(\left|P_{X^n}(a) - P^*(a)\right| \geq \epsilon \big\vert P_{X^n} \in E\right) \rightarrow 0$ as $n \rightarrow \infty$ (Here |.| is used to denote $L_1$ distance). Alternatively, this can be written as $\mathrm{Pr}\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$ in probability, $a \in \chi$.

I don't understand how to conclude this last inference (in bold).

Source Link
real
  • 323
  • 1
  • 9

Last Inference in proof of conditional limit theorem

I read about the Conditional Limit Theorem from the book "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, second edition, page 371. I can't understand the last inference in the proof of the theorem.

The theorem is formulated as follows: Let $E$ be a closed convex subset of probability distributions and let $Q$ be a distribution not in $E$. Let $X_1,X_2,\dots,X_n$ be discrete random variables drawn i.i.d ~ $Q$. Let $P^*$ achieve $min_{P \in E}D(P||Q)$. Then: $$Pr(X_1 = a \big\vert P_{X^n} \in E) \rightarrow P^*(a)$$ in probability, as $n \rightarrow \infty$.

Note: In the formulation above, $P_{X^n}$ means the "type" of the sequence $X^n = (X_1,X_2,\dots,X_n)$.

The end of the proof contains the following statement:

Thus, $Pr\left(\left|P_{X^n}(a) - P^*(a)\right| \geq \epsilon \big\vert P_{X^n} \in E\right) \rightarrow 0$ as $n \rightarrow \infty$ (Here |.| is used to denote $L_1$ distance). Alternatively, this can be written as $Pr\left(X_1 = a \big\vert P_{X^n} \in E\right) \rightarrow P^*(a)$ in probability, $a \in \chi$.

I don't understand how to conclude this last inference (in bold).