Guessing the result of infinitely many coin tosses

September 22, 2008

What is the probability that an infinite number of coin tosses all land heads up? In a relatively recent analysis paper Tim Williamson argues, convincingly I think, that the probability must be 0. What I’m going to say here is to do with a related puzzle, and may shed some light on this question, although I haven’t fully absorbed the consequences. But either way, it strikes me as very weird, so any comments would be welcome.

The puzzle I’m concerned with involves guessing the results of infinitely many coin tosses. The setup is as follows:

For each n > 0, at $\frac{1}{n}$ hours past 12pm the following is going to happen: aware of the time, you are going to guess either heads or tails, and then I am going to flip a coin and show you the result so you can see if you are right or wrong. This process may have to be done at different speeds to fit it all in to the hour between 12pm and 1pm.

[Note how this differs from the Williamson sequence of coin tosses in that it is a backwards supertask.] The question I’m interested in is: how well can you do at this game? For example, can you, with absolute certainty, guess every result correctly? Intuitively, the answer is ‘no’, and unsurprisingly the answer to this question is indeed ‘no’. Can you adopt a strategy for guessing such that you are guaranteed to get at least one guess right? Intuitively the answer is still ‘no’ – no matter how unlikely, it is still possible that you always guess the wrong answer, and it is hard to see how adopting a certain way of guessing will get you out of this if you are extremely unlucky. Despite the intuition, however, the answer to this second question is in fact ‘yes’! There is a way of guessing such that you are guaranteed to guess right at least once. If that doesn’t strike you as weird yet, think about it a bit more before reading on.

Things get even weirder. It turns out that there’s a way of guessing such that, following it, you are completely guaranteed, no matter how the coins land, to guess all but finitely many of the tosses correctly. That is, if you follow this strategy, you are guaranteed to only make finitely many mistakes. Among other things, this means that at some point after 12pm you won’t have made any mistakes at all! You would have guessed an infinite sequence of coin tosses correctly. So it follows that there is a way of guessing such that it is guaranteed that if you follow it, you will guess the result of a fair toin coss correctly infinitely many times in succession.

The construction of the strategy is actually relatively simple (and it resembles the solution to this infinite hat problem closely.) Firstly we divide the space of all possible complete sequences of heads and tails the coin could land in into equivalence classes as follows. By a possible total sequence of heads and tails I mean a list describing the result of each coin toss at each time 1/n past 12. The sequences are divided into equivalence classes according to whether they agree at all but finitely many places in the sequence. I.e. let a ~ b iff a and b disagree about how the coin lands at most at finitely many places. Now, with the help of the axiom of choice, we can pick a representative sequence from each equivalence class – so we have a choice function that associates each equivalence class with an element it contains.

The stategy you should adopt runs as follows. At 1/n hrs past 12 you should be able to work out exactly which equivalence class the completed sequence of heads and tails that will eventually unfold is in. You have been told the result of all the previous tosses, and you know there are only finitely many tosses left to go, so you know the eventual completed sequence can only differ from what you know about it at finitely many places. Given you know which equivalence class you’re in, you just guess as if the representative of that equivalence class was correct about the current guess. So at 1/n hrs past 12 you just look at how the representative sequence says the coin will land and guess accordingly.

Now, since the representative sequence and the actual sequence of heads and tails that occurs are in the same equivalence class, they must only differ at finitely many places. So, if you guessed according to the representative sequence, you have only made finitely many mistakes.

Now this raises some further puzzles. For example, suppose that it’s half past twelve, and you know the representative sequence predicts that the next toss will be heads. What should your credence that it will land heads be? On the one hand it should be 1/2 since you know it’s a fair coin. But on the other hand, you know that the chance that this is one of the few times in the hour that you guess incorrectly is very small. In fact, in this scenario it is “infinitely” smaller in comparison, so that your credence in heads should be 1. So it seems this kind of reasoning violates the Principal Principle.

1. I’m not convinced by your example. I’m not even sure the concept of a backward supertask is sensible.

In particular, you only lay out what happens at time 1/n. But by time 1/n (for any natural number n) the game is already over: you’ve made all but a finite number of choices, and thus either you’ve guessed correctly a cofinite number of times or you haven’t. Your further guesses don’t change that.

2. “I’m not convinced by your example. I’m not even sure the concept of a backward supertask is sensible.”

Why not? Presumably Zeno’s runner performs one every time he moves in just the same way as he performs a forwards supertask.

“In particular, you only lay out what happens at time 1/n. But by time 1/n (for any natural number n) the game is already over: you’ve made all but a finite number of choices, and thus either you’ve guessed correctly a cofinite number of times or you haven’t. Your further guesses don’t change that.”

