Oracle Induction Proofs

post by Diffractor · 2018-11-28T08:12:38.306Z · LW · GW · 0 comments

Contents

  Notation: 
    Runtime Analysis:
None
No comments

Notation:

$\{0,1{\}}^L$ and $\{0,1{\}}^{\ast }$ are the sets of all bitstrings of length $L,$ and the set of all finite bitstrings, respectively. Elements of these sets are denoted by $x$. The length $i$ prefix of $x$ is denoted by $x_{:i}$.

$B_L$ is the set of all satisfiable booleans with all variables having an index $\le L$, and $B^{}$ is the set of all satisfiable booleans. Similarly, $B_{\ast L}$ and $B_{\ast }$ are the set of all booleans with all variables having an index $\le L$, and the set of all booleans. Elements of these sets are denoted by $B$. $B\wedge B^{\prime }$ is also a boolean. Bitstrings $x$ may be interpreted as boolean constraints saying that the prefix of the bitstring must equal $x$.

$f$ is a function $N^{+}\to N^{+}$ that is time-constructible, monotonically increasing, and $f\left(t\right)>t$, which gives the runtime bound for traders.

$l$ is some function $N^{+}\to N^{+}$ upper-bounded by $2^{f\left(t\right)}$ that is time-constructible, monotonically increasing, and $l\left(t\right)>t$. It gives the most distant bit the oracle inductor thins about on turn $t$.

$d$ is the function $N^{+}\to N^{+}$ given by $d\left(t\right)=l\left(t\right)+\lceil {\log }_{2}l\left(t\right)\rceil +2t+7$, giving the number of iterations of binary-search deployed on turn $t$.

$\delta$ is the function $N^{+}\to [0,1]\cup Q$ given by $\delta \left(t\right)=2^{-(t+3)}$. It gives the proportion of the inductor distribution that is made up by the uniform distribution.

The operations $\text{query(A,p)}$ and $\text{flip(p)}$ take unit time to execute in our model of computation, though the input still has to be written down in the usual amount of time.

Given some arbitrary distribution $\Delta$ over $\{0,1{\}}^L$, and a $B\in B_{\ast L}$, $\Delta \left(B\right)$ is the probability mass assigned to bitstrings that fulfill $B$. Given a $B\in B_L$, ${\Delta }_B$ is the conditional distribution given by ${\Delta }_B\left(x\right)=\frac{\Delta (B\wedge x)}{\Delta \left(B\right)}$. ${\Delta }_B^{\ast }$ is the distribution induced by $\text{Approx(}\Delta \text{,L,D,B)}$. There is an implicit dependence on $D$ which will be suppressed in the notation.

Lemma 1 (n-Lemma): Let $ϵ=2^{-D}$. Given some distribution $\Delta$ over $\{0,1{\}}^L$ for which $\forall x\in \{0,1{\}}^L:\Delta (x)\ge nϵ$, then

$\forall B\in B_L,x\in \{0,1{\}}^L:{\left(\frac{n-1}{n+1}\right)}^L{\Delta }_B(x)\le {\Delta }_B^{\ast }(x)\le {\left(\frac{n+1}{n-1}\right)}^L{\Delta }_B(x)$ .

To begin with, if $x$ is incompatible with $B$, ${\Delta }_B^{\ast }\left(x\right)=0$ by the construction of $\text{Approx}$, and the inequality is trivial. So we can consider the case where $x$ is compatible with $B$. Given $\sigma$ as a strict prefix of $x$, abbreviate $\text{NextBit(}\Delta \text{,L,D,}|\sigma |+1\text{,B,}\sigma )$ as $NB\left(\sigma \right)$.

Because we're using a binary-search depth of $D$ on each bit, and taking the average of the interval, the probabilities are approximated to within $\frac{ϵ}{2}$.

$\frac{\Delta (B\wedge \sigma 1)-ϵ}{\Delta (B\wedge \sigma )+ϵ}<\frac{\Delta (B\wedge \sigma 1)-\frac{ϵ}{2}}{\Delta (B\wedge \sigma )+\frac{ϵ}{2}}\le P\left(NB\right(\sigma )=1)\le \frac{\Delta (B\wedge \sigma 1)+\frac{ϵ}{2}}{\Delta (B\wedge \sigma )-\frac{ϵ}{2}}<\frac{\Delta (B\wedge \sigma 1)+ϵ}{\Delta (B\wedge \sigma )-ϵ}$

