Let $S$ be a finite set, for simplicity assume $S=\{1,2,...,m\}$. Let $f_0$ and $f_1$ be two non-equal probabilities defined on $S$, with $f_0(j)=P_0(X=j)$ and $f_1(j)=P_1(X=j)$, such that $f_0(j)\geq0,f_1(j)\geq0,\sum_{j\in S}f_0(j)=1,\sum_{j\in S}f_1(j)=1$ for every $j\in S$.

Let $X_1,X_2,...,X_n$ be an iid random sample with support $S$. Define:$$Z_n=\prod_{k=1}^n\dfrac{f_1(X_k)}{f_0(X_k)}$$

Show that $Z_n\to0$ almost surely.

I defined $N_n(j)=\sum_{k=1}^n1_{\{X_k=j\}}$ and observed that $Y_n:=\log Z_n=\sum_{j\in S}N_n(j)\log\left(\dfrac{f_1(j)}{f_0(j)}\right)$.

I want to show that $Y_n\to-\infty$ almost surely. I know that $E_0\left(\log\left(\dfrac{f_1(X)}{f_0(X)}\right)\right)<0$ as $f_1\neq f_0$ (by Jensen's Inequality).

Now, $$Y_n=n\sum_{j\in S}\dfrac{N_n(j)}{n}\log\left(\dfrac{f_1(j)}{f_0(j)}\right)$$

Under $f_0$ we have by SLLN, $$\dfrac{N_n(j)}{n}\to f_0(j)$$ almost surely. Hence $$\sum_{j\in S}\dfrac{N_n(j)}{n}\log\left(\dfrac{f_1(j)}{f_0(j)}\right)\to \sum_{j\in S}f_0(j)\log\left(\dfrac{f_1(j)}{f_0(j)}\right)=E_0\left(\log\left(\dfrac{f_1(X)}{f_0(X)}\right)\right)<0$$ and therefore, almost surely,$$\lim_{n\to\infty}Y_n=\lim_{n\to\infty}nE_0\left(\log\left(\dfrac{f_1(X)}{f_0(X)}\right)\right)=-\infty$$ showing that $$Y_n\to-\infty$$ almost surely from which it follows that $$Z_n\to0$$ almost surely.

Is my method correct?

  • $\begingroup$ For a much shorter solution, apply the SLLN to the i.i.d. sequence $(U_n)$ defined by $$U_n=\log f_1(X_n)/f_0(X_n).$$ And please specify the probability measure with respect to which the almost sure statement must be proven. $\endgroup$
    – Did
    Aug 23, 2015 at 7:37
  • $\begingroup$ I understand that while saying "a.s. convergence", the prob. space becomes very important. However, this is an exercise problem from a book where the prob. space wasn't defined. $\endgroup$ Aug 23, 2015 at 7:51
  • $\begingroup$ I thought initially to approach the problem in the way you said, @Did. However, I did not understand under which probability $P_1$ or $P_0$, I should apply the SLLN. Because in SLLN, we have to compute expectation, and that can be done under a particular probability only, isn't it? $\endgroup$ Aug 23, 2015 at 7:56
  • $\begingroup$ ?? Naturally the almost sure convergence to zero occurs with respect to one of the probability measures $P_0$ or $P_1$ but not with respect to the other. $\endgroup$
    – Did
    Aug 23, 2015 at 8:56
  • $\begingroup$ You may be right. But how can one be so sure? Here nothing is mentioned about either of the probabilities. $\endgroup$ Aug 23, 2015 at 9:19

1 Answer 1


Sorry for swapping the variables here but here is my proof

Let $Z_n = \prod^n_i \frac{p(x)}{q(x)}$. Consider the quantity $$W_n = \frac{1}{n}log(Z_n) = \frac{1}{n}\sum_i^n log(\frac{p(x)}{q(x)})$$ By Strong Law of Large Numbers, $$\lim_{n \rightarrow \infty} W_n = E_{q(x)}[log(\frac{p(x)}{q(x)})] = \int_\mathcal{X} log(\frac{p(x)}{q(x)})q(x)dx$$

Since $log(a) < a-1 \ \forall a > 0 $ $ a \neq 1$ and that $\frac{p(x)}{q(x)} > 0$, $p(x) \neq q(x)$

$$W_n \rightarrow \int_\mathcal{X} log(\frac{p(x)}{q(x)})q(x)dx < \int_\mathcal{X} (\frac{p(x)}{q(x)} - 1)q(x)dx = \int_\mathcal{X} p(x)dx - \int_\mathcal{X} q(x)dx = 1 - 1 = 0$$ This gives us $$\lim_{n \rightarrow \infty} W_n < 0 \implies \lim_{n \rightarrow \infty} \frac{1}{n}log(Z_n) < 0 \implies \lim_{n \rightarrow \infty} n \cdot \frac{1}{n}log(Z_n) = -\infty \\ \implies \lim_{n \rightarrow \infty} log(Z_n) = -\infty \\ \implies \lim_{n \rightarrow \infty} Z_n = 0 \ \blacksquare$$


You must log in to answer this question.

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