I wouldn’t say the game was *over*. If it turned out black had a winning strategy in Go, it wouldn’t mean that every game was over before it started.

Similarly, you may reach a point in a game (like Go, or whatever) where no matter what moves you make you’ll win eitherway (i.e. every strategy is winning.) Surely this doesn’t undermine a strategy that allows you to get to this point in a game. By following the strategy described above, you get to such a point at every time 1/n hrs past 12pm.

3. But the strategy never says what to do when you have an infinite number of moves remaining, only what to do when you have a finite number of steps left. It’s like saying that if you have a rook and your opponent has only a king, you can win by a forcemate. But the hard part is reducing your opponent to just a king (while keeping a rook), not in forcing mate once you have!

To reiterate: once only a finite number of moves remain, any sequence of moves result in the same outcome. Your strategy only applies in this case. You haven’t even said what coin to choose for the ‘first’ flip, and couldn’t.

4. Hi Charles.

I’m afraid I still don’t see the problem. Maybe you could spell out what it is you’re objecting to? E.g. do you think that it is possible to follow the strategy I outlined and still make infinitely many wrong guesses? Or do you think that the strategy isn’t complete (i.e. there are some situations where it won’t tell me what to do?) If the latter I really can’t see what the situation would be like: for every coin flip the strategy tells me exactly how to act (there is, of course, no first flip, so accordingly the strategy has nothing to say about it. Nor is there ever a point in the game at which there is an infinite number of moves remaining, so again a strategy needn’t say anything about that situation.) If the former, well, maybe you could point out a mistake in the argument?

5. The strategy isn’t complete. It only tells you what to do in cases where a cofinite part of the game is finished, and since you’re judging the game based on its performance up to finite differences, the strategy is worthless.

In particular, your strategy does not suffice to show what happens at any cofinite portion of the coin throws.

If at any time 1/n you simply choose heads, your results will be the same: your correct guesses for the rest of the finite tail follows a binomial distribution with p = 1/2.

6. Very clever puzzle! I’d seen the hats one before, but this really makes it look crazier. I’ve got more to say about the last paragraph, but I’m putting that in a post on my blog instead.

Charles – the fact that this is a backwards supertask simply means that at every point during the game, a cofinite part of the game is finished. So the fact that the strategy only tells you what to do at those points means that it doesn’t leave out any points of the game.

I think the worry you might have is, “what about the first coin flip?” Well, the problem is that there is no first coin flip.

7. […] Help! My credences are unmeasurable! September 29, 2008 This is a brief follow up to the puzzle I posted a few days ago, and Kenny’s very insightful post and the comments to his post, where […]

8. […] Bizarrely, however, player does have winning strategies on non-well founded games. Suppose they play on a backwards omega sequence, e.g. each move takes place at 1/n hours past 12pm, and the game ends at 1pm. Then you divide the possible sequences that player two might play into equivalence classes according to whether they differ by at most finitely many moves. If player one picks a representative from each class, then at each point in the game he can work out what class he’s in, and he can play the same move that the representative sequence predicts player two will play. At the end he must have won all but finitely many moves (I discussed the strategy a bit more here. […]

9. I know this is a long time after :). But, I couldn’t resist a comment.

I think it is possible to follow the strategy and still make infinitely many wrong guesses. In particular, I think the probability of guessing correctly using the strategy will be 1/2 at any given point (assuming that the choice function is independent of the actual coin flips that result). This follows from the fact that we gain no information with which to make our guess. By standard axioms, I bet one could prove that the infinite-correct-guess scenario has measure zero.

Yet, the argument in the post seems sound: if we know the equivalence class of the flip sequence at flip N (counting backwards, so the last flip is 1), we also knew the equivalence class we were dealing with at N+1, N+2, and indeed N+x for any finite x. Since all coin flips have the property of being only a finite number of flips from the end, we know the equivalence class the whole time! Yet we can’t manage to guess correctly, because that gives us no specific info about the next flip?

It might be that the game is inconsistent. I am not sure.

10. OK, nevermind, I’ve done more reading now and I see that non-measurable sets will block my argument!

11. This is kind of neat. I guess it’s an example of the properties of ultrafilters. At first it seems like a paradox, but then once you realize that at every point in time you have an infinite amount of information about the future, this opens up the possibility for strategies that are impossible with only finite information. However, note that the probability of any particular guess being right is still 1/2–I’m not sure what your reasoning is in the last paragraph.

12. Yeah you’re right – that was a really dodgy application of the principle of indifference. I think it should be 1/2.

13. Unexpected Hanging on steroids :DDD

14. You can derive a contradiction using the same type of reasoning as follows:

Clearly at every point 1/n, we have available to us the information about every previous coinflip at 1/m with m > n, and also the information about our own actions at every 1/m with m > n.

