Equitable Sequencing

The application which comes closest to my intuition for the sequence is equitable sequencing.

If two people are taking turns attempting something to see who can do it first, like flipping a coin to get heads or throwing rocks to hit a can or rolling dice to get doubles, alternating back and forth will give an advantage to the person who goes first. The first player to try might succeed on the first try, never giving the other player a shot: early attempts are more valuable than later attempts.

To compensate for this a bit the second player could go first in the second round: we could “take turns taking turns,” since earlier turns are better than later ones.

You can play with the chart to see how this improves fairness: it gets better at every event success chance, but probabilities above 50% are never going to be good with any alternating order; the best we could ever get with these is player 2 trying an infinite number of turns after player 1 makes one attempt.

One way to describe a fair turn order is to say the person with the lower probability of having won so far should take the next turn.

This solves the above 50% problem, but what happens at low event success probabilities is more interesting. As the chance of success gets lower, this sequence converges toward “taking turns at taking turns at taking turns…”

0110100110010110100101100110100110010110011010010110100110010110...

                turns of turns of turns of turns
       turns of turns of turns
  turns of turns
 2 turns  2 turns
   01       10      10     01       01     10      10     01

This is the Thue-Morse sequence. It’s interesting for a lot of reasons, the most intuitive being “Equitable Sequencing,” minimizing the advantage of being the first to choose when two parties are choosing taking turns choosing. The probability example above is a restatement of the Galois duelers problem: a fair order for alternating duelers with bad aim. A new penalty format for soccer has been introduced which uses an approximation of this sequence for shootouts

Check out Sriharsha’s post about the sequence and it’s applications. Here’s a teaser:

I would start by doing something trivial using one of my hands, say my left hand. It could be flicking, tapping, touching something, whatever, something very trivial. I would call this a. I would then do something similar with my right hand and call it b.

So as to compensate the imbalance caused in the universe due to that ghastly act a. There now, the world is at peace with itself. Is it though?

a b

a b Balanced but not fair. Discernible folks would've realized by now that it isn't fair on b though right? I mean shouldn't it get a chance to lead the sequence too?

I would therefore, repeat b and then a. We have thus arrived at

a b b a

Justice seems to have prevailed and balance in the universe is as good as ever. Maybe not, after all. I mean b is kinda relieved with the court order but it still sees some injustice that has escaped the jury's attention. 'Justice of first order schmirst order.' b sneers at you, seething with discontent. Onlookers whisper among themselves 'Utter drivel. Token justice. Pandering to the powerful. Isn't b worthy enough to lead a sequence of length four?'

I would therefore proceed ahead with baab , baab and abba and thus complete

abba baab baab abba Normally this is where it ended. gasp Slow Clap time. b is happy now guys. We did it. Look at the smile plastered on it's face. Some of you champions of the oppressed might say b isn't exactly beaming with joy but let's not get greedy and talk about justice of third order. [ abbabaabbaababba baababbaabbabaab baababbaabbabaab abbabaabbaababba ] That would be unfair on me, the attorney who took this up pro bono.

The nomenclature part came later of course. When it started, it was all about balancing it out and being fair. By fair I mean, why does a have to be chosen first before b ? So ba gets appended to ab and so on.

Other Resources

• The Fairest Sharing Sequence Ever - Matt Parker, standupmaths
• Recursive Binary Sequences of Differences
• Fair division and the Thue-Morse sequence - John D. Cook
• Avoiding chazakah with the Prouhet-Thue-Morse sequence - James Propp
• The ubiquitous Prouhet-Thue-Morse sequence
• What’s the fairest turn sequence for n players? - kram1032