# For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

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.

-
In which sense is $\approx$ taken here? –  Ashok Mar 25 '14 at 5:34
For $P_{0}$ close to $P_{1}$ ? –  ElfPath Mar 25 '14 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 '14 at 10:35

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]$

-