Taking the midle three terms and subtracting $1$ from all of them, which flips the sign of the inequality, and rewriting $1-P\left(NB\right(\sigma )=1)$ as $P\left(NB\right(\sigma )=0)$ and rewriting $1$ as $\frac{\Delta (B\wedge \sigma )\pm \frac{ϵ}{2}}{\Delta (B\wedge \sigma )\pm \frac{ϵ}{2}}$, we get

$\frac{\Delta (B\wedge \sigma )-ϵ}{\Delta (B\wedge \sigma )+ϵ}<\frac{\Delta (B\wedge \sigma )-\frac{ϵ}{2}}{\Delta (B\wedge \sigma )-\frac{ϵ}{2}}-\frac{\Delta (B\wedge \sigma 1)+\frac{ϵ}{2}}{\Delta (B\wedge \sigma )-\frac{ϵ}{2}}\le P\left(NB\right(\sigma )=0)\le \frac{\Delta (B\wedge \sigma )+\frac{ϵ}{2}}{\Delta (B\wedge \sigma )+\frac{ϵ}{2}}-\frac{\Delta (B\wedge \sigma 1)-\frac{ϵ}{2}}{\Delta (B\wedge \sigma )+\frac{ϵ}{2}}<\frac{\Delta (B\wedge \sigma )+ϵ}{\Delta (B\wedge \sigma )-ϵ}$

Now, because ${\Delta }_B^{\ast }\left(x\right)={\prod }_{i=1}^{L}P\left(NB\right(x_{:i-1})=x_i)$, using the previous inequalities, we can establish

${\prod }_{i=1}^L\frac{\Delta (B\wedge x_{:i})-ϵ}{\Delta (B\wedge x_{:i-1})+ϵ}<{\Delta }_B^{\ast }\left(x\right)<{\prod }_{i=1}^L\frac{\Delta (B\wedge x_{:i})+ϵ}{\Delta (B\wedge x_{:i-1})-ϵ}$

For an individual term in the product of the lower/upper bound ($\pm$ and $\mp$ will be used, the upper sign is used for the lower bound, the lower sign is used for the upper bound, and $⋛$ will be abused to mean $\ge$ for the lower bound and $\le$ for the upper bound), we can get the following equality.

$\frac{\Delta (B\wedge x_{:i})\mp ϵ}{\Delta (B\wedge x_{:i-1})\pm ϵ}=\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})\pm ϵ}\mp \frac{ϵ}{\Delta (B\wedge x_{:i-1})\pm ϵ}=\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})}\frac{\Delta (B\wedge x_{:i-1})}{\Delta (B\wedge x_{:i-1})\pm ϵ}(1\mp \frac{ϵ}{\Delta (B\wedge x_{:i-1})})$

Because, by assumption, all bitstrings with nonzero probability and therefore prefixes of them have probability bounded below by $nϵ$, we get

$\frac{\Delta (B\wedge x_{:i-1})}{\Delta (B\wedge x_{:i-1})\pm ϵ}⋛\frac{nϵ}{nϵ\pm ϵ}=\frac{n}{n\pm 1}$ and $1\mp \frac{ϵ}{\Delta (B\wedge x_{:i-1})}⋛1\mp \frac{ϵ}{nϵ}=1\mp \frac{1}{n}=\frac{n\mp 1}{n}$

which can be applied to conclude

$\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})}\frac{\Delta (B\wedge x_{:i-1})}{\Delta (B\wedge x_{:i-1})\pm ϵ}(1\mp \frac{ϵ}{\Delta (B\wedge x_{:i-1})})⋛\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})}\frac{n}{n\pm 1}\frac{n\mp 1}{n}=\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})}\frac{n\mp 1}{n\pm 1}$

Therefore, since we have lower-bounded or upper-bounded every term in the product, and $\Delta (B\wedge x_{:L})=\Delta (B\wedge x)=\Delta \left(x\right)$, we can show

${\Delta }_B^{\ast }\left(x\right)\gtrless {\prod }_{i=1}^L\frac{\Delta (B\wedge x_{:i})\mp ϵ}{\Delta (B\wedge x_{:i-1})\pm ϵ}⋛{\prod }_{i=1}^L\frac{\Delta (B\wedge x_{:i})}{\Delta (B\wedge x_{:i-1})}\frac{n\mp 1}{n\pm 1}=\frac{\Delta \left(x\right)}{\Delta \left(B\right)}{\left(\frac{n\mp 1}{n\pm 1}\right)}^L={\Delta }_B\left(x\right){\left(\frac{n\mp 1}{n\pm 1}\right)}^L$

The n-Lemma is thus proven.

