Let $(\Omega,\mathcal{F},P)$ be a probability space, $\{\mathcal{F}_n \subseteq \mathcal{F}\}_{n \in \mathbb{N}}$ an increasing filtration, $S$ a finite set and $X: \Omega \rightarrow S$ a random variable. Denote $\mathcal{P}(\Omega)$ the space of probability measures on $(\Omega, \mathcal{F})$ and assume that $\{Q_n: \Omega \rightarrow \mathcal{P}(\Omega)\}_{n \in \mathbb{N}}$ are regular conditional probabilities corresponding to $\mathcal{F}_n$. That is, for any $A \in \mathcal{F}$, $Q_n(\omega)(A)$ is an $\mathcal{F}_n$-measurable function of $\omega \in \Omega$ and for any $B \in \mathcal{F}_n$

$$\int_B Q_n(\omega)(A) P(d\omega) = P(A \cap B)$$

For each $n \in \mathbb{N}$, define the information gain $I_n: \Omega \rightarrow \mathbb{R} \sqcup \{+\infty\}$ by

$$I_n(\omega):= D_{KL}(X_* Q_{n+1}(\omega) \mid\mid X_* Q_{n}(\omega))$$

Here, $X_*$ denotes push-forward by $X$, i.e. $X_* Q_{n}(\omega)$ is the probability measure on $S$ s.t. for any $A \subseteq S$

$$X_* Q_{n}(\omega)(A) := Q_n(\omega)(X^{-1}(A))$$

$D_{KL}$ is the Kullback–Leibler divergence, i.e. given probability measures $\mu,\nu$ on $S$, regarded as functions from $S$ to $[0,1]$:

$$D_{KL}(\mu \mid\mid \nu) := \sum_{s \in S} \mu(s) \ln{\frac{\mu(s)}{\nu(s)}}$$

Is it true that $\sum_{n=0}^\infty I_n < \infty$ almost surely?

If it helps, consider one or both of the following simplifying assumptions:

  • $\Omega$ is standard.
  • Each $\mathcal{F}_n$ corresponds to a finite partition of $\Omega$ (that becomes finer as $n$ grows).
  • $\begingroup$ Could you, please, remind the definition of $D_{KL}$? I should confess that I'm totally ignorant of this notation and I suspect that I'm not alone :-) Also, do I understand it right that $Q_n(\omega)(A)=\mathcal P(A\cap \{X=X(\omega)\})$ (I'm used to the definitions that require $Q_n:\mathbb N\to \mathcal P(\Omega)$, so I feel a bit confused about the language) $\endgroup$
    – fedja
    May 26, 2017 at 21:28
  • 1
    $\begingroup$ Sorry, I meant $\mathcal P(A\cap \{X=X(\omega)\})/\mathcal P(\{X=X(\omega)\})$, of course. You see now to what extent one can get confused if you use too much of a special language and assume that people understand it ;-). $\endgroup$
    – fedja
    May 26, 2017 at 21:56
  • $\begingroup$ @fedja I totally agree. $D_{KL}$ is easier to decode, it is the KL divergence between two prob. measures. For the push-forward, there are two slightly different definition in probability afaik, so there is definitely such a need to clarify notations. $\endgroup$
    – Henry.L
    May 27, 2017 at 0:52
  • $\begingroup$ @fedja, Henry.L : I added some clarifications, I hope this helps? Please tell me if the question is still unclear. $\endgroup$
    – Vanessa
    May 27, 2017 at 7:43
  • $\begingroup$ @Henry.L I am curious - what are the slightly different definitions of push-forward measures in probability you are referring to? $\endgroup$
    – R W
    May 27, 2017 at 8:35

1 Answer 1


Let me know if I'm talking nonsense but it looks like if you just consider the usual entropy $H(P)=\sum_k P(k)\log P(k)$ for probability measures $P$ on $\mathbb N$, then $$ E[H(X_*Q_{n+1})]-E[H(X_*Q_{n})]= E I_n $$ simply because of the identity $$ p\log p-q\log q=p\log \frac pq+(p-q)\log q $$ (the linear in $p$ part just gets killed by the conditional expectation, as usual). Then the answer is that you are fine as long as the entropy of $X_*\mathcal P$ is finite (which is always the case when you have finite range) but not necessarily if it is not (there is a difference between the finiteness of the expectation and the finiteness a.e., of course, but you said that you have a counterexample for the infinite range yourself, so I'll not elaborate).

Does this make sense?

Edit: a counterexample without finite range requirement.

Let us take $[0,1]$ with the Borel $\sigma$-algebra and the Lebesgue measure for the probability space and the usual dyadic partitions as the filtration. To create the distribution of $X_*P$, just split the integers into chunks of lengths $2^n$, assign some probability $c_n$ to each chunk so that $\sum_n c_n=1$, $\sum_n nc_n=+\infty$. Now we need to construct $X$ itself. Start with the first chunk ($\{0,1}\}$ of length $2$) and assign the conditional probabilities so that $P(0)=2c_1, P(1)=0$ on the left half, the reverse holds on the right half, and the rest is split equally. That gives the information gain $I_1$ of $1\cdot c_1\log 2$ uniformly throughout the whole interval. Now take the second chunk $\{2,3,4,5\}$ and first split so that $2,3$ go to the left and $4,5$ to the right, after which separate them again at the next level. Again, the corresponding gain $I_2+I_3$ will be spread uniformly and equal to $2\cdot c_2\log 2$. Now take care of the third chunk and so on. Note that we do not have $X$ itself yet, but we have the martingales for $P(X=k|\omega\in I)$ for each dyadic $I$ and can lift the sum of gains to any level we want uniformly throughout the interval. The only little problem is that those martingales converge to some fractional values instead of $0,1$, so we do not get true set partitions. To compensate for that, we need to start making slightly non-even partitions now and then allowing the probability of every number whose fate we already decided (in the sense that once we know $I$, we know if it is either present on each further subinterval, or is absent on each further subinterval to spread or squeeze a bit. Just do it rarely enough and only once after you accumulate a uniform gain of $1$. This operation is fairly harmless because all it does to the tails is to multiply them by some positive numbers, which doesn't change the divergence of the series and, thereby, doesn't affect our gain accumulation abilities. However now, from the perspective of each integer, you start running a random walk for its conditional probability, so if your step is, say, half of the distance to the endpoint at least once in a while, then you'll end up with $0$ or $1$ almost surely and full measure will be honestly partitioned.

  • $\begingroup$ You are absolutely right, except that you need $E[H_n] - E[H_{n+1}]$ there because the definition of $H$ has a minus sign that is not present in the definition of $D_{KL}$. $\endgroup$
    – Vanessa
    May 27, 2017 at 10:45
  • $\begingroup$ Only that my counterexample was wrong. In fact, in the countable case you can replace $H(X_* Q_n)$ with $-D_{KL}(X_* Q_n \mid\mid X_* Q_0)$ and it remains to prove that the latter is almost surely bounded below which sounds plausible. Anyway, I reformulated the question to refer only to the finite case so never mind... $\endgroup$
    – Vanessa
    May 27, 2017 at 10:55
  • $\begingroup$ @Squark -Only that my counterexample was wrong- I checked mine, it seems correct. Do you want me to post it? $\endgroup$
    – fedja
    May 27, 2017 at 12:55
  • $\begingroup$ Definitely, I'm intrigued. $\endgroup$
    – Vanessa
    May 27, 2017 at 13:56
  • $\begingroup$ @Squark OK, I'll add it to the answer. Just hold on for a while: I'm a slow typist. $\endgroup$
    – fedja
    May 27, 2017 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .