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.

So I was reading a paper where the following approximation was made. Note that $p$ is small, $L$ is large, and $pL$ is $O(1)$: $$\left[1-e^{-4p(1+p)L}\right]^{L/2}=\textrm{exp}\left[\frac{2(pL)^2}{e^{4pL}-1}\right](1-e^{-4pL})^{L/2}+O(p^3L^2)$$ I just don't see where this approximation came from, despite playing around with it for a while. Any insight would be much appreciated.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

If $p$ is small, then $1+p \sim 1$, so let's pull that out:

$$ e^{-4p(1+p)L} = e^{-4pL} e^{-4p^2L} = e^{-4pL} (1 + O(p^2 L))$$

Easy enough. $e^{-4pL} \in O(1)$ so we can simplify a bit:

$$ 1 - e^{-4p(1+p)L} = (1 - e^{-4pL}) (1 + O(p^2 L)) $$

Oh, but this approximation isn't good enough to compute $(1 + O(p^2 L))^{L/2}$. So let's do better:

$$ e^{-4p(1+p)L} = e^{-4pL} (1 - 4p^2L + O(p^4 L^2))$$

now, we have

$$ (1 - e^{-4p(1+p)L}) = 1 - e^{-4pL} + e^{-4pL} 4 p^2 L + O(p^4 L^2) $$

a little messier to factor:

$$ \cdots = (1 - e^{-4pL}) \left(1 + \frac{e^{-4pL} 4 p^2 L}{1 - e^{-4pL}} + O(p^4 L^2)\right) $$

It's still going to be a pain to raise that to the $L/2$ power. Fortunately, we can rewrite the second factor in a convenient way:

$$ \cdots = (1 - e^{-4pL}) \exp\left( \frac{e^{-4pL} 4 p^2 L}{1 - e^{-4pL}} + O(p^4 L^2) \right) $$

Great! I don't usually use this trick, but that's probably because I usually forget about it! You could do without it (binomial theorem). Anyways, raising to the $L/2$ power...

$$ (1 - e^{-4p(1+p)L})^{L/2} = (1 - e^{-4pL})^{L/2} \exp\left( \frac{e^{-4pL} 4 p^2 L^2}{2(1 - e^{-4pL})} + O(p^4 L^3) \right) $$

Now let's move that $O$ out of the exponent:

$$ \cdots = (1 - e^{-4pL})^{L/2} \exp\left( \frac{e^{-4pL} 2 p^2 L^2}{(1 - e^{-4pL})} \right) (1 + O(p^4 L^3))$$

We can simplify that exponential a bit more:

$$ \cdots = (1 - e^{-4pL})^{L/2} \exp\left( \frac{2 p^2 L^2}{e^{4pL} - 1} \right) (1 + O(p^4 L^3))$$

Also, since the first factor has magnitude less than 1 and the second is $O(1)$, we can easily distribute the last factor:

$$ \cdots = (1 - e^{-4pL})^{L/2} \exp\left( \frac{2 p^2 L^2}{e^{4pL} - 1} \right) + O(p^4 L^3)$$

So the approximation is actually better than what the paper claims. Honestly, I didn't expect to get the same approximation when I started this calculation; I figured I'd get something similar, but show enough of the ideas that you could work the rest of the details on your own to get the exact form you wanted.

(EDIT) Warning: I had assumed $pL \in \Theta(1)$ in my derivation. If you are interested in the case of $pL \in o(1)$, you may (or may not) need to tweak some things. One thing to be careful of is that $(1 - e^{-4pL})^{-1}$ would no longer be $O(1)$.

share|improve this answer
    
Thank you! Very helpful. –  user34364 Jun 24 '12 at 2:18
    
@narps: See my warning: I had assumed $pL \in \Theta(1)$ when I first made the derivation, so I've mentally made some logic errors, although I do not know if it actually changes anything. –  Hurkyl Jun 24 '12 at 2:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.