Lemma 2: The distribution induced by $\text{OI(t)}$ has the probability of all bitstrings bounded above by $nϵ$.

Identify $D$ with $d\left(t\right)=l\left(t\right)+\lceil {\log }_{2}l\left(t\right)\rceil +2t+7$. Identify $L$ with $l\left(t\right)$. Identify $n$ with $l\left(t\right)2^{t+4}$.

Because $ϵ=2^{-D}$, $ϵ=2^{-\left(l\right(t)+\lceil {\log }_{2}l(t)\rceil +2t+7)}\le \frac{1}{l\left(t\right)}{2}^{-\left(l\right(t)+2t+7)}$. Due to $\delta \left(t\right)$ of the distribution being composed of the uniform distribution, the probability of all $x$ is bounded below by

$\delta \left(t\right)2^{-L}=2^{-(t+3)}{2}^{-l\left(t\right)}=l\left(t\right)2^{t+4}\frac{1}{l\left(t\right)}{2}^{-\left(l\right(t)+2t+7)}\ge nϵ$

And Lemma 2 is proved.

From here on, we will frequently be going from the approximation of a conditional distribution to a conditional distribution via the n-Lemma and Lemma 2, so let ${ϵ}_t=2^{-d\left(t\right)}$, and $n_t=l\left(t\right)2^{t+4}$, and $L_t=l\left(t\right)$. ${\Delta }^i$ and ${\Delta }_B^i$ will be used to refer to the probability distribution and conditional probability distribution over bitstrings that $\text{OI(i)}$ produces, and ${\Delta }^{\ast i}$ and ${\Delta }_B^{\ast i}$ refer to the approximation of that probability distribution with $D=d\left(t\right)$.

Lemma 3: The assessed value at time $t$ in world $x$ of a trader $T$ with a runtime and oracle-call filter attached is lower-bounded by

$-t+{\sum }_{1\le i\le t}\frac{max\left({\left(\frac{n_t-1}{n_t+1}\right)}^{L_t}{\sum }_{B\in B_{L_t}}\right(P(T^i=B){\Delta }_B^i\left(x\right))-{ϵ}_t,0)}{{\Delta }^i\left(x\right)+{ϵ}_t}$ and upper-bounded by

$-t+{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}{\sum }_{1\le i\le t}\frac{{\sum }_{B\in B_{L_t}}P(T^i=B){\Delta }_B^i\left(x\right)}{{\Delta }^i\left(x\right)}$ .

To begin, the assessed value at time $t$ in world $x$ of a trader $T$ by $\text{OverBudget}$ is $-t+{\sum }_{1\le i\le t}\frac{\left({\sum }_{B\in B_{L_t}}\right(P(T^i=B){\Delta }_B^{\ast i}\left(x\right)){)}^{\ast }}{{\Delta }^{\ast i}\left(x\right)}$ .

${\Delta }^{\ast i}\left(x\right)$ has $d\left(t\right)$ rounds of binary search run on it, which yields an interval with a width of ${ϵ}_t$, and an upper-bound estimate is taken, so ${\Delta }^i\left(x\right)\le {\Delta }^{\ast i}\left(x\right)\le {\Delta }^i\left(x\right)+{ϵ}_t$. Similarly, the net value of a trade has a lower-bound estimate run on it, so

${\sum }_{B\in B_{L_t}}\left(P\right(T^i=B\left){\Delta }_B^{\ast i}\right(x\left)\right)-{ϵ}_t\le \left({\sum }_{B\in B_{L_t}}P\right(T^i=B\left){\Delta }_B^{\ast i}\right(x){)}^{\ast }\le {\sum }_{B\in B_{L_t}}P(T^i=B\left){\Delta }_B^{\ast i}\right(x)$

Further, by the n-Lemma and Lemma 2 (probability of x is either $0$ or over $n_t{ϵ}_t$), we can replace ${\Delta }_B^{\ast i}\left(x\right)$ by ${\left(\frac{n_t+1}{n_t-1}\right)}^{L_i}{\Delta }_B^i\left(x\right)$ or ${\left(\frac{n_t-1}{n_t+1}\right)}^{L_i}{\Delta }_B^i\left(x\right)$ respectively, which are then upper and lower-bounded by ${\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}{\Delta }_B^i\left(x\right)$ and ${\left(\frac{n_t-1}{n_t+1}\right)}^{L_t}{\Delta }_B^i\left(x\right)$, which, because the fraction doesn't depend on $i$, can be pulled out of the sum, yielding the stated bounds.

