We have two Bernoulli distributions with success probabilities $\mu_1$ and $\mu_2$. We sample $n$ times from distribution 1 and the sequence we get is $X_1, \ldots, X_n$. Let

$ \hat{kl}_s = \sum_{t=1}^s \ln\frac{\mu_1 X_t + (1-\mu_1)(1-X_t)}{\mu_2 X_t + (1-\mu_2)(1 - X_t)}, $

represent the empirical estimate of KL-divergence between the two probability distributions. Then the following property holds: For any event $A$ in the $\sigma$-algebra generated by $X_1, \ldots, X_n$ the following change of measure identity holds:

\begin{equation} P_2(A) = E_1\left[ I_A \exp(-\hat{kl}_n) \right], \end{equation}

where the subscript $2$ in $P_2$ implies that the probability is based on the distribution 2. Similarly for the expectation. $I$ represents the indicator function. How to prove the above identity?


Shishir, this is quite elementary: write the probability $P_2(\omega)$ of any individual bit sequence $\omega$ as $P_1(\omega) f(\omega)$ where by definition, $f(\omega)=\exp(-\hat{kl}_n)$. Finally, sum over $\omega \in A$.


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.