In "Probabilistic Graphical Models" book by Daphne Koller and Nir Friedman they have the following approximation of probability of r successful outcomes of N Bernoulli trials:

$P(S_N=r)\approx \exp(-N \cdot \mathbb{D}((p,1-p) \parallel (r/N,1-r/N)))$

Here $p$ is the probability of success, $N$ is the number of all trials, $r$ is the number of successful trials, $\mathbb{D}$ is Kullback–Leibler divergence (relative entropy) .

I'm struggling with the proof of the approximation. Here is what I get so far:

First, we know that $P(S_N=r)$ is equal to $A=\frac{N!}{r! \cdot (N-r)!} \cdot p^r \cdot (1-p)^{N-r}$

Using Stirling approximation we can get $\log(A)\approx N\log(N)-r\log(r)-(N-r) \cdot \log(N-r)+r \cdot \log(p)/\log(2)+(N-r) \cdot \log(1-p)/\log(2)$.

The right hand side of the approximation is equal to $B=\exp(-N \cdot (p \cdot \log_2(\frac{p}{r/N})+(1-p) \cdot \log_2(\frac{1-p}{1-r/N})))$

$\log(B)=-N \cdot (p \cdot \log_2(\frac{p}{r/N})+(1-p) \cdot \log_2(\frac{1-p}{1-r/N}))$

I do not see any connection between $\log(A)$ and $\log(B)$. Should I use another approximation of binomial coefficient? Any other ideas about the proof of the approximation?

  • 1
    $\begingroup$ 1. With this definition of relative entropy, one should use $D(r/N,1-r/N\mid p,1-p)$, not the other way round. 2. Later on, every $\log_2$ should be $\log$. 3. Use $r=xN$ everywhere to reach the correct formula $D(x,1-x\mid p,1-p)$ (it works). $\endgroup$ – Did Mar 18 '13 at 10:35

Did pointed out the main points above. I will develop the ideas here and will write a proof for my own question.

Let $r=x \cdot N$

$\log(A)\approx r/x\cdot\log(r/x)-r\cdot\log(r)-(r/x-r)\cdot\log(r/x-r)+ r \cdot \log(p)+(r/x-r) \cdot \log(1-p)=r/x\cdot\log(r)-r/x \log(x)-r/x \log r- r/x \log(1-x)+r/x \log x + r\log r+r\cdot\log (1-x)-r\log x-r\log r+r\log p +r/x \log(1-p) -r \log(1-p) =-r/x \cdot \log (1-x)+r\cdot \log (1-x) -r\cdot \log x + r \cdot \log p + r/x \cdot \log(1-p) -r\cdot \log(1-p)$

$\log(B)=-r/x \cdot (x\log x/p + (1-x) \log (\frac{1-x}{1-p}))=-r \cdot \log x +r\cdot \log p- r/x \cdot \log (1-x) +r \cdot \log(1-x)+r/x \cdot \log(1-p)-r \cdot \log (1-p)$

It is easy to see that the last expression we get for $\log A$ is equivalent to last expression for $\log B$.

Thank you, Did. I finally solved the question which bothered me for a whole week.

  • $\begingroup$ +1. You may accept your own answer if you wish, in a while. (But please use \log everywhere.) $\endgroup$ – Did Mar 18 '13 at 20:00

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.