0
$\begingroup$

Define $L(k) = \lim_{n \rightarrow \infty} (1-\frac{k}{n})^{k}$, where $1 \leq k \leq n$.

For "low" values of $k$ (e.g. $k = c_0$ independent of $n$) it holds that $L = 1$, and for "high" values of $k$ (e.g. $k = n - 1$) it holds that $L = 0$. I am trying to compute the "phase transition range", i.e. the range $O = [1,f(n)]$ such that for all $k \in O$, $L(k) = 1$ and the range $Z = [g(n), n]$ such that for all $k \in Z$, $L(k) = 0$ (where $f,g$ are as tight as possible).

Any ideas?

$\endgroup$
8
  • $\begingroup$ Take logarithms ? $\endgroup$
    – Empy2
    Apr 5, 2020 at 14:48
  • $\begingroup$ Tried that. But I couldn't see how $k \log(1-\frac{k}{n})$ is better than the original expression (it helps to see the behavior for a given $k$, but I couldn't derive the range from it) $\endgroup$
    – Ernie
    Apr 5, 2020 at 14:56
  • $\begingroup$ If k is much smaller than n then $\log(1-k/n)\approx -k/n$ $\endgroup$
    – Empy2
    Apr 5, 2020 at 14:58
  • $\begingroup$ Indeed, but this would only help to understand what happens when $k$ is "small". It won't help to understand what happens when $k = \Theta(n)$, and I don't see how it helps to determine the range $\endgroup$
    – Ernie
    Apr 5, 2020 at 15:05
  • $\begingroup$ If $k=m\sqrt n$ the log is roughly $-m^2$, $L\approx \exp(-m^2)$ and it is in this interval that $L$ goes from $1$ to $0$ $\endgroup$
    – Empy2
    Apr 5, 2020 at 15:10

1 Answer 1

0
$\begingroup$

If $k= m\sqrt n$ as $n$ gets large, then $k/n$ gets small, so $$\ln L(k)=k\ln(1-k/n)\approx k(-k/n) =-m^2\\L(k)\approx e^{-m^2}$$

$\endgroup$

You must log in to answer this question.

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