Uniform van Lambalgen's theorem fails for computable randomness (Q2304533): Difference between revisions

It is not possible to have a successful strategy in a game of chance. However, formalizing this statement is not easy, even for simple situations when the outcome of a game is determined by a (potentially infinite) sequence \(a_1a_2\ldots a_n\ldots\) of truly random bits: head or tail, red or black, etc. The usual formalization takes into account that the gambler starts with some amount of money. The gambler can stop after each \(n\); in this case, he/she will have the amount of money \(f(a_1\ldots a_n)\). Instead of taking this amount, the gambler can ask for one more cycle, with values \(f(a_1\ldots a_n0)\ge 0\) and \(f(a_1\ldots a_n1)\ge 0\) whose mathematical expectation \((f(a_1\ldots a_n0)+ f(a_1\ldots a_n1))/2\) is equal to the current amount. The resulting function \(f(a)\) from finite binary sequences to non-negative real numbers is known as a \textit{martingale}. For each gambling strategy (i.e., for each computable martingale \(f(a)\)), if a sequence \(\{a_i\}\) is truly random, then, while the gambler may earn some money, we do not expect the gambler with finite initial funds to be earning an unlimited amount of money -- so all the amounts \(f(a_1\ldots a_n)\) should be bounded. This idea underlies one of the natural definitions of randomness: an infinite sequence \(a_1a_2\ldots\) is \textit{computably random} if for each computable martingale \(f(a)\), the set of all the values \(f(a_1\ldots a_n)\) is bounded. This paper provides an unexpected counter-intuitive example of a sequence in which odd bits are computably random, even bits are computably random relative to the odd bits, but the whole sequence is not computably random: it has a martingale allowing infinitely increasing wins! Such examples are impossible if we use other definitions of randomness; so maybe computable randomness does not fully capture our intuitive idea of randomness? From the technical viewpoint, this paper's example is very subtle -- e.g., if we also require that odd bits are computably random relative to even bits, then the whole sequence is always computably random.