Skip to main content
Became Hot Network Question
edited tags
Link
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88
used \label and \eqref to refer to the equation (\star) with MathJax
Source Link

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)} \quad (\star)$$$$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 $(\star)$\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$.

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)} \quad (\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 $(\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$.

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$.
Source Link
Moritz Firsching
  • 10.7k
  • 3
  • 63
  • 88

Nicer expression for 2.1369288...?

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)} \quad (\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 $(\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$.