5
$\begingroup$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I believe. So any help would be appreciated.

Solution is as follows: first we observe that $m = o(\sqrt n)$, in other cases ($m \ge \sqrt n$) exponent decreases much faster compared to growth of binomial coefficient. So, for the case of $m = o(\sqrt n)$ we could write following chain of (asymptotical) equalities:

\begin{align} C_n^m\cdot e^{-m^3/(\ln m)^{10}} & \sim \frac{n^m}{m!} \cdot e^{-m^3/(\ln m)^{10}} \\ &= e^{m \ln n - \ln m! - m^3/(\ln m)^{10}} \\ &\sim e^{m \ln n - m \ln m \cdot (1 + o(1)) - m^3/(\ln m)^{10}} \\ \end{align}

For last equation to be less than $1$, exponent argument should be less than/asymptotically equal to $0$:

\begin{align} & m \ln n - m \ln m \cdot (1 + o(1)) - \frac{m^3}{(\ln m)^{10}} \sim 0 \\ & \ln n - \ln m \cdot (1 + o(1)) - \frac{m^2}{(\ln m)^{10}} \sim 0 \\ & \ln n - \frac{m^2}{(\ln m)^{10}} \cdot (1 + o(1)) \sim 0 \\ \end{align}

And in the last equation I should find $m$ in terms of $n$. And I don't know how can I do that. May be I missed something on the previous steps and $(\ln m)^{10}$ could be removed somehow. But I cannot see a way to do that.

Thanks in advance for any ideas.

$\endgroup$
2
  • 2
    $\begingroup$ yandex school's problems are crazy $\endgroup$
    – Norbert
    Oct 27, 2013 at 9:33
  • $\begingroup$ Is $C_n^m$ defined as "choose $m$ objects out of $n$", or "choose $n$ objects out of $m$"? $\endgroup$
    – Kirill
    Oct 28, 2013 at 19:11

1 Answer 1

1
+50
$\begingroup$

$\def\tfrac#1#2{{\textstyle\frac{#1}{#2}}}$ Your approach seems to be in the direct direction, but you need to do more work and be more rigourous, especially when using asymptotic expansions of binomial coefficients. You expanded $\log m!$ correctly keeping the asymptotic error term $o(1)$, but you didn't do the same for $n!/(n-m)!$, which isn't really correct.

Especially you need to keep trying different asymptotic forms for $m$; if $m=o(n^\gamma)$ for every $\gamma>0$, the next thing to try is always some power of $\log n$.

Also, it is wrong to write $$ \text{anything} \sim 0, $$ because the definition of $f(x)\sim g(x)$ is $\lim_{x\to\infty}f(x)/g(x)=1$. The leading asymptotic term will be obtained from $$ \text{something} \sim m^3/(\log m)^{10},$$ but even after the leading term is found, the exponent will not be asymptotically constant, because of smaller terms, so expecting the exponent to be $\sim 0$ is wrong.

First, because $n$ is large, we can ignore the way $m$ is restricted to positive integers, and instead consider the equation $$ {n\choose m}e^{-m^3/\log^{10} m} = 1 $$ with real $m$ and $n$. Taking the logarithm of it, we get $$ \log\Gamma(n)-\log\Gamma(m)-\log\Gamma(n-m) = f(m), $$ where $f(m) = m^3/\log^{10}m$. Expanding using Stirling's formula, and simplifying gives the following equation that must be satisfied by $m$: $$ m\log(n/m) + O(m^2/n+m) = f(m). $$

Then proceed by trial and error. First, write $m\sim \rho n^\gamma$, $0<\gamma<\frac12$: $$ (1-\gamma)\rho n^\gamma\log n + O(n^\gamma+n^{2\gamma-1}) \sim n^{3\gamma}/\log^{10} n. $$ Clearly this cannot be solved (as you said), because it requires $\gamma=3\gamma$, $\gamma=0$, and we started with $\gamma>0$.

So, after some attempts, try the form $m\sim\rho (\log n)^\beta (\log\log n)^\delta$, which gives $$ \rho (\log n)^{\beta+1}(\log\log n)^\delta \sim \frac{\rho^3 (\log n)^{3\beta} (\log\log n)^{3\delta}} { (\beta \log \log n)^{10} }, $$ which can be solved for the unknowns.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer and for the general method for solving such problems. But I'm unable to solve the last equality (to rule out the unknowns). It gives me something like $\rho \sim \beta^5(\log n)^{1/2-\beta}(\log\log n)^{5-\delta}$ and $\beta^5$ is left after substituting $\rho$ in the equality for $m$. $\endgroup$
    – iw.kuchin
    Oct 29, 2013 at 7:47
  • $\begingroup$ @iw.kuchin I don't understand what you mean, both $\rho$ and $\beta$ are unknown constants, so how can it be impossible to solve for their values there? $A\sim B$ means $\lim_{n\to\infty}A/B = 1$. $\endgroup$
    – Kirill
    Oct 29, 2013 at 7:58
  • 1
    $\begingroup$ Also, I think the same form of $m$ could be used in my solution. If we just use it in the last equation we will get same result with defined $\beta$: $m \sim 2^{-5} \sqrt{\log n} (\log\log n)^5$ $\endgroup$
    – iw.kuchin
    Oct 29, 2013 at 8:00
  • $\begingroup$ @iw.kuchin Yes, that's right, but I find the way you wrote down your solution to be very imprecise. The solution is the same in both cases. $\endgroup$
    – Kirill
    Oct 29, 2013 at 8:02
  • $\begingroup$ this is the way same looking problem was solved during the lectures (except instead of $-m^3/(\ln m)^{10}$ there was just $-m^2$). And I've understood how is $2^{-5}$ is found in your solution. Thanks again! $\endgroup$
    – iw.kuchin
    Oct 29, 2013 at 8:08

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.