I'm interested in whether Levin and Solomonoff's results on "universal semimeasures" can be extended to other settings. One case that especially interests me is finding "universal" strategies in the one-player game "guess the next bit, win 1 dollar if you're right, lose 1 dollar if you're wrong" played over infinite (and possibly uncomputable) bit sequences. Obviously any deterministic strategy (whether computable or incomputable) can be humiliated by an input sequence that makes it always guess wrong, so I shifted my attention to computable randomized strategies. Here's a formalization:

The question

Let's define a "supermartingale with bounded increments" (SWBI) as a function M on finite bit sequences S that satisfies the following conditions:

1) M(empty sequence) = 0

2) for any S, (M(S#0) + M(S#1))/2 ≤ M(S)

3) for any S, M(S#0) - M(S) ≤ 1 and M(S#1) - M(S) ≤ 1

Question 1: does the set of all lower-semicomputable SWBIs contain an element X that dominates any other element Y up to an additive constant (which may depend on Y but doesn't depend on S)?

Question 2: if the answer to question 1 is "no", is there a lower-semicomputable SWBI that doesn't lose to any other by more than epsilon per step?

Partial result that may be helpful

Multiplicative weights over all lower-semicomputable SWBIs yields an SWBI that fits the conditions of question 2, but I don't know if it's lower-semicomputable, though it is certainly limit-computable.


(Note: It is very possible I misunderstood the questions.)

By $X$ dominates $Y$ up to an additive constant, do you mean $X,Y$ are supermartingales with bounded increments, and $X(S)>Y(S)-C$ for some constant $C$ and all finite bit-strings $S$? If so, the answer to the first question is no.

Consider $M$ that "always bets on 1", i.e. $M(S0)=M(S)-1$ and $M(S1)=M(S)+1$, and $N$ which "always bets on 0", i.e. $N(S0)=N(S)+1$ and $N(S1)=N(S)-1$. Then $M(S)$ is the number of 1's in $S$ minus the number of 0's in $S$. Similarly, $N(S)$ is the opposite.

There is no supermartingale starting at 0 (with bounded increments or not, computable or otherwise) that can dominate both of them simultaneously up to additive constants. Let $L$ be the submartingale $L(S)=\max(M(S),N(S))$. It is known that the expected value $\sum_{length(S)=n} L(S)/2^n$ goes to $\infty$ as $n$ grows. (In short, it is because random walks are not $L^1$-bounded.)

However any supermartingale $K$ which dominates $M,N$ up to a constant $C$, must also dominate $L$ up to the same constant. But the expected value of any such supermartingale starting at $0$ is $\sum_{length(S)=n} K(S)/2^n =0$, hence $0=\sum_{length(S)=n} K(S)/2^n \geq \sum_{length(S)=n} (L(S)-C)/2^n=-C+\sum_{length(S)=n} L(S)/2^n$ which is a contradiction since the RHS goes to $\infty$ as $n$ grows.

I am not sure what you mean by question 2, but I think the answer is also no.

Let me know if I misunderstood the question.

  • $\begingroup$ You certainly haven't misunderstood the question. I'm embarrassed that I didn't think of this argument myself. Thanks! As for question 2, it means finding an X such that X(S) > Y(S) - C - epsilon*length(S) for a given epsilon > 0. $\endgroup$ – Vladimir Slepnev Mar 17 '11 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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