2
$\begingroup$

I'm currently studying Information Theory from Csiszar and Korner, "Information Theory: Coding theorems for Discrete Memoryless Sources". There are several questions pertaining to the set of all probability measures on the underlying space. I figured if I prove the following lemma, it will make things easier:

Let $\mathcal{X}$ be a finite set. Let $\mathcal{P}=\mathcal{P}(\mathcal{X})$ be the set of all probability measures that can be defined on $\mathcal{X}$. Under the total variation metric i.e. for any two measures $P,Q \in \mathcal{P}$ $$d_{TV}(P,Q) := \sum_{x \in \mathcal{X}}|P(x)-Q(x)|$$

Prove that $(\mathcal{P},d_{TV})$ is compact.

I'm actually looking for a simple proof of this. For instance, I wanted to use the result that a metric space is compact iff it is complete and totally bounded. Completeness was easy as I could just use the completeness of $\mathbb{R}$ in a pointwise fashion and show the pointwise limit is a measure. Finiteness of $\mathcal{X}$ helps greatly here.

So all that is left is Totally Boundedness. Unfortunately, while I did start by assuming an $\epsilon$-cover of $\mathcal{P}$, I could not find a way to pick finitely many that would cover the whole space. I'm sure that finiteness of $\mathcal{X}$ would help here as well.

The other idea, in fact the property I wanted to use, was to show sequential compactness since this is equivalent to compactness. But even here I'm not sure how to go about things.

Kindly help me in this regard in the form of subtle hints and tips. If I get it, I'll post my solution and credit the most helpful hint.

Update: It turns out I could use the fact that $\mathcal{P}$ is convex. Since any measure is a convex combination of degenerate distributions... Could I use this I wonder?

$\endgroup$
2
$\begingroup$

When $X$ is finite, you can treat $\mathcal P$ as a subset of $\Bbb R^X$. Total variation is the norm there, and all the norms over finite-dimensional spaces are equivalent, so the induced metric is equivalent to the Eucledian one. Embedded $\mathcal P$ is bounded and closed in Eucledian metric, hence compact.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is also a very good and simple proof... probably simpler than mine. Thanks. $\endgroup$ – Gautam Shenoy Nov 25 '15 at 4:38
1
$\begingroup$

Ok. I got it. The Lemma is true. Given a sequence of probability measures $P_n$, we consider $P_n(x)$ for every $x \in \mathcal{X}$. Using Weierstrass Bolzano theorem, noting that $P_n(x)$ is a bounded sequence of real numbers, there exists a convergent subsequence. We do this iteratively: WLOG, assume $\mathcal{X} = \{1,2,...,N\}$.

Step $1$: Find a convergent subsequence in $P_n(1)$. Let the limit be $\hat{P}(1)$. Note that the measures are applied to $1$ here.

Step $2$: For $i \geq 2$, repeat step $1$ but for the subsequence obtained in step $i-1$ and the measure applied to $i$. Stop after step $N$.

Thus we get a final subsequence, $P_{n_{k}}$ which converges in Total Variation to $\hat{P}$. To see that $\hat{P}$ is a prob measure, firstly $\hat{P}(x) \in[0,1]$ for every $x$. Also we have $$\sum_{x \in \mathcal{X}} \hat{P}(x) = \sum_{x \in \mathcal{X}} \lim_{k \to \infty} P_{n_k}(x) = \lim_{k \to \infty} \sum_{x \in \mathcal{X}} P_{n_k}(x)=1$$

Thus $\hat{P}$ is a valid prob. measure and hence $\hat{P} \in \mathcal{P}$.

Thus $\mathcal{P}$ is sequentially compact and hence is compact as it is a metric space. $\blacksquare$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.