论文标题
詹森（Jensen）不平等的错误方向在算法上是正确的
The wrong direction of Jensen's inequality is algorithmically right
论文作者
论文摘要
令$ \ mathcal {a} $为一种算法，其预期运行时间$ e^x $，以某些随机变量$ x $的值为条件。我们构造了一个算法$ \ Mathcal {a'} $，其中预期运行时间$ O（e^{e [x]}）$，该$完全执行$ \ Mathcal {a} $。特别是，可以将其运行时间为随机变量$ t $的算法转换为预期运行时间$ o（e^{e [\ ln t]）$的算法，它永远不会比$ o（e [t]）$更糟。对于$ \ Mathcal {a}'$构建$ x $的分布没有任何信息。
Let $\mathcal{A}$ be an algorithm with expected running time $e^X$, conditioned on the value of some random variable $X$. We construct an algorithm $\mathcal{A'}$ with expected running time $O(e^{E[X]})$, that fully executes $\mathcal{A}$. In particular, an algorithm whose running time is a random variable $T$ can be converted to one with expected running time $O(e^{E[\ln T]})$, which is never worse than $O(E[T])$. No information about the distribution of $X$ is required for the construction of $\mathcal{A}'$.