In the next theorem, we will be abbreviating ${\sum }_{B\in B_{l\left(i\right)}}P(T^i=B){\Delta }_B^i\left(x\right)$ as $a_i$ and abbreviating ${\Delta }^i\left(x\right)$ as $c_i$, so the value of a trader at timestep $t$ in world $x$ against the sequence of $\text{OI}$ distributions is $-t+{\sum }_{1\le i\le t}\frac{a_i}{c_i}$.

Theorem 1: If a trader exploits the market, there is a budgeted version that trader that exploits the market.

As before, the net value of a trader at timestep $t$ in world $x$ against the sequence of $\text{OI}$ distributions is $-t+{\sum }_{1\le i\le t}\frac{a_i}{c_i}$. Because the trader exploits the market, for all $t$ and all $x$ plausible at $t$, the net value $\ge -b$ for some integer constant $b$, we get that for all t and all $x$ plausible at $t$, ${\sum }_{1\le i\le t}\frac{a_i}{c_i}\ge t-b$. Call this quantity the gain of the trader. Separate the sum into "good" days where $a_i\ge t{ϵ}_t$, and "bad" days where this is false, and use Lemma 2 to get

${\sum }_{good}\frac{a_i}{c_i}\ge t-b-{\sum }_{bad}\frac{a_i}{c_i}>t-b-t\frac{t{ϵ}_t}{n_t{ϵ}_t}\ge t-b-t^2{2}^{-(t+4)}>t-b-\frac{5}{64}$

Abbreviate ${\left(\frac{n_t-1}{n_t+1}\right)}^{L_t}$ as $y_t$, and abbreviate ${\left(\frac{n_t-1}{n_t+1}\right)}^{L_t+1}$ as $z_t$. Using Lemma 3, the worst-case assessed gain of the trader is $\ge {\sum }_{1\le i\le t}\frac{max(y_t{a}_i-{ϵ}_t,0)}{c_i+{ϵ}_t}\ge {\sum }_{good}\frac{y_t{a}_i-{ϵ}_t}{c_i+{ϵ}_t}$. Focusing on an individual day, and using the fact that $c_i\ge n_t{ϵ}_t$, and it's a good day so $a_i\ge t{ϵ}_t$, we get

$\frac{y_t{a}_i-{ϵ}_t}{c_i+{ϵ}_t}=\frac{c_i}{c_i+{ϵ}_t}\frac{a_i}{c_i}(y_t-\frac{{ϵ}_t}{a_i})>\frac{n_t}{n_t+1}(y_t-\frac{1}{t})\frac{a_i}{c_i}>(\frac{n_t-1}{n_t+1}{y}_t-\frac{1}{t})\frac{a_i}{c_i}=(z_t-\frac{1}{t})\frac{a_i}{c_i}$

Substituting this into the sum and pulling out terms that don't depend on $i$, we get

${\sum }_{good}\frac{y_t{a}_i-{ϵ}_t}{c_i+{ϵ}_t}>(z_t-\frac{1}{t}){\sum }_{good}\frac{a_i}{c_i}>(z_t-\frac{1}{t})(t-b-\frac{5}{64})>t{z}_t-b-\frac{5}{64}-1$

The last step was done by $z_t<1$ and ignoring some positive terms. Now we will bound $t{z}_t$.

$(L_t+1){\int }_{n_t-1}^{n_t+1}\frac{dx}{x}<\frac{2(L_t+1)}{n_t-1}\le \frac{8L_t}{n_t}=2^{-(t+1)}\le \frac{1}{4t}<{\int }_{t-1/4}^t\frac{dx}{x}$

Multiplying both sides by $-1$, which flips the upper and lower bounds of integration, we get

$\ln \left({\left(\frac{n_t-1}{n_t+1}\right)}^{L_t+1}\right)=(L_t+1)\left(\ln \right(n_t-1)-\ln (n_t+1\left)\right)=(L_t+1){\int }_{n_t+1}^{n_t-1}\frac{dx}{x}>{\int }_t^{t-1/8}\frac{dx}{x}=\ln (t-1/4)-\ln \left(t\right)=\ln \left(\frac{t-1/4}{t}\right)=\ln (1-\frac{1/4}{t})$

By putting both sides in an exponent, this inequality is equivalent to ${\left(\frac{n_t-1}{n_t+1}\right)}^{L_t+1}>1-\frac{1/4}{t}$. Multiplying both sides by $t$ and using the definition of $z_t$, we get $t{z}_t>t-\frac{1}{4}$.

