10
$\begingroup$

I am doing research on expected runtimes of evolutionary algorithms, and as I was trying to prove some inequalities about a certain Markov chain, I reduced one of the inequalities to the following:

Let $\ell$ and $n$ be integers with $2 \leq \ell < n$, then $$(2^\ell - 1) \sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \geq 0$$

I haven't yet been able to prove this, but my intuition on the Markov chain this comes from suggests that it is true.

Also, I have tested the above inequality in a simple Python program, and in all the couple million cases of $\ell$ and $n$ that I tried, the inequality was true. I tested it for the following cases:

  • $\ell \in \{2, 3, \ldots, 9 \}$ and $n \in \{\ell+1, \ell + 2, \ldots, 300000 \}$
  • $\ell \in \{10, 11, \ldots, 24 \}$ and $n \in \{\ell+1, \ell + 2, \ldots, 80000 \}$
  • $\ell \in \{25, 26, \ldots, 80 \}$ and $n \in \{\ell+1, \ell + 2, \ldots, 1000 \}$
  • $\ell \in \{81, 82, \ldots, 250 \}$ and $n \in \{\ell+1, \ell + 2, \ldots, 252 \}$

So is the above inequality true? And if so, what would be a proof for it?

As a side note, let me point out how tight (or close to tight) the above inequality is. Inside the sum, if you replace the exponent of $2\ell - 2k$ with $2\ell$, then the resulting inequality is not true in general. Further, if you only take the term $k = 1$ in the sum, then the inequality is not true in general. However, in all the above cases that I tried, the inequality did hold if we took the terms $k = 1$ and $k = 2$. Further, notice that the left hand side of the inequality approaches 0 as $n \to \infty$ (with $\ell$ fixed).

$\endgroup$

4 Answers 4

6
$\begingroup$

Let $m=n-1$ so $2\le\ell\le m$. Multiplying through by $(m+1)^{2\ell}$ and rearranging gives the equivalent $$(2^\ell-1)\sum_{k=1}^\ell\binom\ell km^{2(\ell-k)}\ge\left(\sum_{k=1}^\ell\binom\ell km^{\ell-k}\right)^2$$ which is true by Cauchy-Schwarz since $$\left(\sum_{k=1}^\ell\sqrt{\binom\ell k}\sqrt{\binom\ell k}m^{\ell-k}\right)^2\le\underbrace{\sum_{k=1}^\ell\binom\ell k}_{2^\ell-1}\cdot\sum_{k=1}^\ell\binom\ell km^{2(\ell-k)}.$$ By the if-and-only-if corollary, the inequality is strict as $m^{\ell-k}$ cannot be constant for all $k$.

$\endgroup$
1
  • 1
    $\begingroup$ It is very nice. $\endgroup$
    – River Li
    Jul 31, 2022 at 23:07
2
$\begingroup$

Let $\ell$ and $n$ be integers with $2 \leq \ell < n$, then $$(2^\ell - 1) \sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \geq 0$$

Multiply through by $n^{2\ell}$ and rearrange:

$$ (2^\ell-1)\sum_{k=1}^\ell\binom{\ell}{k}(n-1)^{2(\ell-k)} \geq n^{2\ell}+(n-1)^{2\ell}-2n^\ell(n-1)^\ell \tag{1} \label{1} $$

Now $$n^{2\ell}+(n-1)^{2\ell}-2n^\ell(n-1)^\ell=(n^\ell-(n-1)^\ell)^2, \label{2} \tag{2} $$ so to prove the inequality we just need to show that the left side of \eqref{1} is greater than \eqref{2}.

