5
$\begingroup$

In Drift Analysis and Evolutionary Algorithms Revisited by Johannes Lengler and Angelika Steger in Theorem 10, there is mention of a constant "$2.2$", and in the proof it becomes apparent that the theorem is actually true for all c, which are the solution to the following system: Define $f \colon \mathbb{R}^2 \to \mathbb{R}$ as

$$f(a, c) := ac - e^{(a - 1)c} + \frac{a}{a - 1}$$ and consider the system of equations \begin{align}f(a, c) &= 0\\\\ \frac{\partial f}{\partial a}(a, c) &=0\end{align}

We are looking for a solution of this system near $(0.237, 2.13)$. It is easy to calculate solutions to this system numerically to arbitrary precision: Here is some code to get $$c = 2.13692884344059837908651709517671705999047797307894493...$$

For $0 = \frac{\partial f}{\partial a}(a, c) - c\cdot f(a, c)$ the exponential terms cancel and we get the relation $$c = \frac{\sqrt{-4a + 1} - 1}{2(a^2 - a)} \label{Eq:star}\tag{$\star$}$$ Substituting this expression back in $f(a, c)$, gives a function $g\colon \mathbb{R} \to \mathbb{R}$ defined as $$g(a) := f(a, \tfrac{\sqrt{-4a + 1} - 1}{2(a^2 - a)}).$$ One way of defining $c$ is to define $a$ as the root of $g$ (near $0.237$) and then use \eqref{Eq:star} to obtain $c$.

  • Is there is a less implicit way of expressing $c$?
  • Is $c$ related to some known other known constants?

Two observations:

  1. It seems like $a$ is not so important here, in the sense that we can reparameterize $a$ and replace it by a function $z(b)$ (as long as $z$ is differntiable and goes through $0.237$ in the domain) and then have as the second equation the derivative with respect to $b$ instead of $a$. I played around with this a bit and for example $z(b):= \frac{1 -b^2}{4}$ then gives $c = \frac{8}{b^3 + b^2 + 3b + 3}$, but there might be an even better reparameterization.
  2. Instead of expressing $c$ in terms of $a$ as the solution of a quadratic equation, one can also express $a$ in terms of $c$ as the solution of a cubic equation and then substitute back into $f$ to get a function only depending on $c$. Then the number I'm looking for is a root of that function, but this function is even more ugly than the description involving $a$.
$\endgroup$
3

2 Answers 2

10
$\begingroup$

Apply Lagrange reversion to @TheSimpliFire’s equation:

$$\frac{k}{(k-1)^2}+1=e^k\iff k=1+\sqrt{\frac k{e^k-1}}\\\implies k=1+\sum_{n=1}^\infty\frac1{n!}\left.\frac{d^{n-1}}{dx^{n-1}}\left(\frac x{e^x-1}\right)^\frac n2\right|_1$$

Now use the Norlund polynomial, or generalized Bernoulli number, generating function. One notices the $\frac1{(n-m+1)!}$ truncates the inner sum:

$$\boxed{c=\frac{k^3}{k^2-k+1},k=\sum_{n=0}^\infty\sum_{m=0}^{n+1}\frac{B_n^{(\frac m2)}}{m! (n-m+1)!}}$$

shown here

$\endgroup$
6
  • $\begingroup$ Note: the $n$ and $m$ indices were switched at the end $\endgroup$ Commented Feb 17 at 23:00
  • 1
    $\begingroup$ @PeterTaylor What does the sum become then; it seems to diverge? The closest formula for the inner sum was this one, but there is an extra $(-1)^k$ factor $\endgroup$ Commented Feb 18 at 13:38
  • 1
    $\begingroup$ Simple case of misunderstanding the notation: $B_n^{(\frac m2)} \neq \sqrt{B_n}^m$. $\endgroup$ Commented Feb 18 at 23:04
  • 1
    $\begingroup$ Are there any other formulas for $k$? The only other sum found was fairly long. Maybe there is an integral representation too. $\endgroup$ Commented Feb 19 at 16:27
  • 1
    $\begingroup$ @ModsAndStaffAreNotFair I thought one comment was deleted, so another was posted. Additionally, I had no idea that that message appeared in the room. Thanks for the information. $\endgroup$ Commented Jun 29 at 13:04
12
$\begingroup$

With a few substitutions, we find that $$c=\frac{k^3}{k^2-k+1}\quad\text{where}\quad1+\frac k{(1-k)^2}=e^k.$$ The solution for $k$ requires a more advanced function than Lambert $W$.

$\endgroup$
1
  • $\begingroup$ Nice! That is already much shorter! $\endgroup$ Commented Feb 17 at 19:15

You must log in to answer this question.

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