The following strategy is defined at 1/n for every possible set of previous coinflips and previous actions:

If previously an infinite number of wrong guesses have been made, predict according to the equivalence-class representative of the previous coinflips, chosen as above. Call this string A.

If previously a finite number of wrong guesses have been made, predict according to the string “all heads”, unless the string “all heads” makes only a finite number of wrong guesses on the previous coinflips, in which case predict according to the string “all tails”. Call these strings B and C respectively.

If at any point 1/n the player predicts according to string A, B, or C, the player predicts according to the same string at point 1/(n+1). The player thus predicts throughout using the same string that is selected at point 1/1, proof by induction on the positive integers.

The player thus gets an infinite number of guesses wrong if and only if the player gets a finite number of guesses wrong. This is a contradiction and therefore the reasoning involved in “backwards supertasks” is not in general permissible. QED.

15. Hi Eliezer,

Thanks for this. I’m aware that there are strategies like the one you described which are impossible to follow. Here’s a simple one: at each round predict tails if you’ve predicted heads at every previous round, and predict heads otherwise.

Maybe you could expand a little on your diagnosis; which bit of reasoning is not permissible? I don’t think I would blame the contradiction on the possibility of backwards supertasks. They’re not even essential: you could imagine instead a being who had been tossing and guessing coins at a constant rate for eternity. This doesn’t require a supertask, only that time has no beginning.

(By the way, I have a more worked out version of these thoughts here if you’re interested:

)

• If I were to expand on my diagnosis, it would have to do with the non-well-foundedness of the set, and the impredicativity of the induction (reasoning at any given time 1/n about tasks already accomplished – any particular order of the reasoning will demand that you consider things as having already happened that you haven’t already considered).

I’d sooner say that the “backward supertask” as a global whole is impossible, than that I magically can’t follow a locally well-specified strategy. In any case, if you want to propose that backward supertasks are a legitimate subject of mathematical discussion, it’s up to you to provide axioms of reasoning about them which will not lead us into contradictions. Claiming that some particular strategy can’t be performed (without giving us general rules) is like Frege saying, “Well, there’s nothing wrong my set theory – it’s just that, if you try to form the set of all sets that don’t contain themselves, you’ll find for some reason that you can’t actually check whether that set contains itself.”

16. “In any case, if you want to propose that backward supertasks are a legitimate subject of mathematical discussion, it’s up to you to provide axioms of reasoning about them which will not lead us into contradictions.”

I’m not quite sure what you want me to do here. Mathematically there is nothing exceptional about non-well-founded sequences. We don’t need special axioms, we could model the whole set up above using standard mathematics: for example, the naturals under the ordering > form a non-well-founded sequence. We could model the players choices as a functions from naturals to {0, 1}: for each sequence of choices the player could have made there will be a corresponding function and vice versa. Your claim that one could follow a “locally well-specified strategy” (say, the simple strategy I described in my last message) amounts to the claim that there is a function on the naturals to {0,1} such that f(n)=1 if f(m)=0 for all m>n and f(n)=0 otherwise. There is no such function on pain of contradiction. It would be bizarre to conclude that somehow the non-well-foundedness of the natural numbers under > is responsible for this.

17. Hi Andrew,

Probably a silly worry but you say: “the representative sequence and the sequence that represents how Bob actually played, must be in the same equivalence class”. But given that for any round it will be finitely many rounds from the end, the representative sequence may differ from Bob’s actual sequence in what it ascribes for that round and yet be in the same equivalence class (as it may agree for all previous rounds). Any help or info would be great.

Thanks
Sam

18. Sam,

This is right: you can’t guarantee any particular guess will be right, but you’ll guarantee that out of the entire sequence you’ll get all but finitely many right.

19. For a plain mathematical formulation of this “paradox” see Problem 5348, American Mathematical Monthly 72 (1965), p. 1136.
(WARNING: The *first* solution of Problem 5348 published in the Monthly was incorrect; the second solution they published was correct, as was the proposer’s.) This result has been applied toward the construction of counterexamples in algebra: see Karel Prikry et al., “Infinitary Jonsson algebras and partition relations, Algebra Universalis 6 (1976), 367-376,, and George M. Bergman et al., Transversals of families in complete lattices, and torsion in product modules, Order 3 (1987), 391-403.

20. This article claims to provide a strategy to guess an infinite number of tosses right and just a finite number of tosses wrong. As the strategy depends on information about past tosses at some time past 12:00, the number of tosses left is finite. And I don’t see how you could claim to have guessed backward an infinite number of tosses right, as your ,guess’ only consists of the finite number of tosses that it differs with the known realized sequence of tosses.