Using the previous inequalities, we get that the worst-case assessed gain of the trader is greater than $t-b-\frac{1}{4}-\frac{5}{64}-1=t-b-\frac{85}{64}$. Therefore, the worst-case assessed value of the trader is greater than $-b-\frac{85}{64}$, so when the budget is $b+3$, $\text{OverBudget}$ will at worst evaluate the value as $-b-\frac{85}{64}>-(b+3)+1$, so it will never return $1$ and interfere with the trade, so the budgeted trader makes the same trades as the original trader and exploits the market.

Lemma 4: The worst-case value of a trader with a budget of $b$ is $\ge -b-1/4$.

Assume the value of a trader equals $-b$ for some $b\in R^{\ge 0}$ on some turn $t$. Then the gain of the trader, ${\sum }_{1\le i\le t}\frac{a_i}{c_i}$ is $\le t-b$. By Lemma 3, the assessed gain is less than

${\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}{\sum }_{1\le i\le t}\frac{a_i}{c_i}={\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}(t-b)<t{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}-b$

Now we will bound the last term.

$\ln \left({\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}\right)=L_t\left(\ln \right(n_t+1)-\ln (n_t-1\left)\right)=L_t{\int }_{n_t-1}^{n_t+1}\frac{dx}{x}<\frac{2L_t}{n_t-1}\le \frac{4L_t}{n_t}=2^{-(t+2)}\le \frac{1/4}{t+1}<\frac{1/4}{t+1/4}<{\int }_t^{t+1/4}\frac{dx}{x}=\ln (t+1/4)-\ln \left(t\right)=\ln \left(\frac{t+1/4}{t}\right)=\ln (1+\frac{1/4}{t})$

By putting both sides in an exponent, we get the equivalent inequality ${\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}<1+\frac{1/4}{t}$ and multiplying both sides by $t$ yields $t{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}<t+1/4$, so the assessed gain is less than $t-b+1/4$ and the assessed value is $\le -b+1/4$.

Then, if the trader has a budget of $b$ (an integer), the worst-case scenario is that on some turn t it has a true value of $-b+3/4$ and it is assessed to have a value of $-b+1$ (maximum possible), so it barely passes the budgeting filter, and then loses $1$ dollar on the next turn, getting a final value of $-b-1/4$ (after which it only outputs $B_{\top }$ which has a value of $0$).

Theorem 2: If a budgeted trader exploits the market, the supertrader exploits the market.

$P_i(A\wedge b)=P_i\left(A\right)P_i\left(b\right)$ is the probability of the supertrader drawing a bitstring $a$ which encodes the algorithm $A$ and budget $b$ on timestep $i$. $P(A_b^i=B)$ is the probability of $A\left(i\right)$ with a runtime and oracle call filter and a budget filter of $b$ outputting the boolean $B$. $P\left(A\right)$ is the probability of a randomly selected infinite string encoding $A$, and $P\left(b\right)=2^{-b}$. For sufficiently large $i$, $P_i\left(A\right)=P\left(A\right)$ and $P_i\left(b\right)=P\left(b\right)$.

A useful thing to note is that, because the bitstring $a$ that is chosen is of length $f\left(t\right)$, and it is only run on the UTM for $f\left(t\right)$ steps, its behavior is identical to that of all algorithms that are encoded by a bitstring that has $a$ as a prefix. Therefore, even though the probability of some $A$ being drawn may be $0$ on a timestep, there is some amount of probability mass in the supertrader that might as well have come from $A$, in the sense that its behavior is indistinguishable from $A$ after the runtime and oracle call filter is applied.

Similarly, because the maximum selectable budget is $f\left(t\right)$, and a trader can lose at most $1$ dollar each turn, for all $A$ and positive integers $c$, $A_{f\left(i\right)}^i$ has the same exact behavior as $A_{f\left(i\right)+c}^i$, so we can pretend we are dealing with the full distribution over all budgets.

Therefore, for all $i$, the distribution over satisfiable booleans given by ${\sum }_{A,b}{P}_i(A\wedge b)P(A_b^i=B)$ equals the distribution over satisfiable booleans given by ${\sum }_{A,b}P\left(A\right)P\left(b\right)P(A_b^i=B)$, and because of this,

$\forall i\forall x\in \{0,1{\}}^{L_i}:{\sum }_{A,b}{P}_i(A\wedge b\left){\sum }_{B\in B_{L_i}}P\right(A_b^i=B\left){\Delta }_B^i\right(x)={\sum }_{A,b}P(A\left)2^{-b}{\sum }_{B\in B_{L_i}}P\right(A_b^i=B\left){\Delta }_B^i\right(x)$

