1

I came across the following asymptotic problem in my reseach, however I don't know how to answer it.

Let $C_0,C_1,C_2,C_3$ be absolute constant (do not depend on $n$), and $p(n)$ is a function of $n$.

We need to find $p(n)$ such that the following two conditions hold:

(1) $p(n)$ that is larger than the following function, i.e., $$\tiny p(n)>\frac{-(4+(n-2)(2C_1+C_2))+\sqrt{((4+(n-2)(2C_1+C_2)))^2-4\cdot (-(n-2)(C_1+C_2-C_3))\cdot(-2C_0-(n-2)C_1)}}{2(-(n-2)(C_1+C_2-C_3))}$$ It is okay if this only holds for sufficiently large $n$.

(2) Let $$\tiny E(p(n),n):=(-2C_0-(n-2)C_1+(4+(n-2)(2C_1+C_2))\cdot p-(n-2)(C_1+C_2-C_3)p^2)^2$$ and $$\tiny F(p(n),n):= 4C_0^2\cdot (-4p^2+4p)+C_1^2\cdot \frac{1}{8}(n-2)4(-p+1)p+(n-1)(1-(1-2p)^4)+C_2\cdot \frac{1}{4}(n-1)\big(1-(1-2p)^4\big)+C_3^2 \frac{1}{8}(n-2)4(-p+1)p+(n-1)(1-(1-2p)^4)$$

we need $$E\succ F$$ for sufficiently large $n$. In other words, $$\lim_{n\rightarrow+\infty}\frac{E}{F}=+\infty$$

What I tried

Should I assume the following and then plug it into $\frac{E}{F}$?

$$\tiny p(n)=\frac{-(4+(n-2)(2C_1+C_2))+\sqrt{((4+(n-2)(2C_1+C_2)))^2-4\cdot (-(n-2)(C_1+C_2-C_3))\cdot(-2C_0-(n-2)C_1)}}{2(-(n-2)(C_1+C_2-C_3))}+g(n)$$

chloe
  • 512
  • For your first condition, I think the RHS is asymptotic to a constant $K=\frac{2C_1+C_2-\sqrt{C_2^2+4C_1 C_3}}{2(C_1+C_2-C_3)}$ so that as long the $C_j$ are chosen so that $K\neq 0$ you can choose $p(n)$ any increasing function of $n$. For the second, $p(n)=n$ seems to work – Sal Mar 09 '24 at 08:47
  • @Sal I'm wondering what would be the worst $p(n)$? I tried numerics and see even $p(n)$ decreases, $E$ still dominates $F$. So my question is what is the $p(n)$ that sit on the worst case (the slowest one but still $E$ dominates $F$) – chloe Mar 09 '24 at 14:10
  • if your problem has been resolved I would appreciate it if you mark an answer as accepted :) – Sal Mar 12 '24 at 09:30

1 Answers1

1

With the help of a CAS, we find

$$ \frac{F}{E}\sim\frac{1}{n} \frac{N}{D} \qquad, \qquad n \to \infty $$

Where

$$ N= \left(-4 C_2-32\right) p^4+\left(8 C_2+64\right) p^3+\left(-\frac{C_1^2}{2}-6 C_2-\frac{C_3^2}{2}-48\right) p^2+\left(\frac{C_1^2}{2}+\frac{C_3^2}{2}+2 C_2+16\right) p \\ D=\left(C_1+C_2-C_3\right){}^2 p^4-2 \left(2 C_1+C_2\right) \left(C_1+C_2-C_3\right) p^3+\left(\left(2 C_1+C_2\right){}^2+2 C_1 \left(C_1+C_2-C_3\right)\right) p^2-2 C_1 \left(2 C_1+C_2\right) p+C_1^2 $$

Consider cases: If $p\to \infty$ then the $4$ powers of $p$ in the numerator match the $4$ powers in the denominator, so $F/E\sim 1/n \to 0$. If $p\to 0$ then the numerator vanishes and the denominator stays finite, so $F/E\to 0$. If $p\to \text{const}$ then $F/E\sim1/n\to 0$. So for any choice of $p$, your second condition is fulfilled- as long as the appropriate leading term doesn't vanish due to an unfortunate relation between the $C_i$ (such as $C_1+C_2-C_3=0$).

