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'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough.

My approach was to take the Taylor series at $x=\frac{1}{4}$, cut it off as a quadratic, then find the inverse of that. That yields

$$H_2^{-1}(x) \approx -\frac{1}{16} \, \sqrt{-96 \, x \log\left(2\right) + 9 \, \log\left(3\right)^{2} - 72 \, \log\left(3\right) + 96 \, \log\left(4\right)} + \frac{3}{16} \, \log\left(3\right) + \frac{1}{4}$$

Unfortunately, that's a pretty bad approximation and it's complex at $H_2^{-1}(1)$. What other approaches can I take?

[1] I originally forgot to write the base 2 subscript (I added that in a later edit)

share|improve this question

2 Answers 2

A nice approximation I found in this thesis:

$ \frac{x}{2 \log_2 (6/x)} \leq H_2^{-1}(x) \leq \frac{x}{ \log_2 (1/x)}$

share|improve this answer

A rather coarse approximation of $H_2(x)$ on the said interval is $4 \log(2) x(1-x)$. Hence a crude approximation for the inverse is: $$ H_2^{-1}(y) \approx \frac{1}{2} \left(1- \sqrt{1-\frac{y}{\log(2)}}\right) = \frac12\frac{y}{\log(2) + \sqrt{\log(2)\left(\log(2)-y\right)}} $$ This initial approximation should be refined with Newton-Raphson method.

share|improve this answer
    
Thanks! How did you come up with $H_2(x) \approx 4 \log(2) x (1-x)$? –  Red Aug 29 '12 at 3:17
2  
The entropy is symmetric function of $x$, suggesting to approximate it by a polynomial in $x(1-x)$. –  Sasha Aug 29 '12 at 3:19
1  
@Red I meant symmetric around $x=1/2$. –  Sasha Aug 29 '12 at 3:27
    
+1. A slightly better approximation would be to choose $a$ such that $$\int_0^1 \left(H_2(x) - ax(1-x) \right)^2 dx$$ is minimized. This gives us $a= \dfrac{35}{12} \approx 2.91667$ as opposed to $a = 4 \log(2) \approx 2.7726$. Sasha's $4 \log 2$ ensures that the approximation is always $\leq H_2(x)$, whereas the above approximation optimizes the choice over the entire domain. –  user17762 Nov 28 '12 at 23:53

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.