display | more...

An infinite sequence of s and 1s, defined in any of the following (equivalent) ways. In each case, an obvious "limit" exists (and can be made rigorous), which is the Morse sequence

  1. Write down a 0. Then, at each stage, copy the previous stage's word, then copy it "inverted", switching 0's and 1's.
  2. Define a morphism by
    0 → 01
    1 → 10
    
    and extend it to words; now repeatedly apply it to the word "0".

In each case, the same sequence is obtained:

0
01
0110
01101001
0110100110010110
...

This sequence is aperiodic, but still strongly recurrent.


Method 2 above is an example of an L-system which converges to a single limit.

Thue-Morse sequence as a fair-share sequence

Let’s suppose a simple game that I’ll call The Greed Game: there’s several coins (gil) on the table. The rules are simple: we take turns and we may take one gil. You and me taking one turn will be defined as a round.

Is this a fair game? It is, as long as we keep playing full rounds. At the end of each round we both have one gil, so it doesn’t matter who goes first.

Let’s also imagine what I’ll call The Weighed Greed Game. It’s almost the same as before, but this time instead of single coins, there are piles of coins. To keep it simple, let’s imagine the piles have 1, 2, 3, 4, 5, 6, 7 and 8 gil. The game is the same: Andy and Bob take turns, but this time we can take one and only one pile of gil.

I’ll go first.I take 8 gil. What do you do?

You’ll probably take the pile with 7 gil. Then I’ll take 6… and you can see where this is going. At the end, I have 20 gil and you have 16.

This seems unfair, right? At the beginning of each round, I always take the largest pile, leaving you with the second largest. Wouldn’t it be better if we took turns being the first each round?

1 A regular 4-turn order

Let’s try again, with a smaller example: only 4 piles—with 1, 2, 3 and 4 gil—, but this time we take turns being the first in a round. In other words, the turn order is now Andy, Bob, Bob, Andy (ABBA for short)

I’ll take 4, you’ll likely take 3; now it’s your turn again, so you’ll likely take 2 and I’ll take 1. final score: we both have 5 gil. Fair division!

So we can just repeat this algorithm to divide 8 coins equally, right? Let’s see what happens with 8 coins:

  • A takes 8
  • B takes 7
  • B takes 6
  • A takes 5
  • A takes 4
  • B takes 3
  • B takes 2
  • A takes 1

Total: 18 gil for A; 18 gil for B. Hooray! This works and we can go home, right?

2 The long run

However, this works under the assumption that we always play full rounds. Moreover, our 4-turn strategy only works perfectly if the number of turns is a multiple of 4—in other words, if the number of rounds is even—and still has a bias that favors the Player A for reasons that I will demonstrate later.

Suppose that we play the Greed Game—or the Weighed Greed Game— with piles of 1, 2, …, 23 and 24 gil. But this time there’s the extra catch that I can cut the game short at any turn. What’s the most fair turn order?

Let’s keep a running score with both strategies. The score is as follows:

  • Every time Andy has more money, it will be worth 1 point to the score
  • Every time there’s a tie, it will be worth 0 points
  • Every time Bob has more money, it will be worth -1 points

This way, a fair turn order should end up with a score of 0 (or close to it). Let’s see how our game starts, assuming we have 24 piles of gil.

The regular turn order goes as follows:

Turn A’s wealth B’s wealth Turn score Running average score
0 24 0 1 1.0
1 24 23 1 1.0
2 46 23 1 1.0
3 46 44 1 1.0
4 66 44 1 1.0
5 66 63 1 1.0
6 84 63 1 1.0
7 84 80 1 1.0
8 100 80 1 1.0
9 100 95 1 1.0
10 114 95 1 1.0
11 114 108 1 1.0
12 126 108 1 1.0
13 126 119 1 1.0
14 136 119 1 1.0
15 136 128 1 1.0
16 144 128 1 1.0
17 144 135 1 1.0
18 150 135 1 1.0
19 150 140 1 1.0
20 154 140 1 1.0
21 154 143 1 1.0
22 156 143 1 1.0
23 156 144 1 1.0

