0
$\begingroup$

How do I see that $$1-(1-\frac 1 M)^Q \approx \frac Q M$$ (provided that $Q$ is small compared to $M$), where both $Q$ and $M$ are integers ?

The approximation is stated in a book without proof.

I've tried looking into some analysis and using the binomial expansion theorem, but haven't come to a conclusion.

Also, how "small" should $Q$ be compared to $M$ before the approximation is good ?

$\endgroup$
  • 2
    $\begingroup$ Using the Taylor expansions of $-\ln(1-x)$ and $e^x$ around $0$, you get $$\begin{align} 1-\left(1-\frac 1 M\right)^Q &= 1-e^{Q\ln (1-\frac 1 M)} = 1-e^{-\frac{Q}{M} + o\!\left(\frac{Q}{M}\right)} = 1-\left(1-\frac{Q}{M} + o\!\left(\frac{Q}{M}\right)\right) \\&= \frac{Q}{M} + o\!\left(\frac{Q}{M}\right) \end{align}$$ $\endgroup$ – Clement C. Dec 31 '14 at 10:59
  • 1
    $\begingroup$ You buy an item and you get 1% discount. And because you are the first customer of 2015, another 1% of the remaining amount. Then, because 1% is really tiny anyway, this is almost the same thing as getting 1% of the total amount instead. So $(1-\tfrac1{100})^2 \simeq 1 - \tfrac{2}{100}$. $\endgroup$ – Myself Dec 31 '14 at 12:13
1
$\begingroup$

Another way to look at it compared with clement nice comment/answer is $$ (x+y)^n = \sum_{k=0}^{n}\left(\matrix{n\\k}\right)x^{k}y^{n-k} $$ Putting in $x= -1/M$ and $y=1$ for convience. We find $$ (-\frac{1}{M} +1)^Q= \sum_{k=0}^{Q}\left(\matrix{Q\\k}\right)\left(-\frac{1}{M}\right)^{k} $$ The first few terms are $$ \left(\matrix{Q\\0}\right)\left(-\frac{1}{M}\right)^{0} + \left(\matrix{Q\\1}\right)\left(-\frac{1}{M}\right)^{1} + ... $$ Which yields your result. The size of $x$ in this case determines you can truncate the binomal expansion to first order terms.

$\endgroup$
1
$\begingroup$

Consider the geometric progression: $$ \overbrace{\left(1{}+{}\left(1-\frac{1}{M}\right){}+{}\ldots{}+{}\left(1{}-{}\frac{1}{M}\right)^{Q-1}\right)}^{Q\mbox{ terms}}{}={}\frac{\left(1{}-{}\left(1{}-{}\frac{1}{M}\right)^Q\right)}{\left(1{}-{}\left(1{}-{}\frac{1}{M}\right)\right)}{}={}M\left(1{}-{}\left(1{}-{}\frac{1}{M}\right)^Q\right) $$

For $M$ sufficiently large, each of the $Q$ terms on the l.h.s is approximately $1$. Therefore, their sum in this case is approximately $Q$, giving $$ \frac{Q}{M}\approx\left(1{}-{}\left(1{}-{}\frac{1}{M}\right)^Q\right)\,. $$ For $Q$ and $M$ not integers, the argument required is more sophisticated.

$\endgroup$

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.