1
$\begingroup$

Given the following sum:

$S(n) = \sum_{i=1}^{n} \frac{1}{(1-\operatorname{H}(p))^i}$

where $H$ is the binary entropy function defined as:

$\operatorname{H}(p) = -p\log p - (1-p)\log (1-p) $.

Let $f(n) = \frac{n}{S(n)}$.

Assume $p$ is very small, is it possible to approximate the $S(n)$ and $f(n)$ defined above with simpler closed formulae e.g. a polynomial of $p$ without loosing much precision?

$\endgroup$
3
  • 2
    $\begingroup$ Is something missing in the sum? As wirtten it is $S(n)=\frac{n}{1-\operatorname{H}(p)}\,$, $f(n)=1-\operatorname{H}(p)$. $\endgroup$
    – Andrew
    Jan 2, 2014 at 8:03
  • $\begingroup$ My apologies, yes, I missed the exponent for $1-H(p)$, just edited my question. $\endgroup$
    – Kelvin Lee
    Jan 2, 2014 at 17:56
  • $\begingroup$ It's just a geometric series with the largest term at the end. Why don't you just sum it exactly? Then if you want an approximation for tiny $p$ use a Taylor expansion of the exact sum. $\endgroup$ Jan 4, 2014 at 2:42

2 Answers 2

2
$\begingroup$

The second order Taylor expansion of $H(p)$ may suffice for you. Expanding $H(p)$ around $p = 1/2$ it is not difficult to show that $$H(p)=1-\frac{(1-2 p)^2}{2 \ln 2}+O\left(\left(p-\frac{1}{2}\right)^3\right)$$ Thus, using the approximation $1 - H(p) \approx \frac{(1-2 p)^2}{2 \ln 2}$, we get $$S(n) \approx \sum_{i=1}^n \left(\frac{2 \ln 2}{(1-2 p)^2}\right)^{i},$$ which is has the simple closed form $$S(n) \approx \frac{2 \ln 2 \left((1-2 p)^2\right)^{-n} \left(\left((1-2 p)^2\right)^n-(2 \ln 2)^n\right)}{4 p^2-4 p+1-2 \ln 2}.$$

The approximation should be good near $p = 1/2$, however in the numerical examples I have worked out, it seems pretty reasonable.

$\endgroup$
4
  • $\begingroup$ I assumed $p$ was very small and maybe very close to $0$, say 1e-2, 1e-3, or 1e-4, will that complicate the approximation? $\endgroup$
    – Kelvin Lee
    Jan 4, 2014 at 5:40
  • $\begingroup$ Of course. As $p$ approaches 0, the sum approaches $n$ but this approximation doesn't. $\endgroup$ Jan 4, 2014 at 10:26
  • $\begingroup$ You may want to try the same ideias to obtain a Taylor Series approximation around any point $p$. And you may also calculate the sum in $n$ (geometric progression) and then do Taylor Approximation... some of these thechniques may suffice... $\endgroup$
    – Campello
    Jan 4, 2014 at 10:57
  • $\begingroup$ Oh. This is exactly what Brendan commented above. Sorry dude. $\endgroup$
    – Campello
    Jan 4, 2014 at 10:59
1
$\begingroup$

Almost eight years later

$$S(n) = \sum_{i=1}^{n} \frac{1}{\Big[1-\operatorname{H}(p)\Big]^i}=\frac{\Big[1-\operatorname{H}(p)\Big]^{-n}-1 }{\operatorname{H}(p) }$$

Answering this question, I proposed as a rather good approximation for the whole range of $p$ $$\operatorname{H}(p) \sim \big[4p(1-p)\big]^{\frac 34}\implies f(n)=\frac n {S(n)}=\frac{n\operatorname{H}(p) }{\Big[1-\operatorname{H}(p)\Big]^{-n}-1 }$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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