Dueling Dilettantes

[This is post #4 in a series on the Thue-Morse sequence. See posts #1, #2, and #3.]

What? You don’t agree that the Thue-Morse sequence is awesome? OK, there’s only one way to settle this dispute: I challenge you to a duel. This unfortunately might take a while, because we both have terrible aim.

Let’s say we both have the same probability $$p=.2$$ of hitting our target on any given shot, and the first to hit is the winner. I’ll even be gracious and let you go first, and I’ll shoot second. In the first two shots of the game, the probability that you win (i.e., hit your first shot) is $$p=.2$$, and the probability that I win (i.e., you miss and then I hit) is $$(1-p)\cdot p = .16$$. (In the remaining probability $$1-.2-.16=.64$$, the duel continues.) This means that you are more likely to win during the first two shots than I am, so it should only be fair that I take the third shot!

How do the probabilities look in the first three shots? Your chances of winning are still $$p=.2$$, while mine are $$(1-p)\cdot p + (1-p)^2\cdot p = .288$$ because I might win on the second or third shot. Now it seems that I have the advantage, so you should take the 4th shot in the interest of fairness. Let’s continue like this, choosing to give the 5th shot to the theoretical underdog from the first 4 rounds, the 6th shot to the underdog in the first 5 rounds, and so on.

You can (and should!) check that the shot order will be Y, M, M, Y, M, Y, Y, M, M, Y,  M, Y, Y, M, M, Y, ..., where Y=You and M=Me. Does that sequence look familiar? The first 10 digits look suspiciously like the start of the Thue-Morse sequence, but I don’t recognize the rest of it. Did we make a computation error? Hmm…

The problem, as it turns out, is that our aim is too good! What happens if we make ourselves worse by, say, standing farther apart? Let’s say we now have a $$p=.1$$ chance of hitting our mark on each shot. What is the “fair” shot order this time? Our duel will now follow the sequence Y, M, M, Y, M, Y, Y, M, M, Y, Y, M, Y, M, M, Y, M, Y, Y, M,  M, Y, Y, ... which matches the Thue-Morse sequence in the first 20 digits. Similarly, setting $$p=.05$$ gives 48 correct Thue-Morse digits, defining $$p=.01$$ gives 192 correct Thue-Morse digits, and decreasing to $$p=.001$$ gives 1536 matching digits! It can in fact be proved[1] that decreasing $$p$$ toward 0 (i.e., making our aim worse) gives more and more Thue-Morse digits, with the full Thue-Morse sequence appearing in the limit.

See? Even when arguing about whether the Thue-Morse sequence is cool, we find evidence of its greatness! I hereby declare myself the winner of this duel.

This concludes our series on the Thue-Morse sequence. Tune in next week for, well, something else!

Notes

1. Joshua Cooper and Aaron Dutle. Greedy Galois Games. ArXiv, 2011. []

3 thoughts on “Dueling Dilettantes”

1. Anders Kaseorg says:

I just tried to use this result to generalize the Thue-Morse sequence to non-binary alphabets:

2 players: 0110100110010110100101100110100110010110011010010110100110010110
3 players: 0122102100121200210211202100121022010211202100121022010211201200
4 players: 0123321032100123213003120312213013200231203113023102201301233210
5 players: 0123443210432100123423140041321043223401342011024302413314201432
6 players: 0123455432105432100123453241500514231054233245014253011035240351

But then I computed some more terms and discovered to my surprise that the sequences for 3,4,5,6 players are eventually periodic (with periods 54,192,500,864)! Weird.

2. Sid says:

And the Thue-Morse sequence being cube-free, no one would have 3 consecutive shots. This is awesome. I love this sequence!

Given p, is it easy to predict the point at which it would deviate from the Thue-Morse sequence?

1. Zachary Abel says:

Sid,

Thanks for writing! I’m glad you have enjoyed hearing about the Thue-Morse sequence! (This means we don’t have to duel… =D)

Yes, in the limit there would be no three shots in a row by a single player. But this can happen for positive $$p$$. Try to find such a value!

Regarding your question about relating $$p$$ to the number of matching digits, the authors of Greedy Galois Games (mentioned in the post) conjecture that this number is approximately proportional to $$1/p^2$$.

Here’s a more detailed description (of Conjecture 1.2 in their paper). To concretely relate these quantities, let’s turn the question around and ask how small a $$p$$ we need to get $$n+1$$ matching terms. If we define the polynomial $$g_n(x) = 1-x-x^2+x^3-\cdots\pm x^n$$ where the plus/minuses follow the Thue-Morse sequence, then it can be checked that the sign of the number $$g_n(1-p)$$ (i.e., positive or negative) determines the $$n+1$$st player, assuming $$p$$ matches the Thue-Morse sequence up to round $$n$$. So to guarantee that $$p$$ and all smaller values give the correct next player, we need $$1-p$$ to be large enough so that $$g_n(1-p)$$ doesn’t change sign when $$p$$ is decreased toward 0, i.e., we need $$1-p$$ to be larger than the largest root of $$g_n(x)$$ smaller than 1. The authors conjecture that this largest root $$\alpha_n$$ has the form $$\alpha_n = 1-\beta_n$$ where $$\beta_n \propto 1/\sqrt{n}$$, i.e., we need $$p \propto 1/\sqrt{n}$$ (or smaller) to guarantee the correct prediction up to round $$n+1$$.