No surprises here. The regular order always gives an advantage to the first player and from the table, it’s evident that Andy will always have more gil. What happens with the 4-turn order?

Turn A’s wealth B’s wealth Turn score Running average score
0 24 0 1 1.0
1 24 23 1 1.0
2 24 45 -1 0.3333333333333333
3 45 45 0 0.25
4 65 45 1 0.4
5 65 64 1 0.5
6 65 82 -1 0.2857142857142857
7 82 82 0 0.25
8 98 82 1 0.3333333333333333
9 98 97 1 0.4
10 98 111 -1 0.2727272727272727
11 111 111 0 0.25
12 123 111 1 0.3076923076923077
13 123 122 1 0.35714285714285715
14 123 132 -1 0.26666666666666666
15 132 132 0 0.25
16 140 132 1 0.29411764705882354
17 140 139 1 0.3333333333333333
18 140 145 -1 0.2631578947368421
19 145 145 0 0.25
20 149 145 1 0.2857142857142857
21 149 148 1 0.3181818181818182
22 149 150 -1 0.2608695652173913
23 150 150 0 0.25

Immediately we can see that this is better, but there’s a catch: notice how the average score is always positive and seems to tend to 0.25. Look at the third column for a hint: in any four consecutive turns, Andy wins two, B wins one and they are tied in one. This order, while better, still gives Andy an edge. Can we do better?

3 Thue-Morse Sequence

Why not extend the idea of taking turns in taking turns? As we’ve seen, using only the 4-turn order gives an advantage to Andy. What if every 4 turns the 4-turn is reversed? This way, we could get an 8-turn order… but using it could also be unfair, right? why not then take the 8-turn order and reverse it after 8 turns? And then after 16 turns…

You get the idea of how this goes. In general, we can always construct a fair sequence by taking the sequence so far and reversing it. In essence, doing this forever will give us the Thue-Morse sequence. But, how does it fare against the other strategies?

Turn A’s wealth B’s wealth Turn score Running average score
0 24 0 1 1.0
1 24 23 1 1.0
2 24 45 -1 0.3333333333333333
3 45 45 0 0.25
4 45 65 -1 0.0
5 64 65 -1 -0.16666666666666666
6 82 65 1 0.0
7 82 82 0 0.0
8 82 98 -1 -0.1111111111111111
9 97 98 -1 -0.2
10 111 98 1 -0.09090909090909091
11 111 111 0 -0.08333333333333333
12 123 111 1 0.0
13 123 122 1 0.07142857142857142
14 123 132 -1 0.0
15 132 132 0 0.0
16 132 140 -1 -0.058823529411764705
17 139 140 -1 -0.1111111111111111
18 145 140 1 -0.05263157894736842
19 145 145 0 -0.05
20 149 145 1 0.0
21 149 148 1 0.045454545454545456
22 149 150 -1 0.0
23 150 150 0 0.0

This is way better. Look at the last column: now there’s three things to notice:

  1. The running average is sometimes positive and sometimes negative, which means Andy doesn’t always have the advantage;
  2. There are many zeroes, which means there are many (cutting) points at which the whole sequence is fair; and
  3. The absolute values of the running average get smaller and smaller and tend toward zero, meaning that the longer this sequence goes, the most likely it is to be fair at any one point.

So, what gives? The Thue-Morse sequence is thus a fair(-er) way of “taking turns” if we don’t know ahead of time how long the game will go on. the Weighed game serves to illustrate a situation that may be encountered in many situations in life: there’s a limited resource to draw from and being first matters. With two parties vying to get it, the Thue-Morse sequence offers a first approach as to how to allocate that resource in a fair way.


You can see my amateurish code and illustrative graphics by pointing your browser to this jupyter notebook and watching it, maybe even running it in your own home Python console (numpy and matplotlib required)


🜞⚔️⚔️⚔️⚔️⚔️

Log in or register to write something here or to contact authors.