Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation without proving it,and I can not find the proof.

Definition 1 The relative entropy between two probability mass functions $P_{o}\left [ x \right ]$ and $P_{1}\left [ x \right ]$ over the same domain $\mathcal{X}$ is defined as

$D\left ( P_{o}\left [ x \right ]\left | \right |P_{1}\left [ x \right ] \right )=\sum_{x\in \mathcal{X}}^{} P_{0}\left [ x \right ]log\frac{P_{0}\left [ x \right ]}{P_{1}\left [ x \right ]}$.

For $P_{0}$ close to $P_{1}$ the relative entropy can be approximated by its series expansion,

$D\left ( P_{o}\left [ x \right ]\left | \right |P_{1}\left [ x \right ] \right )\approx \frac{1}{2ln2}\sum_{x\in \mathcal{X}}^{}\frac{\left ( P_{o}\left [ x \right ]-P_{1}\left [ x \right ]\right )^{2}}{P_{1}\left [ x \right ]}$.

I want to know why, or where to find the proof. Thanks for you attention.

share|improve this question
    
In which sense is $\approx$ taken here? –  Ashok Mar 25 at 5:34
    
For $P_{0}$ close to $P_{1}$ ? –  ElfPath Mar 25 at 6:57
    
$D(P_{o}[x]\left | \right |P_{1}[ x ])\ge \frac{1}{2ln2}\sum_{x\in \mathcal{X}}(P_{o}(x)-P_{1}(x))^2$ holds in general (source: Cover and Thomas). –  Ashok Mar 25 at 10:35

1 Answer 1

up vote 1 down vote accepted

Just do the math. Let me change notation, call $a_x = P_0[x] $, $b_x=P_1[x] $ and let $e_x=a_x-b_x$

Then each term of the sum (using natural logarithms) has the form

$$ a_x \, \ln \frac{a_x}{b_x}=b_x \, \left(1+\frac{e_x}{b_x}\right) \ln \left(1 +\frac{e_x}{b_x}\right) =b_x \, (1+u_x) \, \ln(1+u_x)$$

where $u_x=e_x/b_x$. Now, for small $u_x$, we use $\ln(1+u) = u - \frac{u^2}{2}+O(u^3)$ and hence the above is

$$ b_x \left( (1 + u_x) (u_x - \frac{u_x^2}{2}) + O(u_x^3)\right)=b_x \left( u_x +\frac{u_x^2}{2} + O(u_x^3)\right)$$

When we sum over $x$, the linear term vanishes, because $\sum_x b_x u_x = \sum_x e_x = 0$. Thus we are left with

$$ \sum_x b_x \left(\frac{u_x^2}{2} + O(u_x^3)\right) \approx \sum_x \frac{(a_x-b_x)^2}{2 \, b_x}$$

Because we want the relative entropy in bits, we must use the logarithm in base $2$, hence we must divide by $\ln(2)$.

$$D\left ( P_{o}\left [ x \right ]\left | \right |P_{1}\left [ x \right ] \right ) = \frac{1}{\ln (2)}\sum_{x} P_0[x] \ln \frac{P_0[x]}{P_1[x]} \approx \frac{1}{\ln(2)}\sum_{x}^{}\frac{\left( P_{0}\left [ x \right ]-P_{1}\left [ x \right ]\right)^{2}}{ 2 \, P_{1}\left [ x \right ]}$$

Notice that this approximation relies on $|u_x| = \frac{|P_0[x] - P_1[x]|}{P_1[x]} \ll 1$ in all the support of $P_1[x]$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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