---
# System prepended metadata

title: Desk Notes

---

# Desk Notes
Suppose $ALG$ is an algorithm, $\Pr$ is a probability distribution over input instances $i$, and $OPT(i)$ denotes the value of the optimum on instance $i$.

Suppose $\alpha = E[ALG]/E[OPT] = \sum_i \frac{\Pr(i) ALG(i)}{\Pr(i) OPT(i)}.$

Define modified probability distribution $\mu$ as $\mu(i) = Pr(i) OPT(i)/(\sum_j Pr(j) OPT(j))$.

Then in the RHS of the equation above for $\alpha$, the numerator is $\sum_i \mu(i) \cdot (ALG(i)/OPT(i))$. The denominator is 1. So we have...

$\alpha = E_{\mu}[ALG(i)/OPT(i)].$

Conclusion: if there's a distribution that makes $E[ALG]/E[OPT]$ as small as $\alpha$, there's some other distribution that makes $E[ALG/OPT]$ as small as $\alpha$.

Note the transformation from $\Pr$ to $\mu$ may not preserve the property of being a product distribution.

So this may not imply anything about gambler-to-prophet ratios for stopping sequences of random variables, for example.