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$
4
  • $\begingroup$ Note: the $n$ and $m$ indices were switched at the end $\endgroup$ 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$ Feb 18 at 13:38
  • 1
    $\begingroup$ Simple case of misunderstanding the notation: $B_n^{(\frac m2)} \neq \sqrt{B_n}^m$. $\endgroup$ 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$ Feb 19 at 16:27
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$ Feb 17 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.