Motivation:
Consider a game in which two shooters take turns shooting at a target. The winner is the one who manages to hit the target first. Say each shot has a relatively small chance of hitting the target, so that a large number of turns are to be expected. What is the fairest way to take turns?
The $0$-$1$ valued Thue-Morse sequence valued claims to find an answer. The sequence can be heuristically described as “taking turns taking turns taking turns...”. It is defined as follows:
Using $0$ to denote that the first player should shoot and $1$ for the second, the sequence is defined by the following iterative process - start with the string $1$. At each iteration step, append the binary complement of the string to the end. By binary complement, I mean the string obtained by turning all $1$’s in the string to $0$’s and $0$’s to $1$’s. Thus the sequence of strings starts as follows:
$1, 10, 1001, 10010110, \dots$
The Thue Morse sequence is the infinite string obtained by iterating this process. The full sequence begins:
$01101001100101101001011001101001 \dots$
Now I would like to try to quantify the sense in which this is really the fairest turn taking algorithm possible. To this end, consider the following definitions.
Definitions:
Define, for each $0$-$1$ valued sequence $\{a_n\}$ the advantage sequence $\{Va_n\}$ as follows:
$Va_n := \sum_{i = 0}^{n-1} (-1)^{a_i + 1}$
Thus $Va_n$ records at each step $n$, how many more turns player 1 has had over player 2 or vice versa.
Define now for each $k \geq 1$the k-th order advantage sequence $\{V^ka_n\}$ by
$V^1 a_n := Va_n$,
$V^ka_n := \sum_{i = 0}^{n-1} V^{k-1}a_i$ for $ k > 1$.
Intuitively, the $V^k$ can be understood as follows.
$V^1a$ records how many more turns player 1 has had (or vice versa) than player 2 thus far.
$V^2 a$ records how many more times (with multiplicity) player 1 has had more turns than player 2 thus far.
$V^3 a$ records how many more times player 1 has had more of a second order advantage than player 2 thus far.
... and so on.
Now, let us define a partial order on the set of $0$-$1$ valued sequences as follows:
$\{a_n\} ≥ \{b_n\}$ if for all $k \geq 1$, there exists some $N > 0$ such that $\sum_{i = 0}^{n} |V^k a_i| ≥ \sum_{i = 0}^{n} |V^k b_i|$ for all $n > N$.
As is customary, we say $\{a_n\} > \{b_n\}$ if $\{a_n\} ≥ \{b_n\}$ but not vice versa.
Now we are ready to state the problem.
Problem: Denote by $\{T_n\}$ the Thue-Morse sequence. Is it true that $\{T_n\} < \{a_n\}$ for any other $0$-$1$ valued sequence $\{a_n\}$ such that $a_0 = 1$? Thus the Thue-Morse sequence would be the unique turn taking sequence that minimises the long run average of the higher order advantages.
