I'm looking for an intuitive explanation for the following questions:
In statistics and information theory, what's the difference between Bhattacharyya distance and KL divergence, as measures of the difference between two discrete probability distributions?
Do they have absolutely no relationships and measure the distance between two probability distribution in totally different way?
The Bhattacharyya coefficient is defined as $$D_B(p,q) = \int \sqrt{p(x)q(x)}\,\text{d}x$$ and can be turned into a distance $d_H(p,q)$ as $$d_H(p,q)=\{1-D_B(p,q)\}^{1/2}$$ which is called the Hellinger distance. A connection between this Hellinger distance and the Kullback-Leibler divergence is $$d_{KL}(p\|q) \geq 2 d_H^2(p,q) = 2 \{1-D_B(p,q)\}\,,$$ since \begin{align*} d_{KL}(p\|q) &= \int \log \frac{p(x)}{q(x)}\,p(x)\text{d}x\\ &= 2\int \log \frac{\sqrt{p(x)}}{\sqrt{q(x)}}\,p(x)\text{d}x\\ &= 2\int -\log \frac{\sqrt{q(x)}}{\sqrt{p(x)}}\,p(x)\text{d}x\\ &\ge 2\int \left\{1-\frac{\sqrt{q(x)}}{\sqrt{p(x)}}\right\}\,p(x)\text{d}x\\ &= \int \left\{1+1-2\sqrt{p(x)}\sqrt{q(x)}\right\}\,\text{d}x\\ &= \int \left\{\sqrt{p(x)}-\sqrt{q(x)}\right\}^2\,\text{d}x\\ &= 2d_H(p,q)^2 \end{align*}
However, this is not the question: if the Bhattacharyya distance is defined as$$d_B(p,q)\stackrel{\text{def}}{=}-\log D_B(p,q)\,,$$then
\begin{align*}d_B(p,q)=-\log D_B(p,q)&=-\log \int \sqrt{p(x)q(x)}\,\text{d}x\\
&\stackrel{\text{def}}{=}-\log \int h(x)\,\text{d}x\\
&= -\log \int \frac{h(x)}{p(x)}\,p(x)\,\text{d}x\\
&\le \int -\log \left\{\frac{h(x)}{p(x)}\right\}\,p(x)\,\text{d}x\\
&= \int \frac{-1}{2}\log \left\{\frac{h^2(x)}{p^2(x)}\right\}\,p(x)\,\text{d}x\\
\end{align*}
Hence, the inequality between the two distances is
$${d_{KL}(p\|q)\ge 2d_B(p,q)\,.}$$
One could then wonder whether this inequality follows from the first one. It happens to be the opposite: since $$-\log(x)\ge 1-x\qquad\qquad 0\le x\le 1\,,$$
we have the complete ordering$${d_{KL}(p\|q)\ge 2d_B(p,q)\ge 2d_H(p,q)^2\,.}$$
I don't know of any explicit relation between the two, but decided to have a quick poke at them to see what I could find. So this isn't much of an answer, but more of a point of interest.
For simplicity, let's work over discrete distributions. We can write the BC distance as
$$d_\text{BC}(p,q) = - \ln \sum_x (p(x)q(x))^\frac{1}{2}$$
and the KL divergence as
$$d_\text{KL}(p,q) = \sum_x p(x)\ln \frac{p(x)}{q(x)}$$
Now we can't push the log inside the sum on the $\text{BC}$ distance, so let's try pulling the log to the outside of the $\text{KL}$ divergence:
$$d_\text{KL}(p,q) = -\ln \prod_x \left( \frac{q(x)}{p(x)} \right)^{p(x)}$$
Let's consider their behaviour when $p$ is fixed to be the uniform distribution over $n$ possibilities:
$$d_\text{KL}(p,q) = -\ln n - \ln \left(\prod_x q(x)\right)^\frac{1}{n} \qquad d_\text{BC}(p,q) = - \ln \frac{1}{\sqrt{n}} - \ln\sum_x \sqrt{q(x)}$$
On the left, we have the log of something that's similar in form to the geometric mean. On the right, we have something similar to the log of the arithmetic mean. Like I said, this isn't much of an answer, but I think it gives a neat intuition of how the BC distance and the KL divergence react to deviations between $p$ and $q$.