Also, let $V_i\left(A_b\right)$ be the value of $A\left(i\right)$'s trade on day $i$ according to some fixed $x$. $V_{\le i}\left(A_b\right)$ is the value that $A_b$ accumulates over all days up to $t$.

The value of the supertrader at time $t$ according to a world $x$ that is plausible at that time is

${\sum }_{1\le i\le t}(-1+\frac{{\sum }_{A,b}{P}_i(A\wedge b){\sum }_{B\in B_{L_i}}P(A_b^i=B){\Delta }_B^i\left(x\right)}{{\Delta }^i\left(x\right)})={\sum }_{1\le i\le t}{\sum }_{A,b}P\left(A\right)2^{-b}(-1+\frac{{\sum }_{B\in B_{L_i}}P(A_b^i=B){\Delta }_B^i\left(x\right)}{{\Delta }^i\left(x\right)})={\sum }_{1\le i\le t}{\sum }_{A,b}P\left(A\right)2^{-b}{V}_i\left(A_b\right)={\sum }_{A,b}P\left(A\right)2^{-b}{V}_{\le t}\left(A_b\right)$

Now the worst-case value of $V_{\le t}\left(A_b\right)$ is $-b-\frac{1}{4}$ by Lemma 4, so we get that the value of the supertrader is bounded below by

${\sum }_{A}P\left(A\right){\sum }_b{2}^{-b}(-b-1/4)=\frac{-9}{4}{\sum }_{A}P\left(A\right)=\frac{-9}{4}$.

Also, if our exploiting trader and the budget which ensures its trade is never altered are $T$ and $b^{\prime }$, we get that the value of the supertrader equals

$\sum _{A,b}P\left(A\right)2^{-b}{V}_{\le t}\left(A_b\right)=P\left(A\right)2^{-b^{\prime }}{V}_{\le t}\left(T_{b^{\prime }}\right)+\sum _{A,b\ne T,b^{\prime }}P\left(A\right)2^{-b}{V}_{\le t}\left(A_b\right)>P\left(A\right)2^{-b^{\prime }}{V}_{\le t}\left(T_{b^{\prime }}\right)-\frac{9}{4}$

Because $V_{\le t}\left(T_{b^{\prime }}\right)$ is unbounded above for appropriate choices of $t$ and $x$ by assumption, it continues to be unbounded above when multiplied by $P\left(A\right)2^{-b^{\prime }}$ and has $\frac{9}{4}$ subtracted from it. Therefore, the supertrader has plausible value unbounded above as well.

Theorem 3: The supertrader doesn't exploit $\text{OI}$.

Now, we will show that the maximum value that the supertrader can possibly get in worlds plausible at some turn $t$ is upper-bounded by $2^{-t}$, so the value of the supertrader is upper-bounded by $1$.

To begin with, the probability mass the supertrader places on world $x$ at timestep $t$ is ${\sum }_{A,b}P\left(A\right)2^{-b}{\sum }_{B\in B}P(A_b^t=B){\Delta }_B\left(x\right)$. This sum can be rewritten as ${\sum }_{B\in B}{\Delta }_B\left(x\right){\sum }_{A,b}P\left(A\right)2^{-b}P(A_b^t=B)$, and for brevity, from here on, we will abbreviate ${\sum }_{A,b}P\left(A\right)2^{-b}P(A_b^t=B)$ as $P_t\left(B\right)$. With this abbreviation, we can express the value of the supertrader's trade on day $t$ and world $x$ as $\frac{{\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B\left(x\right)}{\delta \left(t\right)2^{-L_t}+(1-\delta (t\left)\right){\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B^{\ast }\left(x\right)}-1$. Note that the numerator of the fraction is the supertrader, which uses the true conditional distribution, while the denominator is what the actual distribution is composed of, a small fragment of a uniform distribution with the rest is composed of a mixture of approximations to the appropriate conditional distribution. To begin the bounding argument, apply the n-Lemma to yield

