The Random Sequence
Fifteen years ago I attended Silvio Micali‘s cryptography course. During one of the lectures, he asked me to close my eyes. When I did, he wrote a random sequence of coin flips of length six on the board and invited me to guess it.
I am a teacher at heart, so I imagined a random sequence I would write for my students. Suppose I start with 0. I will not continue with zero, because 00 looks like a constant sequence, which is not random enough. So my next step would be sequence 01. For the next character I wouldn’t say zero, because 010 seems to promise a repetitive pattern 010101. So my next step would be 011. After that I do not want to say one, because I will have too many ones. So I would follow up with 0110. I need only two more characters. I do not want to end this with 11, because the result would be periodic, I do not want to end this with 00, because I would have too many zeroes. I do not want to end this with 01, because the sequence 011001 has a symmetry: reversing and negating this sequence produces the same sequence.
During the lecture all these considerations happened in the blink of an eye in my mind. I just said: 011010. I opened my eyes and saw that Micali had written HTTHTH on the board. He was not amused and may even have thought that I was cheating.
Many teachers, when writing a random sequence, do not flip a coin. They choose a sequence that looks “random”: it doesn’t have too many repetitions and the number of ones and zeroes is balanced (that is, approximately the same). When they write it character by character on the board, they often choose a sequence so that any prefix looks “random” too.
As a result, the sequence they choose stops being random. Actually, they’re making a choice from a small set of sequences that look “random”. So the fact that I guessed Micali’s sequence is not surprising at all.
If you have gone to many math classes, you’ve seen a lot of professors choosing very similar-looking “random” sequences. This discriminates against sequences that do not look “random”. To restore fairness to those under-represented sequences, I have decided that the next time I need a random sequence, I will choose 000000.
Share:
Qiaochu Yuan:
To be fair, if you are trying to demonstrate some theorem it is more important that your example have all of the features of the general case than that it actually be “random.” Roughly speaking it should have high Kolmogorov complexity.
21 August 2010, 1:27 pmTanya Khovanova:
Qiaochu,
You are absolutely right. I am even planning to discuss that in my next piece on the subject. Having said that, I find it very useful and educational to throw students off from time to time.
21 August 2010, 2:07 pmXamuel:
Loved the description of the heuristics you used. It reminds me of the following trick. Suppose you’re playing a game against a perfectly rational opponent. You are to recite numbers one-by-one from a sequence which may be random or non-random, and your opponent has to guess whether or not the sequence is random, he gets to revise his guess with each new number you announce. He wins if his guesses eventually converge into always being correct. You win otherwise, with bonus points if you get him to change his mind infinitely often.
Here’s how you can win: start reciting 0,0,0,… until eventually the guy guesses “non-random” (he must eventually since, if you kept this up forever, that would clearly not be a random sequence, and the guy is perfectly rational). Now you have a finite string of 0’s which makes him guess “non-random”. To that, start appending numbers randomly and reciting them, until eventually your opponent guesses “random”. He must eventually, because if the process continued forever, the sequence really would be random. So now you have a sequence of finitely many zeros followed by some random numbers, which forces the enemy to eventually guess non-random then later switch to guessing random. Now to this sequence start appending and announcing zero’s. Eventually he must switch his guess to “non-random”… and so on forever. In this way you force him to change his mind infinitely often.
(What if you’re not allowed to make your sequence up as you go, but must fix it in advance? Then you no longer have a winning strategy, but neither does your opponent. Because if your opponent had a winning strategy, you could incorporate that strategy into the sequence you initially choose, and replicate the above situation.)
For more on this kind of thing, see: https://www.xamuel.com/guessability/
21 August 2010, 3:40 pmJBL:
I believe this is related to a point that Peter Winkler made in one of his Simons lectures: he showed a randomly generated rectangular grid with some squares colored, noted it was generated uniformly at random, and then pointed out that if we believe his claim then we also believe that if his first random experiment had returned the all-white grid, he would have put it in his presentation.
27 August 2010, 11:29 pmHarry:
The magician Derren Brown once did a trick like this though unfortunately I can’t find the video. He had a wall with two holes in it which he placed his hands through. He claimed to around 50 people that he would be able to guess which of his hands they placed theirs above, pretending that he had psychic powers. The wall meant he couldn’t see his hands and there would be no physical contact. Each person did it one after the other and he guessed correctly for all but one of the people.
After the trick he explained how he had done it. It was very clever and revolved around the test subjects instinct to try and take the least obvious option, and the first person was coerced by beckoning with one hand to subconsciously make them choose the other. I think the next 5 people choosing an order exactly the same as your one, LRRLRL. He also uses this method to play rock paper scissors, winning time after time. He is very much a master of the bluff, double bluff, triple bluff, etc!
2 September 2010, 5:56 amTest your intuition: consecutive tails « Annoying Precision:
[…] actual answer is about . As Tanya Khovanova observed, when people try to write down sequences of random coin flips, they make certain biased […]
21 September 2010, 1:26 pmBasil:
This is similar reasoning to why there is such high probability of two people in a room of 30 having the same birthday. My teacher in statistics during undergrad walked outside the room, then had one student randomly flip a coin while another student tried to create a random event from their head. He came in and failed the test, but made a good point during the class.
1 February 2011, 9:14 pmTanya Khovanova’s Math Blog » Blog Archive » Complexity of Periodic Strings:
[…] will be more significant. Also, I am pleased to see that the sequence 011010, the one that I called The Random Sequence in one of my previous essays, has the highest […]
27 June 2011, 1:10 pm