2

$$(n-1) \left[\frac{1}{2}\log\left(\frac{1}{2p}\right)+\frac{1}{2}\log\left(\frac{1}{2(1-p)}\right)\right]>2\log(n)$$

where $p$ is a function of $n$.

How to find out on which condition of $p$ such that the inequality holds (asymptotically)?

From the following experiment, it seems when $p>\frac{1+\sqrt{\frac{2\log n}{n}}}{2}$ the inequality holds, and when $p<\frac{1+\sqrt{\frac{2\log n}{n}}}{2}$ the inequality does not hold.

I can manage to prove that this is true by plugging the form of $p$ as $\frac{1+\sqrt{\frac{a\log n}{n}}}{2}$ into the inequality, but I have no idea to prove it without assuming the form of $p$.

It would be much appreciated if someone could help me out. Many thanks in advance!

enter image description here

enter image description here

Math Attack
  • 1
M.K
  • 541
  • It is a quadratic equation of $p$, right? – River Li Dec 01 '23 at 14:05
  • @RiverLi I don't get it, could you rephrase? there is no equation for $p$.. only inequality for $p$. – M.K Dec 01 '23 at 14:18
  • How about $(n-1) \left[\frac{1}{2}\log\left(\frac{1}{2p} \cdot \frac{1}{2(1-p)}\right)\right] > 2\log(n)$, or $p(1 - p) < \cdots$? – River Li Dec 01 '23 at 14:35
  • @RiverLi yes, i see, so it should be $p(1-p)<\exp(-\frac{2\log n}{n-1}-\log 4)$, but then i don't know how to proceed – M.K Dec 01 '23 at 15:54
  • WLOG, assume that $p \ge 1/2$. For an inequality $p (1 - p) < c$, you have $p > \frac12 + \frac12\sqrt{1 - c}$. Then you analyze asymptotic properties of $\frac12 + \frac12\sqrt{1 - c}$. – River Li Dec 01 '23 at 22:58
  • @RiverLi Thank you! I arrived at $p>\frac{1}{2}+\frac{1}{2} \sqrt{1-\exp(-4\frac{\log n}{n-1})}$. But I don't know how to align this with what we expect: $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2\log n}{n}}$ – M.K Dec 03 '23 at 23:05
  • I wrote something as an answer. You can try to prove that $1 - \mathrm{e}^{- \frac{4\ln n}{n - 1}} \le \frac{4\ln n}{n}$. – River Li Dec 04 '23 at 00:12
  • By the way, I think the result should be $p > \frac{1}{2}+\frac{1}{2}\sqrt{\frac{4\log n}{n}}$ rather than $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2\log n}{n}}$. – River Li Dec 04 '23 at 03:53
  • @RiverLi According to the simulation in my post, it should be $\sqrt{\frac{2\log n}{n}}$.. – M.K Dec 04 '23 at 10:53
  • How about $n = 10^6$, solve the original inequality, we have $p> 0.5037168727$. (1) $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2\log n}{n}}$ gives $0.5026282609$; (2) $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{4\log n}{n}}$ gives $0.5037169222$. – River Li Dec 04 '23 at 11:38
  • When $n = 10^{12}$, solve the original inequality, we have $p> 0.5000052565$. (1) $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2\log n}{n}}$ gives $0.5000037169$; (2) $\frac{1}{2}+\frac{1}{2}\sqrt{\frac{4\log n}{n}}$ gives $0.5000052565$. – River Li Dec 04 '23 at 11:40
  • Have you gotten clear which one is correct? – River Li Dec 19 '23 at 23:27

2 Answers2

0

Assuming $n>1$, gouping terms, you look for the problem of $$-\log (p(1-p) )~~ \geq~~ \frac{4 \log (n)}{n-1}+2 \log (2)= A$$ When $n$ increases, the solution requires that $p$ just be above the root of $\text{(lhs - rhs)}=0$ which is closer an closer to $p=\frac 12$.

Expanding as a Taylor series, we have $$\text{(lhs - rhs)}=-\frac{4 \log (n)}{n-1}+\sum_{n=1}^\infty \frac {t^n} n \qquad \text{with}\qquad t=(2p-1)^2$$ that is to say $$\text{(lhs - rhs)}=-\frac{4 \log (n)}{n-1}-\log (1-t)=0$$ $$t=1-n^{-\frac{4}{n-1}}\qquad \implies\qquad p=\cdots$$

Edit

To better see my point, type in Wolfram Alpha

Plot[-2*Log[2]-(4*Log[10])/(10-1)-Log[p(1-p)],{p,0,1}]

and look where the expression is positive. Change the $10$ by the number you want.

Claude Leibovici
  • 260,315
0

Some thoughts.

The inequality is written as $$p(1 - p) < \frac14\mathrm{e}^{- \frac{4\ln n}{n - 1}}. \tag{1}$$

WLOG, assume that $p \ge 1/2$. (1) is equivalently to $$p > \frac12 + \frac12\sqrt{1 - \mathrm{e}^{- \frac{4\ln n}{n - 1}}}.$$

We can prove that, for all $n \ge 2$, $$1 - \mathrm{e}^{- \frac{4\ln n}{n - 1}} \le \frac{4\ln n}{n}.$$

Thus, if $p > \frac12 + \frac12\sqrt{\frac{4\ln n}{n}}$, then the original inequality is true.

River Li
  • 37,323