The summation $$ \sum_{k=1}^\ell{\ell\choose k}(n-1)^{2\ell-2k}=\left({1+(n-1)^2}\right)^\ell-(n-1)^{2\ell} $$ is the usual binomial, where the $(n-1)^{2\ell}$ at the right originates from the sum being from $k=1$ rather than $k=0$, so the left side of \eqref{1} is $$ (2^\ell-1)((1+(n-1)^2)^\ell-(n-1)^{2\ell}) $$ Define $q=\sqrt[\ell]{2^\ell-1}$ and for $\ell\geq 2$ then $q\geq\sqrt3$. The left side of \eqref{1} becomes $(q(1+(n-1)^2)^\ell-(2^\ell-1)$, and so for $n$ sufficiently large that $\sqrt3(n-1)^2>n^2$, for example $\sqrt3\times(199)^2>200^2$, the inequality is clearly valid. Here I've neglected the $(2^\ell-1)$ term since it's very clear that $2^\ell \ll n^\ell$ as n becomes larger, and we already know that the inequality is true for small values of $n$ and $l$ from the examples in the question.

See the SimpliFire's argument for the rest of this.

$\endgroup$
4
  • $\begingroup$ At first, this argument looked correct, but I believe that when you apply the binomial theorem, the $k = 0$ term is actually $(n-1)^{2\ell}$ and not 1. $\endgroup$ Jul 31, 2022 at 15:43
  • $\begingroup$ @AndrewKelley Thank you for spotting the error. $\endgroup$ Jul 31, 2022 at 18:45
  • $\begingroup$ I've amended the answer with corrections. From numerical tests, the entire $2^\ell-1$ seems to be necessary for the inequality to hold. I currently don't have an argument to prove the inequality, I'm going to leave the answer as it is for the time being. $\endgroup$ Jul 31, 2022 at 20:58
  • $\begingroup$ TheSimpliFire's arguments complete this, so I'll leave this answer as it is, since it does provide some of the stages which TheSimpliFire has skipped over. $\endgroup$ Jul 31, 2022 at 22:08
0
$\begingroup$

Since @Suzu Hirose already gave all elements, I shall focus on the asymptotics.

After simplifications, the lhs write (using $m=n-1$ for brevity) $$A=2^l \left(\frac{m}{n}\right)^{2 l} \left(1+\frac{1}{m^2}\right)^l-\left(\frac{m}{n}\right)^{2 l} \left(1+\frac{1}{m^2}\right)^l+2 \left(\frac{m}{n}\right)^l-2^l \left(\frac{m}{n}\right)^{2 l}-1$$

If $n$ is large, a series expansion gives $$A=\frac{l \left(2^l-l-1\right)}{n^2}+O\left(\frac{1}{n^3}\right)$$

$\endgroup$
0
$\begingroup$

Remarks: @TheSimpliFire gave a very nice proof by C-S. Here is an alternative proof.


Proof.

The case $n = 3$ is verified directly.

In the following, assume that $n \ge 4$.

Using the binomial theorem and Bernoulli inequality, we have \begin{align*} &\sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k}\\ =\,& \left[\frac{1}{n^2} + \left(1 - \frac1n\right)^2\right]^\ell - \left(1 -\frac{1}{n}\right)^{2\ell}\\ =\,& \left(1 - \frac1n\right)^{2\ell}\left[1 + \frac{1}{(n-1)^2}\right]^\ell - \left(1 -\frac{1}{n}\right)^{2\ell}\\ \ge\,& \left(1 - \frac1n\right)^{2\ell}\left[1 + \frac{\ell}{(n-1)^2}\right] - \left(1 -\frac{1}{n}\right)^{2\ell}\\ =\,& \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2}. \end{align*}

It suffices to prove that $$(2^\ell - 1) \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \ge 0$$ or $$(2^\ell - 1) \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2} \ge \left(1 - \left(1 - \frac{1}{n}\right)^{\ell}\right)^2 $$ or $$\frac{\sqrt{(2^\ell - 1)\ell}}{n - 1}\left(1 - \frac{1}{n}\right)^{\ell} \ge 1 - \left(1 - \frac{1}{n}\right)^{\ell} \tag{1}$$ which is true. The proof of (1) is given at the end.

We are done.


Proof of (1):

It is easy to prove the cases $\ell = 2, 3$.

In the following, assume that $\ell \ge 4$.

It suffices to prove that $$\sqrt{(2^\ell - 1)\ell} \ge (n-1)\left(\left(1 + \frac{1}{n - 1}\right)^\ell - 1\right)$$ or $$\sqrt{(2^\ell - 1)\ell} \ge \sum_{k=1}^\ell \binom{\ell}{k}\left(\frac{1}{n-1}\right)^{k-1}.$$ Using $n - 1 \ge \ell$, it suffices to prove that $$\sqrt{(2^\ell - 1)\ell} \ge \sum_{k=1}^\ell \binom{\ell}{k}\left(\frac{1}{\ell}\right)^{k-1} = \ell \left(\left(1 + \frac{1}{\ell}\right)^\ell - 1\right).$$ Using $\left(1 + \frac{1}{\ell}\right)^\ell \le \mathrm{e}$, it suffices to prove that $$2^\ell - 1 - (\mathrm{e} - 1)^2 \ell \ge 0.$$ Using Bernoulli, we have $2^\ell = 2^3 2^{\ell - 3} \ge 2^3(1 + \ell - 3)$. It suffices to prove that $$2^3(1 + \ell - 3) - 1 - (\mathrm{e} - 1)^2 \ell \ge 0$$ which is true.

We are done.

$\endgroup$

You must log in to answer this question.

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