Return to Answer

The Thue-Morse sequence isn't a solution when $n=8$, but it gets close. Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $14$, according to an exhaustive brute-force search, where $v_b$ denotes the expected score for the player choosing when the binary digit is $b$.

EDIT: The reverse Thue-Morse sequence do look better than the Thue-Morse sequence but is far from the fairest. The Thue-Morse sequence looks like alternating between being worse and better than the simple alternating sequence. I tabulated their scores after the fairest below, for $1 \le n \le 17$.

$$\begin{array}{rccccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1&\text{approx.}\\ \hline 2&10&5/3&3/2&1/6&0.16666\,66667\\ 3&001&5/2&7/3&1/6&0.16666\,66667\\ 4&0110&10/3&16/5&2/15&0.13333\,33333\\ 5&11010&62/15&33/8&1/120&0.00833\,33333\\ \\ 6&000011&5&5&0&0.00000\,00000\\ &001110&5&5\\ &110001&5&5\\ &111100&5&5\\ \\ 7&1000101&377/64&88/15&23/960&0.02395\,83333\\ \\ 8&00110110&61/9&27/4&1/36&0.02777\,77778\\ &10000011&61/9&27/4\\ &10001110&61/9&27/4\\ &10110001&61/9&27/4\\ &10111100&61/9&27/4\\ &11110010&61/9&27/4\\ \\ 9&011000101&245/32&574/75&7/2400&0.00291\,66667\\ \\ 10&0100110110&77/9&94/11&1/99&0.01010\,10101\\ &0110000011&77/9&94/11\\ &0110001110&77/9&94/11\\ &0110110001&77/9&94/11\\ &0110111100&77/9&94/11\\ &0111110010&77/9&94/11\\ \\ 11&00101101001&3309/350&8417/891&2369/311850&0.00759\,66009\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722&0.00479\,15048\\ &101001000011 &1481/143 &559/54 \\ &101001001110 &1481/143 &559/54 \\ &101001110001 &1481/143 &559/54 \\ &101001111100 &1481/143 &559/54 \\ &101011001001 &1481/143 &559/54 \\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200&0.00167\,02742\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 & 0.00028\,86003\\ & 00001010011110 & 1205/99 & 426/35 \\ & 00111000110110 & 1205/99 & 426/35 \\ & 00111010000011 & 1205/99 & 426/35 \\ & 00111010001110 & 1205/99 & 426/35 \\ & 01111010011010 & 1205/99 & 426/35 \\ & 00111010110001 & 1205/99 & 426/35 \\ & 00111010111100 & 1205/99 & 426/35 \\ & 00111011110010 & 1205/99 & 426/35 \\ & 10001010010101 & 1205/99 & 426/35 \\ & 10001011010110 & 1205/99 & 426/35 \\ & 10111010000101 & 1205/99 & 426/35 \\ & 11111000010110 & 1205/99 & 426/35 \\ & 11111010010001 & 1205/99 & 426/35 \\ & 11111010011100 & 1205/99 & 426/35 \\ & 10111011000110 & 1205/99 & 426/35 \\ & 11111011010010 & 1205/99 & 426/35 \\ & 10111011110100 & 1205/99 & 426/35 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -1.66666\,66667 \\ 3 & 011 & 2 & 11/4 & -0.75000\,00000 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 01101 & 15/4 & 40/9 & -0.69444\,44444 \\ 6 & 011010 & 77/15 & 34/7 & 0.27619\,04762 \\ 7 & 0110100 & 19/3 & 53/10 & 1.03333\,33333 \\ 8 & 01101001 & 234/35 & 554/81 & -0.15379\,18871 \\ 9 & 011010011 & 85/12 & 284/35 & -1.03095\,23810 \\ 10 & 0110100110 & 1639/189 & 1853/220 & 0.24923\,03992 \\ 11 & 01101001100 & 399/40 & 712/81 & 1.18487\,65432 \\ 12 & 011010011001 & 338/33 & 136/13 & -0.21911\,42191 \\ 13 & 0110100110010 & 1582/135 & 6599/616 & 1.00585\,61809 \\ 14 & 01101001100101 & 23955/2002 & 75109/6075 & -0.39808\,69336 \\ 15 & 011010011001011 & 86/7 & 713/52 & -1.42582\,41758 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 01101001100101101 & 2799/196 & 11260/729 & -1.16520\,39417 \\ \end{array}$$

$$\begin{array}{rrccr} n&\text{reverse Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 10 & 5/3 & 3/2 & 1.66666\,66667 \\ 3 & 110 & 7/3 & 5/2 & -1.66666\,66667 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 10110 & 73/18 & 21/5 & -0.14444\,44444 \\ 6 & 010110 & 91/18 & 173/35 & 0.11269\,84127 \\ 7 & 0010110 & 109/18 & 199/35 & 0.36984\,12698 \\ 8 & 10010110 & 554/81 & 234/35 & 0.15379\,18871 \\ 9 & 110010110 & 1235/162 & 269/35 & -0.06225\,74956 \\ 10 & 0110010110 & 1397/162 & 3263/385 & 0.14813\,21148 \\ 11 & 00110010110 & 1559/162 & 3567/385 & 0.35852\,17252 \\ 12 & 100110010110 & 10994/1053 & 3952/385 & 0.17571\,07090 \\ 13 & 0100110010110 & 12047/1053 & 11933/1078 & 0.37107\,24901 \\ 14 & 10100110010110 & 38761/3159 & 13011/1078 & 0.20044\,88751 \\ 15 & 110100110010110 & 41381/3159 & 14089/1078 & 0.02982\,52600 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 10110100110010110 & 849419/56862 & 136503/9163 & 0.04105\,87768 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{alternating}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -0.16666\,66667 \\ 3 & 010 & 8/3 & 17/8 & 0.54166\,66667 \\ 4 & 0101 & 25/8 & 17/5 & -0.27500\,00000 \\ 5 & 01010 & 22/5 & 61/16 & 0.58750\,00000 \\ 6 & 010101 & 77/16 & 181/35 & -0.35892\,85714 \\ 7 & 0101010 & 216/35 & 709/128 & 0.63236\,60714 \\ 8 & 01010101 & 837/128 & 439/63 & -0.42919\,14683 \\ 9 & 010101010 & 502/63 & 1867/256 & 0.67528\,52183 \\ 10 & 0101010101 & 2123/256 & 2029/231 & -0.49058\,10335 \\ 11 & 01010101010 & 2260/231 & 9285/1024 & 0.71616\,69710 \\ 12 & 010101010101 & 10309/1024 & 4553/429 & -0.54567\,08006 \\ 13 & 0101010101010 & 4982/429 & 22237/2048 & 0.75514\,34568 \\ 14 & 01010101010101 & 24285/2048 & 80141/6435 & -0.59601\,36977 \\ 15 & 010101010101010 & 86576/6435 & 414893/32768 & 0.79239\,43129 \\ 16 & 0101010101010101 & 447661/32768 & 173867/12155 & -0.64262\,51278 \\ 17 & 01010101010101010 & 186022/12155 & 948703/65536 & 0.82809\,57089 \\ \end{array}$$

Source code (in need of optimization) in GP/PARI:

f(s,b,i0,k) = { if(#s==1, s[1],
    if(b%2, sum(i=i0,#s,f(setminus(s,[s[i]]), b\2, i, k+1))/#s*(k+1),
            f(vecextract(s,"2.."), b\2, 1, 0)
    ))
};
p(b) = { if(b>1, print1(b%2); p(b\2)) };
g(n) = { d0 = n+1; s = vector(n+1,i,i-1);
    for(b = 0, 2^(n-1)-1,
        v0 = f(s,b,1,0); v1 = f(s, 2^n-1-b, 1, 0);
        if(d0 >= abs(v0-v1), d0 = abs(v0-v1); b0 = b;
            p(b0+2^n); print(" ",v0,"  ",v1,"  ",d0)
    ))
};
g(14);

Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $14$, according to an exhaustive search, where $v_b$ denotes the expected score for the player who can choose when the binary digit is $b$.

The reverse Thue-Morse sequence do look better than the Thue-Morse sequence but its score is far from the fairest. The Thue-Morse sequence looks like alternating between being worse and better than the simple alternating sequence. Their scores are tabulated farther below for $1 \le n \le 17$.

EDIT: RaphaelB4 formula allows fast computation and might lead to some other theorems. Harry also asked for the number of fairest sequences. Here they are (with $v_0\ge v_1$) for $n$ up to $28$. I don't see any pattern in them. The value $222$ for $n=23$ is striking.

$$\begin{array}{c r*{27}} n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \#&1&1&1&1&1&4&1&6&1&6&1&6&1&18&1\\ \end{array}$$

$$\begin{array}{c r*{27}} n&16&17&18&19&20&21&22&23&24&25&26&27&28\\ \#&124&2&11&2&18&1&9&222&2&3&1&72&3\\ \end{array}$$

$$\begin{array}{rccccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1&\text{approx.}\\ \hline 2&10&5/3&3/2&1/6&0.16666\,66667\\ 3&001&5/2&7/3&1/6&0.16666\,66667\\ 4&0110&10/3&16/5&2/15&0.13333\,33333\\ 5&11010&62/15&33/8&1/120&0.00833\,33333\\ \\ 6&000011&5&5&0&0.00000\,00000\\ &001110&5&5\\ &110001&5&5\\ &111100&5&5\\ \\ 7&1000101&377/64&88/15&23/960&0.02395\,83333\\ \\ 8&00110110&61/9&27/4&1/36&0.02777\,77778\\ &10000011&61/9&27/4\\ &10001110&61/9&27/4\\ &10110001&61/9&27/4\\ &10111100&61/9&27/4\\ &11110010&61/9&27/4\\ \\ 9&011000101&245/32&574/75&7/2400&0.00291\,66667\\ \\ 10&0100110110&77/9&94/11&1/99&0.01010\,10101\\ &0110000011&77/9&94/11\\ &0110001110&77/9&94/11\\ &0110110001&77/9&94/11\\ &0110111100&77/9&94/11\\ &0111110010&77/9&94/11\\ \\ 11&00101101001&3309/350&8417/891&2369/311850&0.00759\,66009\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722&0.00479\,15048\\ &101001000011 &1481/143 &559/54 \\ &101001001110 &1481/143 &559/54 \\ &101001110001 &1481/143 &559/54 \\ &101001111100 &1481/143 &559/54 \\ &101011001001 &1481/143 &559/54 \\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200&0.00167\,02742\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 & 0.00028\,86003\\ & 00001010011110 & 1205/99 & 426/35 \\ & 00111000110110 & 1205/99 & 426/35 \\ & 00111010000011 & 1205/99 & 426/35 \\ & 00111010001110 & 1205/99 & 426/35 \\ & 01111010011010 & 1205/99 & 426/35 \\ & 00111010110001 & 1205/99 & 426/35 \\ & 00111010111100 & 1205/99 & 426/35 \\ & 00111011110010 & 1205/99 & 426/35 \\ & 10001010010101 & 1205/99 & 426/35 \\ & 10001011010110 & 1205/99 & 426/35 \\ & 10111010000101 & 1205/99 & 426/35 \\ & 11111000010110 & 1205/99 & 426/35 \\ & 11111010010001 & 1205/99 & 426/35 \\ & 11111010011100 & 1205/99 & 426/35 \\ & 10111011000110 & 1205/99 & 426/35 \\ & 11111011010010 & 1205/99 & 426/35 \\ & 10111011110100 & 1205/99 & 426/35 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -1.66666\,66667 \\ 3 & 011 & 2 & 11/4 & -0.75000\,00000 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 01101 & 15/4 & 40/9 & -0.69444\,44444 \\ 6 & 011010 & 77/15 & 34/7 & 0.27619\,04762 \\ 7 & 0110100 & 19/3 & 53/10 & 1.03333\,33333 \\ 8 & 01101001 & 234/35 & 554/81 & -0.15379\,18871 \\ 9 & 011010011 & 85/12 & 284/35 & -1.03095\,23810 \\ 10 & 0110100110 & 1639/189 & 1853/220 & 0.24923\,03992 \\ 11 & 01101001100 & 399/40 & 712/81 & 1.18487\,65432 \\ 12 & 011010011001 & 338/33 & 136/13 & -0.21911\,42191 \\ 13 & 0110100110010 & 1582/135 & 6599/616 & 1.00585\,61809 \\ 14 & 01101001100101 & 23955/2002 & 75109/6075 & -0.39808\,69336 \\ 15 & 011010011001011 & 86/7 & 713/52 & -1.42582\,41758 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 01101001100101101 & 2799/196 & 11260/729 & -1.16520\,39417 \\ \end{array}$$

$$\begin{array}{rrccr} n&\text{reverse Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 10 & 5/3 & 3/2 & 1.66666\,66667 \\ 3 & 110 & 7/3 & 5/2 & -1.66666\,66667 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 10110 & 73/18 & 21/5 & -0.14444\,44444 \\ 6 & 010110 & 91/18 & 173/35 & 0.11269\,84127 \\ 7 & 0010110 & 109/18 & 199/35 & 0.36984\,12698 \\ 8 & 10010110 & 554/81 & 234/35 & 0.15379\,18871 \\ 9 & 110010110 & 1235/162 & 269/35 & -0.06225\,74956 \\ 10 & 0110010110 & 1397/162 & 3263/385 & 0.14813\,21148 \\ 11 & 00110010110 & 1559/162 & 3567/385 & 0.35852\,17252 \\ 12 & 100110010110 & 10994/1053 & 3952/385 & 0.17571\,07090 \\ 13 & 0100110010110 & 12047/1053 & 11933/1078 & 0.37107\,24901 \\ 14 & 10100110010110 & 38761/3159 & 13011/1078 & 0.20044\,88751 \\ 15 & 110100110010110 & 41381/3159 & 14089/1078 & 0.02982\,52600 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 10110100110010110 & 849419/56862 & 136503/9163 & 0.04105\,87768 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{alternating}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -0.16666\,66667 \\ 3 & 010 & 8/3 & 17/8 & 0.54166\,66667 \\ 4 & 0101 & 25/8 & 17/5 & -0.27500\,00000 \\ 5 & 01010 & 22/5 & 61/16 & 0.58750\,00000 \\ 6 & 010101 & 77/16 & 181/35 & -0.35892\,85714 \\ 7 & 0101010 & 216/35 & 709/128 & 0.63236\,60714 \\ 8 & 01010101 & 837/128 & 439/63 & -0.42919\,14683 \\ 9 & 010101010 & 502/63 & 1867/256 & 0.67528\,52183 \\ 10 & 0101010101 & 2123/256 & 2029/231 & -0.49058\,10335 \\ 11 & 01010101010 & 2260/231 & 9285/1024 & 0.71616\,69710 \\ 12 & 010101010101 & 10309/1024 & 4553/429 & -0.54567\,08006 \\ 13 & 0101010101010 & 4982/429 & 22237/2048 & 0.75514\,34568 \\ 14 & 01010101010101 & 24285/2048 & 80141/6435 & -0.59601\,36977 \\ 15 & 010101010101010 & 86576/6435 & 414893/32768 & 0.79239\,43129 \\ 16 & 0101010101010101 & 447661/32768 & 173867/12155 & -0.64262\,51278 \\ 17 & 01010101010101010 & 186022/12155 & 948703/65536 & 0.82809\,57089 \\ \end{array}$$

The Thue-Morse sequence isn't a solution when $n=8$, but it gets close. Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $13$, according to an exhaustive brute-force search, where $v_b$ denotes the expected score for the player choosing when the binary digit is $b$.

EDIT: added $n=14$ and its $18$ fairest sequences with $v_0\ge v_1$.

$$\begin{array}{rcccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1\\ \hline 2&10&5/3&3/2&1/6\\ 3&001&5/2&7/3&1/6\\ 4&0110&10/3&16/5&2/15\\ 5&11010&62/15&33/8&1/120\\ \\ 6&000011&5&5&0\\ &001110&5&5&0\\ &110001&5&5&0\\ &111100&5&5&0\\ \\ 7&1000101&377/64&88/15&23/960\\ \\ 8&00110110&61/9&27/4&1/36\\ &10000011&61/9&27/4&1/36\\ &10001110&61/9&27/4&1/36\\ &10110001&61/9&27/4&1/36\\ &10111100&61/9&27/4&1/36\\ &11110010&61/9&27/4&1/36\\ \\ 9&011000101&245/32&574/75&7/2400\\ \\ 10&0100110110&77/9&94/11&1/99\\ &0110000011&77/9&94/11&1/99\\ &0110001110&77/9&94/11&1/99\\ &0110110001&77/9&94/11&1/99\\ &0110111100&77/9&94/11&1/99\\ &0111110010&77/9&94/11&1/99\\ \\ 11&00101101001&3309/350&8417/891&2369/311850\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722\\ &101001000011 &1481/143 &559/54 &37/7722\\ &101001001110 &1481/143 &559/54 &37/7722\\ &101001110001 &1481/143 &559/54 &37/7722\\ &101001111100 &1481/143 &559/54 &37/7722\\ &101011001001 &1481/143 &559/54 &37/7722\\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 \\ & 00001010011110 & 1205/99 & 426/35 & 1/3465 \\ & 00111000110110 & 1205/99 & 426/35 & 1/3465 \\ & 00111010000011 & 1205/99 & 426/35 & 1/3465 \\ & 00111010001110 & 1205/99 & 426/35 & 1/3465 \\ & 01111010011010 & 1205/99 & 426/35 & 1/3465 \\ & 00111010110001 & 1205/99 & 426/35 & 1/3465 \\ & 00111010111100 & 1205/99 & 426/35 & 1/3465 \\ & 00111011110010 & 1205/99 & 426/35 & 1/3465 \\ & 10001010010101 & 1205/99 & 426/35 & 1/3465 \\ & 10001011010110 & 1205/99 & 426/35 & 1/3465 \\ & 10111010000101 & 1205/99 & 426/35 & 1/3465 \\ & 11111000010110 & 1205/99 & 426/35 & 1/3465 \\ & 11111010010001 & 1205/99 & 426/35 & 1/3465 \\ & 11111010011100 & 1205/99 & 426/35 & 1/3465 \\ & 10111011000110 & 1205/99 & 426/35 & 1/3465 \\ & 11111011010010 & 1205/99 & 426/35 & 1/3465 \\ & 10111011110100 & 1205/99 & 426/35 & 1/3465 \\ \end{array}$$

Source code (in need of optimisation) in GP/PARI:

f(s,b,i0,k) = { if(#s==1, s[1],
    if(b%2, sum(i=i0,#s,f(setminus(s,[s[i]]), b\2, i, k+1))/#s*(k+1),
            f(vecextract(s,"2.."), b\2, 1, 0)
    ))
};
p(b) = { if(b>1, print1(b%2); p(b\2)) };
g(n) = { d0 = n+1; s = vector(n+1,i,i-1);
    for(b = 0, 2^(n-1)-1,
        v0 = f(s,b,1,0); v1 = f(s, 2^n-1-b, 1, 0);
        if(d0 >= abs(v0-v1), d0 = abs(v0-v1); b0 = b;
            p(b0+2^n); print(" ",v0,"  ",v1,"  ",d0)
    ))
};

g(14);

The Thue-Morse sequence isn't a solution when $n=8$, but it gets close. Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $14$, according to an exhaustive brute-force search, where $v_b$ denotes the expected score for the player choosing when the binary digit is $b$.

EDIT: The reverse Thue-Morse sequence do look better than the Thue-Morse sequence but is far from the fairest. The Thue-Morse sequence looks like alternating between being worse and better than the simple alternating sequence. I tabulated their scores after the fairest below, for $1 \le n \le 17$.

$$\begin{array}{rccccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1&\text{approx.}\\ \hline 2&10&5/3&3/2&1/6&0.16666\,66667\\ 3&001&5/2&7/3&1/6&0.16666\,66667\\ 4&0110&10/3&16/5&2/15&0.13333\,33333\\ 5&11010&62/15&33/8&1/120&0.00833\,33333\\ \\ 6&000011&5&5&0&0.00000\,00000\\ &001110&5&5\\ &110001&5&5\\ &111100&5&5\\ \\ 7&1000101&377/64&88/15&23/960&0.02395\,83333\\ \\ 8&00110110&61/9&27/4&1/36&0.02777\,77778\\ &10000011&61/9&27/4\\ &10001110&61/9&27/4\\ &10110001&61/9&27/4\\ &10111100&61/9&27/4\\ &11110010&61/9&27/4\\ \\ 9&011000101&245/32&574/75&7/2400&0.00291\,66667\\ \\ 10&0100110110&77/9&94/11&1/99&0.01010\,10101\\ &0110000011&77/9&94/11\\ &0110001110&77/9&94/11\\ &0110110001&77/9&94/11\\ &0110111100&77/9&94/11\\ &0111110010&77/9&94/11\\ \\ 11&00101101001&3309/350&8417/891&2369/311850&0.00759\,66009\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722&0.00479\,15048\\ &101001000011 &1481/143 &559/54 \\ &101001001110 &1481/143 &559/54 \\ &101001110001 &1481/143 &559/54 \\ &101001111100 &1481/143 &559/54 \\ &101011001001 &1481/143 &559/54 \\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200&0.00167\,02742\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 & 0.00028\,86003\\ & 00001010011110 & 1205/99 & 426/35 \\ & 00111000110110 & 1205/99 & 426/35 \\ & 00111010000011 & 1205/99 & 426/35 \\ & 00111010001110 & 1205/99 & 426/35 \\ & 01111010011010 & 1205/99 & 426/35 \\ & 00111010110001 & 1205/99 & 426/35 \\ & 00111010111100 & 1205/99 & 426/35 \\ & 00111011110010 & 1205/99 & 426/35 \\ & 10001010010101 & 1205/99 & 426/35 \\ & 10001011010110 & 1205/99 & 426/35 \\ & 10111010000101 & 1205/99 & 426/35 \\ & 11111000010110 & 1205/99 & 426/35 \\ & 11111010010001 & 1205/99 & 426/35 \\ & 11111010011100 & 1205/99 & 426/35 \\ & 10111011000110 & 1205/99 & 426/35 \\ & 11111011010010 & 1205/99 & 426/35 \\ & 10111011110100 & 1205/99 & 426/35 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -1.66666\,66667 \\ 3 & 011 & 2 & 11/4 & -0.75000\,00000 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 01101 & 15/4 & 40/9 & -0.69444\,44444 \\ 6 & 011010 & 77/15 & 34/7 & 0.27619\,04762 \\ 7 & 0110100 & 19/3 & 53/10 & 1.03333\,33333 \\ 8 & 01101001 & 234/35 & 554/81 & -0.15379\,18871 \\ 9 & 011010011 & 85/12 & 284/35 & -1.03095\,23810 \\ 10 & 0110100110 & 1639/189 & 1853/220 & 0.24923\,03992 \\ 11 & 01101001100 & 399/40 & 712/81 & 1.18487\,65432 \\ 12 & 011010011001 & 338/33 & 136/13 & -0.21911\,42191 \\ 13 & 0110100110010 & 1582/135 & 6599/616 & 1.00585\,61809 \\ 14 & 01101001100101 & 23955/2002 & 75109/6075 & -0.39808\,69336 \\ 15 & 011010011001011 & 86/7 & 713/52 & -1.42582\,41758 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 01101001100101101 & 2799/196 & 11260/729 & -1.16520\,39417 \\ \end{array}$$

$$\begin{array}{rrccr} n&\text{reverse Thue-Morse}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 10 & 5/3 & 3/2 & 1.66666\,66667 \\ 3 & 110 & 7/3 & 5/2 & -1.66666\,66667 \\ 4 & 0110 & 10/3 & 16/5 & 0.13333\,33333 \\ 5 & 10110 & 73/18 & 21/5 & -0.14444\,44444 \\ 6 & 010110 & 91/18 & 173/35 & 0.11269\,84127 \\ 7 & 0010110 & 109/18 & 199/35 & 0.36984\,12698 \\ 8 & 10010110 & 554/81 & 234/35 & 0.15379\,18871 \\ 9 & 110010110 & 1235/162 & 269/35 & -0.06225\,74956 \\ 10 & 0110010110 & 1397/162 & 3263/385 & 0.14813\,21148 \\ 11 & 00110010110 & 1559/162 & 3567/385 & 0.35852\,17252 \\ 12 & 100110010110 & 10994/1053 & 3952/385 & 0.17571\,07090 \\ 13 & 0100110010110 & 12047/1053 & 11933/1078 & 0.37107\,24901 \\ 14 & 10100110010110 & 38761/3159 & 13011/1078 & 0.20044\,88751 \\ 15 & 110100110010110 & 41381/3159 & 14089/1078 & 0.02982\,52600 \\ 16 & 0110100110010110 & 44540/3159 & 127340/9163 & 0.20220\,33021 \\ 17 & 10110100110010110 & 849419/56862 & 136503/9163 & 0.04105\,87768 \\ \end{array}$$

$$\begin{array}{rlccr} n&\text{alternating}&v_0&v_1&v_0-v_1 \text{ approx.}\\ \hline 1 & 0 & 1 & 1/2 & 0.50000\,00000 \\ 2 & 01 & 3/2 & 5/3 & -0.16666\,66667 \\ 3 & 010 & 8/3 & 17/8 & 0.54166\,66667 \\ 4 & 0101 & 25/8 & 17/5 & -0.27500\,00000 \\ 5 & 01010 & 22/5 & 61/16 & 0.58750\,00000 \\ 6 & 010101 & 77/16 & 181/35 & -0.35892\,85714 \\ 7 & 0101010 & 216/35 & 709/128 & 0.63236\,60714 \\ 8 & 01010101 & 837/128 & 439/63 & -0.42919\,14683 \\ 9 & 010101010 & 502/63 & 1867/256 & 0.67528\,52183 \\ 10 & 0101010101 & 2123/256 & 2029/231 & -0.49058\,10335 \\ 11 & 01010101010 & 2260/231 & 9285/1024 & 0.71616\,69710 \\ 12 & 010101010101 & 10309/1024 & 4553/429 & -0.54567\,08006 \\ 13 & 0101010101010 & 4982/429 & 22237/2048 & 0.75514\,34568 \\ 14 & 01010101010101 & 24285/2048 & 80141/6435 & -0.59601\,36977 \\ 15 & 010101010101010 & 86576/6435 & 414893/32768 & 0.79239\,43129 \\ 16 & 0101010101010101 & 447661/32768 & 173867/12155 & -0.64262\,51278 \\ 17 & 01010101010101010 & 186022/12155 & 948703/65536 & 0.82809\,57089 \\ \end{array}$$

Source code (in need of optimization) in GP/PARI:

f(s,b,i0,k) = { if(#s==1, s[1],
    if(b%2, sum(i=i0,#s,f(setminus(s,[s[i]]), b\2, i, k+1))/#s*(k+1),
            f(vecextract(s,"2.."), b\2, 1, 0)
    ))
};
p(b) = { if(b>1, print1(b%2); p(b\2)) };
g(n) = { d0 = n+1; s = vector(n+1,i,i-1);
    for(b = 0, 2^(n-1)-1,
        v0 = f(s,b,1,0); v1 = f(s, 2^n-1-b, 1, 0);
        if(d0 >= abs(v0-v1), d0 = abs(v0-v1); b0 = b;
            p(b0+2^n); print(" ",v0,"  ",v1,"  ",d0)
    ))
};
g(14);

EDIT: added $n=12$ and $13$ and improved the source code by saving $k!$ terms for $k$ consecutive random strikes.

The Thue-Morse sequence isn't a solution when $n=8$, but it gets close. Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $13$, according to an exhaustive brute-force search, where $v_b$ denotes the expected score for the player choosing when the binary digit is $b$.

$$\begin{array}{rcccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1\\ \hline 2&10&5/3&3/2&1/6\\ 3&001&5/2&7/3&1/6\\ 4&0110&10/3&16/5&2/15\\ 5&11010&62/15&33/8&1/120\\ \\ 6&000011&5&5&0\\ &001110&5&5&0\\ &110001&5&5&0\\ &111100&5&5&0\\ \\ 7&1000101&377/64&88/15&23/960\\ \\ 8&00110110&61/9&27/4&1/36\\ &10000011&61/9&27/4&1/36\\ &10001110&61/9&27/4&1/36\\ &10110001&61/9&27/4&1/36\\ &10111100&61/9&27/4&1/36\\ &11110010&61/9&27/4&1/36\\ \\ 9&011000101&245/32&574/75&7/2400\\ \\ 10&0100110110&77/9&94/11&1/99\\ &0110000011&77/9&94/11&1/99\\ &0110001110&77/9&94/11&1/99\\ &0110110001&77/9&94/11&1/99\\ &0110111100&77/9&94/11&1/99\\ &0111110010&77/9&94/11&1/99\\ \\ 11&00101101001&3309/350&8417/891&2369/311850\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722\\ &101001000011 &1481/143 &559/54 &37/7722\\ &101001001110 &1481/143 &559/54 &37/7722\\ &101001110001 &1481/143 &559/54 &37/7722\\ &101001111100 &1481/143 &559/54 &37/7722\\ &101011001001 &1481/143 &559/54 &37/7722\\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200\\ \end{array}$$

Source code (in need of optimisation) in GP/PARI:

f(s,b,i0,k) = { if(#s==1, s[1],
    if(b%2, sum(i=i0,#s,f(setminus(s,[s[i]]), b\2, i, k+1))/#s*(k+1),
            f(vecextract(s,"2.."), b\2, 1, 0)
    ))
};
p(b) = { if(b>1, print1(b%2); p(b\2)) };
g(n) = { d0 = n+1; s = vector(n+1,i,i-1);
    for(b = 0, 2^(n-1)-1,
        v0 = f(s,b,1,0); v1 = f(s, 2^n-1-b, 1, 0);
        if(d0 >= abs(v0-v1), d0 = abs(v0-v1); b0 = b;
            p(b0+2^n); print(" ",v0,"  ",v1,"  ",d0)
    ))
};

g(13);

The Thue-Morse sequence isn't a solution when $n=8$, but it gets close. Here are the fairest sequences with $v_0\ge v_1$ for small $n = $ $1,$ $2,$ $\dots,$ $13$, according to an exhaustive brute-force search, where $v_b$ denotes the expected score for the player choosing when the binary digit is $b$.

EDIT: added $n=14$ and its $18$ fairest sequences with $v_0\ge v_1$.

$$\begin{array}{rcccc} n&\text{fairest with }v_0\ge v_1&v_0&v_1&v_0-v_1\\ \hline 2&10&5/3&3/2&1/6\\ 3&001&5/2&7/3&1/6\\ 4&0110&10/3&16/5&2/15\\ 5&11010&62/15&33/8&1/120\\ \\ 6&000011&5&5&0\\ &001110&5&5&0\\ &110001&5&5&0\\ &111100&5&5&0\\ \\ 7&1000101&377/64&88/15&23/960\\ \\ 8&00110110&61/9&27/4&1/36\\ &10000011&61/9&27/4&1/36\\ &10001110&61/9&27/4&1/36\\ &10110001&61/9&27/4&1/36\\ &10111100&61/9&27/4&1/36\\ &11110010&61/9&27/4&1/36\\ \\ 9&011000101&245/32&574/75&7/2400\\ \\ 10&0100110110&77/9&94/11&1/99\\ &0110000011&77/9&94/11&1/99\\ &0110001110&77/9&94/11&1/99\\ &0110110001&77/9&94/11&1/99\\ &0110111100&77/9&94/11&1/99\\ &0111110010&77/9&94/11&1/99\\ \\ 11&00101101001&3309/350&8417/891&2369/311850\\ \\ 12&101000001101 &1481/143 &559/54 &37/7722\\ &101001000011 &1481/143 &559/54 &37/7722\\ &101001001110 &1481/143 &559/54 &37/7722\\ &101001110001 &1481/143 &559/54 &37/7722\\ &101001111100 &1481/143 &559/54 &37/7722\\ &101011001001 &1481/143 &559/54 &37/7722\\ \\ 13&0110100111010 &2534/225 &13873/1232 &463/277200\\ \\ 14& 00001010010011 & 1205/99 & 426/35 & 1/3465 \\ & 00001010011110 & 1205/99 & 426/35 & 1/3465 \\ & 00111000110110 & 1205/99 & 426/35 & 1/3465 \\ & 00111010000011 & 1205/99 & 426/35 & 1/3465 \\ & 00111010001110 & 1205/99 & 426/35 & 1/3465 \\ & 01111010011010 & 1205/99 & 426/35 & 1/3465 \\ & 00111010110001 & 1205/99 & 426/35 & 1/3465 \\ & 00111010111100 & 1205/99 & 426/35 & 1/3465 \\ & 00111011110010 & 1205/99 & 426/35 & 1/3465 \\ & 10001010010101 & 1205/99 & 426/35 & 1/3465 \\ & 10001011010110 & 1205/99 & 426/35 & 1/3465 \\ & 10111010000101 & 1205/99 & 426/35 & 1/3465 \\ & 11111000010110 & 1205/99 & 426/35 & 1/3465 \\ & 11111010010001 & 1205/99 & 426/35 & 1/3465 \\ & 11111010011100 & 1205/99 & 426/35 & 1/3465 \\ & 10111011000110 & 1205/99 & 426/35 & 1/3465 \\ & 11111011010010 & 1205/99 & 426/35 & 1/3465 \\ & 10111011110100 & 1205/99 & 426/35 & 1/3465 \\ \end{array}$$

Source code (in need of optimisation) in GP/PARI:

f(s,b,i0,k) = { if(#s==1, s[1],
    if(b%2, sum(i=i0,#s,f(setminus(s,[s[i]]), b\2, i, k+1))/#s*(k+1),
            f(vecextract(s,"2.."), b\2, 1, 0)
    ))
};
p(b) = { if(b>1, print1(b%2); p(b\2)) };
g(n) = { d0 = n+1; s = vector(n+1,i,i-1);
    for(b = 0, 2^(n-1)-1,
        v0 = f(s,b,1,0); v1 = f(s, 2^n-1-b, 1, 0);
        if(d0 >= abs(v0-v1), d0 = abs(v0-v1); b0 = b;
            p(b0+2^n); print(" ",v0,"  ",v1,"  ",d0)
    ))
};

g(14);