0

I know that $(1-1/n)^n \approx 1/e$, but what is the result for $\left(1-\frac{c f(n)}{n}\right)^n$, where $c$ is an arbitrary constant and $f(n)$ is an arbitarry function of $n$?

I am asking because I am having trouble understanding these derivations: $E(x)=\binom{n}{2} (1-p)(1-p^2)^{n-2}$

Let $p=c \sqrt{\ln n / n}$

$E(x) \approx n^2/2 (1-c \sqrt{\ln n / n})(1-c^2 \ln n / n)^n$

$\approx n^2/2 e^{-c^2\ln n} \approx 1/2 n^{2-c^2}$

For $c>\sqrt 2$, then $E(x) \to 0$

Source: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf, page 11

user
  • 154,566
fox
  • 679
  • 7
  • 18
  • $\lim_{n\to \infty} (1-(c/n)^n=e^{-c}$. – Dispersion May 30 '18 at 19:16
  • But that does not fit the derivation above, made by a professor of CMU. I am missing something – fox May 30 '18 at 19:17
  • It is quite easy to see what the limit should be if it exists. If $c$ is an integer, for example, then take the subsequence with $n=mc$ - and if the limit exists it must be the limit of the subsequence. Rational numbers can be handled too. The issue at hand seems to be proving that the limit exists for $c$ a real number. And given what you write, it rather assumes that the natural logarithm has already been defined - that definition would be important to the proof. – Mark Bennet May 30 '18 at 19:23
  • @Zachary That's true, but irrelevant to the question... – Clement C. May 30 '18 at 19:30
  • By the way, (to the OP), the last line s ambiguous. It is $\frac{1}{2}n^{2-c^2}$, while what you wrote could be interpreted as $\frac{1}{2n^{2-c^2}}$. – Clement C. May 30 '18 at 19:31
  • After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. – Clement C. Jun 01 '18 at 16:54

4 Answers4

1

You cannot say much about an arbitrary function of $n$: the result will depend on the function.

For instance, for $f(n)=1/n$ $$ \left(1+\frac{1}{n^2}\right)^n \xrightarrow[n\to\infty]{} 1 $$ while for $f(n) = n$, of course $$ \left(1+1\right)^n \xrightarrow[n\to\infty]{} \infty\,. $$ and for say $f(n) = -\sqrt{n}$ $$ \left(1-\frac{1}{\sqrt{n}}\right)^n \xrightarrow[n\to\infty]{} 0\,. $$

In your specific case, however, for $f(n) = -c^2 \ln n$, $$ \left(1-\frac{c^2\ln n}{n}\right)^n = e^{n\ln\left(1-\frac{c^2\ln n}{n}\right)} = e^{-c^2\ln n + o(1)} = \frac{1+o(1)}{n^{c^2}} \xrightarrow[n\to\infty]{} 0\,, $$ using that $\ln(1+u)=u+O(u^2)$ when $u\to 0$.

Clement C.
  • 67,323
  • Golub and Jackson (http://www.people.fas.harvard.edu/~bgolub/papers/homophily.pdf, proposition 4) shows that in a random graph model with $r$ random graphs, nodes connected inside graphs with prob $p$, outside with prob $q$, the expected diameter is $\log n/ \log degree$. How to renconcile thsi finding with the one of Blum's? – fox Jun 01 '18 at 17:35
0

As already pointed out it depends upon the particular function $f(n)$ chosen, indeed by simple examples we see that

  • $f(n)=\frac n c\implies \left(1-\frac{c f(n)}{n}\right)^n=(1-1)^n=0$

  • $f(n)=-\frac 1 c\implies \left(1-\frac{c f(n)}{n}\right)^n=\left(1+\frac{1}{n}\right)^n\to e$

user
  • 154,566
  • Not to be mean, but your answer starts (as you yourself write) by saying things already said, and then does not answer the specific thing the OP is trying to understand (i.e., the derivation from the lecture notes linked). – Clement C. May 30 '18 at 19:56
  • @ClementC. Sorry I didn't take a look to the notes attached, I was focusing to select some simple example to answer to the first part of the OP. For the second part your answer seems sufficient to explain! – user May 30 '18 at 20:00
0

The author seems to be indulging in the kind of loosey-goosey reasoning mathematicians love to hate: Because $(1-{x\over n})^n\approx e^{-x}$ when $n$ is large and $x$ is small, and because $\ln n$ is small compared to $n$ when $n$ is large, they are saying, in effect, that

$$\left(1-{\ln n\over n}\right)^n\approx e^{-\ln n}={1\over n}$$

It's worth checking how good the comparison is for a few values of $n$:

$$\begin{align} \left(1-{\ln100\over100}\right)^{100}&=0.00896362657\ldots\approx0.01\\ \left(1-{\ln1000\over1000}\right)^{1000}&=0.00097631598\ldots\approx0.001\\ \left(1-{\ln10000\over10000}\right)^{10000}&=0.00009957648\ldots\approx0.0001 \end{align}$$

You can see that the approximations do seem to be getting better, but what's missing (certainly here) is any technical description of what "getting better" means. Perhaps a closer reading of the source might find an argument that more formally justifies the approximations being made.

Barry Cipra
  • 79,832
  • Importantly, here this "loosey-goosey reasoning" does work and can be made rigorous, even if (after looking at the source) it's not done there. – Clement C. May 30 '18 at 20:03
  • 1
    @ClementC., agreed. I'm a big fan of loosey-goosey reasoning, especially when there's rigor lurking behind the curtain (and sometimes even when there isn't...). – Barry Cipra May 30 '18 at 21:22
-1

You have to set the following change of variable x= -n/c. Then your equation become : ((1+1/x)^x)^-c. Because c is a constant you can pass the limit into the exponential and when x goes to infinity, you find e^-c

thephysics17
  • 31