For your first condition, let $Q= [\text{RHS expression}]$. We have

$$ Q\sim K=\frac{2C_1+C_2-\sqrt{C_2^2+4C_1 C_3}}{2(C_1+C_2-C_3)} \qquad, \qquad n \to \infty $$

So we want to choose $p=K$. However, $Q$ may approach $K$ from above or below, and the inequality $p>Q$ means we must ensure that the difference $p-Q>0$. The difference $K-Q$ shows up at order $1/n$. If the coefficient at this order is positive, we can choose $p=K$. If the coefficient is negative, we can add a small positive term to $K$. The smallest term we can add that fixes the difference will be just a little larger than $1/n$. So the 'best' choice, written compactly to take care of either case above, is

$$ p(n)=K+n^{\epsilon-1}H(X) $$

Where $0<\epsilon\ll 1$, $H$ is the Heaviside step function, and $-X$ has the sign of the difference $K-Q$, specifically:

$$ X=\left( C_1+C_2-C_3\right)\left(\sqrt{C_2^2+4 C_1 C_3}+\left(C_0-2\right) C_1+\left(C_0-1\right) C_2-C_0 C_3\right) $$

Sal
  • 4,822
  • Thank you for your input! But I got some questions: First question from the condition (1) we would need $p$ larger than $K$ which means that $p$ either grows with $n$ (thus $p$ goes to inifinity), or it decreases with $n$, and converges to $K$. So the case in your answer, $p\rightarrow 0$ doesn't exist. Thus to proceed condition (2), should we plug in $p=K+n^{\epsilon-1}H(x)$? Second question I don't understand the step on Heaviside step function, why $p(n)=K+n^{\epsilon-1}H(x)$? – chloe Mar 11 '24 at 07:41
  • I understand the second question partialy now: the Heaviside step function is to avoid the negativeness of the coefficient. But the coefficient of H(x) is not consistent to yours: $\frac{2c_2^2+8c_1c_3+(-4c_1+2c_0c_1-2c_2+2c_0c_2-2c_0c_3) \sqrt{c_2^2+4c_1c_3}}{(c_1+c_2-c_3)(c_2^2+4c_1c_3)}$. This was obtained by asymptotics of $[RHS]-K$ and take the coefficient of $1/n$. – chloe Mar 11 '24 at 09:01
  • Third question I am a bit confused the first condition: The asymptotics of [RHS] is $K$, but why the asymptotics of [RHS]-$K$ is $H(x)\frac{1}{n}$? should it be zero? It seems contradiction because I thought: asymptotics of {[RHS]-K}={asymptotics of [RHS]} - K. – chloe Mar 11 '24 at 09:29
  • Something terrible happened when I copied the text for my $X$. Its fixed now.
    1. my grammar made the conclusion read in an unintended way: I meant that for any choice of $p$ your second condition still holds (even if $p$ doesn't $\to 0$). I wasn't saying it holds for (only) any $p\to 0$. I've edited in the answers to 2 and 3
     – Sal Mar 11 '24 at 09:39
  • thank you! The $X=\frac{2c_2^2+8c_1c_3+(-4c_1+2c_0c_1-2c_2+2c_0c_2-2c_0c_3) \sqrt{c_2^2+4c_1c_3}}{(c_1+c_2-c_3)(c_2^2+4c_1c_3)}$ I obtained seems still not consistent to yours.. – chloe Mar 11 '24 at 09:48
  • Your $X$ is (I think- check brackets) correct as the coefficient of $1/n$. To get mine I simplified that coefficient knowing we'd be applying $H$ so only the sign of the result matters. This means lots of stuff can just be cancelled in that expression – Sal Mar 11 '24 at 09:51
  • and what does "CAS" mean? thanks! – chloe Mar 11 '24 at 14:06
  • No problem :) It means computer algebra system... for instance Mathematica. I am curious- where did your problem come from? – Sal Mar 11 '24 at 15:33
  • ah I see! It's a bit long story, I was trying to compute a probability that a function is negative, to do that I would need the terms in that probability to be "nice" asymptotically. – chloe Mar 11 '24 at 16:12
  • @chloe If my answer has resolved your problem, I would be much obliged if you accept it :) – Sal Mar 21 '24 at 16:30