$\frac{{\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B\left(x\right)}{\delta \left(t\right)2^{-L_t}+(1-\delta (t\left)\right){\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B^{\ast }\left(x\right)}-1<\frac{{\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B\left(x\right)}{(1-\delta (t\left)\right){\left(\frac{n_t-1}{n_t+1}\right)}^{L_t}{\sum }_{B\in B}{P}_t\left(B\right){\Delta }_B\left(x\right)}-1=\frac{{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}}{1-\delta \left(t\right)}-1$

Also,

$\ln \left({\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}\right)-\ln (1-\delta (t\left)\right)=L_t\left(\ln \right(n_t+1)-\ln (n_t-1\left)\right)-\ln (1-\delta (t\left)\right)+\ln \left(1\right)=L_t{\int }_{n_t-1}^{n_t+1}\frac{dx}{x}+{\int }_{1-\delta \left(t\right)}^1\frac{dx}{x}<\frac{2L_t}{n_t-1}+\frac{\delta \left(t\right)}{1-\delta \left(t\right)}<\frac{4L_t}{n_t}+2\delta \left(t\right)=2^{-(t+2)}+2^{-(t+2)}=2^{-(t+1)}<\frac{2^{-t}}{1+2^{-t}}<{\int }_1^{1+2^{-t}}\frac{dx}{x}=\ln (1+2^{-t})-\ln \left(1\right)=\ln (1+2^{-t})$

By putting both sides in an exponent, this inequality is equivalent to $\frac{{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}}{1-\delta \left(t\right)}<1+2^{-t}$, so $\frac{{\left(\frac{n_t+1}{n_t-1}\right)}^{L_t}}{1-\delta \left(t\right)}-1<2^{-t}$, so the value of the supertrader gained on any given day is bounded above by $2^{-t}$, so the total value of the supertrader at any time is bounded above by $1$.

Runtime Analysis:

The strength of the bounded reflective oracle needed is controlled by the longest runtime of the algorithms that the oracle is queried about. The relevant oracle calls are the invocations of SAT in $\text{NextBit}$, $\text{eval(B',OI(t))}$ in the binary search portion of $\text{NextBit}$, $\text{OverBudget}$, the SAT call in $\text{TradeToBool}$, the $\text{eval(B,OI(i))}$ calls that the trader may make, and the oracle calls in the binary search portion of $\text{OverBudget}$.

To begin with, the runtime of $\text{eval(B,x)}$ is the time needed to flip enough coins to get to the most distant variable index in $B$ (call it $n$), and then the time to run the boolean circuit on the padded $x$ itself, which would be be $O(n\cdot |B|)$, to check each bit of the padded $x$ and do a pass over the boolean to substitute $\top$ or $\perp$ for that variable, and then evaluating the resulting boolean with variables filled in.

Similarly, the runtime of SAT is the time to write down $B$ and the binary string corresponding to the probability bound, which has a length of approximately $n$, for a runtime of $O(n+|B|)$.

Now we can look at the runtime of $\text{BinSearch}$. It is always called with $D=d\left(t\right)=O\left(l\right(t\left)\right),$ and there are that many iterations of writing down $\Delta$ (which, everywhere it's invoked, takes less than $d\left(t\right)$ bits) and the average of the two bounds, which, by a suitable binary encoding, takes at most about $d\left(t\right)$ bits, so we get a runtime of about $d(t{)}^2$, which is $O\left(l\right(t{)}^2)$.

As for the runtime of $\text{NextBit}$, the length of the boolean at the start is at most $f\left(t\right)+O\left(l\right(t\left)\right)$ (the first part is because $B$ was returned by an algorithm that ran for at most $f\left(t\right)$ steps, and the second part is the bound on the length of $x$). A boolean of this length is written down 3 times, and SAT is invoked twice, and $\text{BinSearch}$ is run twice, for a runtime of $O\left(3\right(f\left(t\right)+l\left(t\right))+2(l\left(t\right)+f\left(t\right)+l\left(t\right))+2l(t{)}^2)=O(f\left(t\right)+l\left(t{)}^2\right)$ . Adding in the time to write in/read $B$ and $x$ from the input just adds another $f\left(t\right)+l\left(t\right)$ term which doesn't affect runtime that much.

Now for $\text{Approx}$. There are at most $l\left(t\right)$ iterations of $\text{NextBit}$, and we already accounted for the time to write the input to $\text{NextBit}$, so the runtime is $O\left(f\right(t\left)l\right(t)+l(t{)}^3)$.

$\text{TradeToBool}$ reads the input, which takes $O\left(f\right(t\left)\right)$ time, emulates $f\left(t\right)$ steps of a turing machine, which takes $O\left(f\right(t\left)\log f\right(t\left)\right)$ time, clips the input which takes $O\left(f\right(t)+l(t\left)\right)$ time (the latter is an upper bound on the time to compute $l\left(t\right)$ because $l$ is time-constructible), calls SAT on a boolean of length at most $f\left(t\right)$ with a maximum index of $l\left(t\right)$, and writes the boolean, for a runtime of $O\left(f\right(t\left)\log f\right(t)+l(t\left)\right)$.

$\text{BTtoBool}$ reads the input and writes parts of it into the query, which takes $O\left(f\right(t\left)\right)$ time, writes down the probability bound in $O\left(l\right(t\left)\right)$ time, and runs $\text{TradeToBool}$, for a runtime of $O\left(f\right(t\left)\log f\right(t)+l(t\left)\right)$.

$\text{OI}$ either writes down $\delta \left(t\right)$ in $O\left(t\right)$ time and generates a string in $O\left(l\right(t\left)\right)$ time, or computes $f\left(t\right)$, $l\left(t\right)$, and $d\left(t\right)$ in $O\left(f\right(t)+l(t\left)\right)$ time, generates the trader and budget string in $O\left(f\right(t\left)\right)$ time, and invokes $\text{TradeToBool}$ and $\text{Approx}$ for a runtime of $O\left(l\right(t{)}^3+f\left(t\right)l\left(t\right)+f\left(t\right)\log f\left(t\right))$ .

Now we can address the runtime of all the algorithms fed into an oracle query but one. The SAT calls in $\text{NextBit}$ ask about $\text{eval(B',}\lambda )$ with a runtime of $O\left(l\right(t)+f(t\left)\right)$, which is sufficiently low. The queries about $\text{eval(B',OI(t))}$ in $\text{BinSearch}$ have $\text{eval(B',OI(t))}$ running in $O\left(l\right(t{)}^2)$ time (for the evaluation) plus $O\left(l\right(t{)}^3+f\left(t\right)l\left(t\right)+f\left(t\right)\log f\left(t\right))$ time (to calculate $\text{OI(t)}$), so the runtime is $O\left(l\right(t{)}^3+f\left(t\right)l\left(t\right)+f\left(t\right)\log f\left(t\right))$ which is sufficiently low. The SAT call in $\text{TradeToBool}$ asks about $\text{eval(B,}\lambda )$ with a runtime of $O\left(l\right(t)+f(t\left)\right)$ which is sufficiently low. The SAT call the trader makes about $\text{eval(B,OI(i))}$ isn't about a longer-running algorithm than the algorithm invoked in $\text{BinSearch}$, so we're good there as well. Finally, the oracle queries in the binary search portion of $\text{OverBudget}$ take $O\left(l\right(t{)}^2)$ time (for the evaluation), plus the runtime of $\text{Approx}$ and the runtime of $\text{TradeToBool}$ (in the numerator) or the runtime of $\text{OI}$ (in the denominator), for a runtime of $O\left(l\right(t{)}^3+f\left(t\right)l\left(t\right)+f\left(t\right)\log f\left(t\right))$ in both cases, which is sufficiently low.

This just leaves establishing the runtime of $\text{OverBudget}$ to ensure that the oracle is strong enough for our needs.

Generating $n$ takes $O\left(t\right)$ time. Generating the world $x$ takes $O\left(l\right(t\left)\right)$ time. Running the deductive process takes $O\left(f\right(t)+l(t\left)\right)$ time, and so does writing down the resulting boolean, and the maximum index is $l\left(t\right)$ so the SAT invocation takes $O\left(f\right(t)+l(t\left)\right)$ time as well, for a runtime so far of $O\left(f\right(t)+l(t\left)\right)$. That leaves the sum (computing the < isn't harder than computing the sum in the first place). We are carrying out at most $t$ fraction-additions. Each fraction-addition involves three multiplications, one addition, and two iterations of binary search. The length of the numbers is $l\left(t\right)$, but with each multiplication, they get longer by $l\left(t\right)$, so the maximum length of the numbers is $tl\left(t\right)$. Using the standard inefficient multiplication algorithm for $O\left(t^{2}l\right(t{)}^2)$ runtime per multiplication, and with addition being faster than multiplication, we get $O\left(t\right(t^{2}l(t{)}^2+l(t{)}^2\left)\right)=O\left(t^{3}l\right(t{)}^2)$ for the whole sum, to get a runtime of $O\left(t^{3}l\right(t{)}^2+f\left(t\right))$, which again is sufficiently low to permit oracle calls.

Thus, an oracle strength of $O\left(l\right(t{)}^3+t^{3}l(t{)}^2+f(t\left)l\right(t)+f(t\left)\log f\right(t\left)\right)$ suffices to make all oracle calls directed to algorithms with permissibly low runtime.

0 comments

Comments sorted by top scores.