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?

Improve this question
$\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
    Commented 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
    Commented 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$
    – Brendan McKay
    Commented Jan 4, 2014 at 2:42

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented Jan 4, 2014 at 5:40
  • $\begingroup$ Of course. As $p$ approaches 0, the sum approaches $n$ but this approximation doesn't. $\endgroup$
    – Brendan McKay
    Commented 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
    Commented Jan 4, 2014 at 10:57
  • $\begingroup$ Oh. This is exactly what Brendan commented above. Sorry dude. $\endgroup$
    – Campello
    Commented 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 }$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .