4

Say we have a coin and want to decide if it is fair or not. We flip it many times. Consider two cases.

  1. Say the result is a sequence like 0110101011101...
  2. The result is 000000000000...

In the first case the assumption that the coin is fair sounds reasonable, while in the the second the coin is obviously completely biased. However, for a truly fair coin the probabilities of the two sequences are the identical. What is then the concept that distinguishes the first one as more likely? How does one quantify that?

Consider also the third case

  1. The result is 010101010101010...

This actually does not look like a coin at all, but it seems to pass naive tests which boil down to comparing number of zeros to number of ones. Is there a sense in which it is less random then (1)? Or I have to invent a new rule if somebody gives me a more cleverly crafted sequence?

Weather Report
  • 315
  • 2
    The concept is entropy. – Spencer Jan 28 '20 at 20:25
  • You have to change your perspective a little. If you instead count the number of heads, then the first outcome was much more likely than the second outcome. A way to take this further is to then do something called a hypothesis test, doing some calculations with a binomially distributed random variable. – Izaak van Dongen Jan 28 '20 at 20:27
  • @IzaakvanDongen's pointing you to the sequences' p-values. – J.G. Jan 28 '20 at 20:30
  • 1
    https://www.google.com/url?sa=t&source=web&rct=j&url=https://youtube.com/watch%3Fv%3DtP-Ipsat90c&ved=2ahUKEwjEg42xkafnAhWjl-AKHQYxAJYQwqsBMAB6BAgFEAQ&usg=AOvVaw1CjqSZa6OK8DI-jcbCvxMz –  Jan 28 '20 at 20:30
  • There are many many sequences "like" the first. But only one "like" the second – Ali Jan 28 '20 at 20:33
  • 1
    Use Bayesian interference to generate a predictive model. In other words, there are two possible outcomes for any flip. You start with the assumption that the coin is fair. Then, each flip alters the predictive model for the following flip. – SlipEternal Jan 28 '20 at 20:51
  • 3
    Kolmogorov complexity perhaps? It is the length of the smallest program that will output your result. For something "simple" like $000000\ldots$ you can just print $0$ and loop, but for most random bit sequences you can do no better than just storing the sequence in the program and printing it. – Jair Taylor Jan 28 '20 at 21:23
  • 2
    If you flip a coin three times, and the outcome is $000$, is the coin "obviously completely biased"? – mjw Jan 28 '20 at 21:23
  • @JairTaylor I like your suggestion the best, especially in view of the additional case. However this measure seems much trickier to quantify then other ideas. I'll try to look into this. Also it's interesting how many different proposals I've got already:) – Weather Report Jan 28 '20 at 21:42
  • @WeatherReport Yes, the downside is that it's impossible in general to know what the Kolmogorov complexity is - it is uncomputable! But it is still a theoretically useful concept. – Jair Taylor Jan 28 '20 at 21:46
  • 1
    @JairTaylor The Wikipedia article you've linked is excellently written. The fact that the naive program computing Kolmogorov's complexity by probing all programs of a given size will not work (because some programs will involve infinite loops) is maybe standard for computer theorists, but it blew me away! I'm glad I've asked the question:) – Weather Report Jan 28 '20 at 22:06
  • @weather with the 3rd sequence, the difficulty I see is that it doesn't seem to fit the set up with the coin flips, i.e. you pick a coin that you throw independent flips. As there appears to be colleration between the different flips. – clark Jan 29 '20 at 10:32
  • @clark Sure I get your point. But on the other hand. Assuming that the coin is fair, there is identical probability for all 1-3. Why am I then so suspicious of (2) and (3). Is there a general rule? General type of correlation I should consider? – Weather Report Jan 29 '20 at 10:39
  • I agree that Kolmogorov complexity is something OP would be interested in. There is a rich history of attempts to define the "randomness" of a sequence of 0s and 1s. – littleO Feb 09 '20 at 08:27
  • @Weather Report Regarding correlation, if we use the autocorrelation as defined in https://en.wikipedia.org/wiki/Linear_prediction, we find that in your third sequence, R(1) is the expected value of products 0·1 and 1·0, so it is 0. R(2) is the expected value of 0·0 and 1·1, so it is $\frac{1}{2}$. In the random sequence, assuming products 0·0, 0·1, 1·0 and 1·1 are equiprobable, R(1) and R(2) are both $\frac{1}{4}$. – Jaume Oliver Lafont Feb 09 '20 at 10:21

3 Answers3

2

The sequences themselves do have the same probability. However, what makes the first seem more likely to you is the fact that it has a more even number of ones and zeros. Instead of testing the likelihood of the exact sequences, you can test the likelihood of the number of ones and the number of zeros.

For a fair coin, this is binomial with $p = \frac{1}{2}$, meaning that the probability that the number of ones in a sequence of length $n$ is $k$ is

$P_{\frac{1}{2}}(k) = {n\choose{k}}\frac{1}{2}^n$

The only thing that differentiates the sequences is essentially ${n\choose{k}}$, which represents the number of sequences of length n with k ones. This would indeed give a higher probability to your first sequence.

Another way of looking at it, is treating $p$ as unknown. For a given $p$, such that $P(x_i = 1) = p = 1 - P(x_i = 0) \forall i$, the probability of a sequence $x_1, ... x_n$ is

$P(x_1, ... x_n | p) = p^{ |\{i : x_i = 1\}|}\cdot (1 - p)^{|\{i : x_i = 0\}|}$

Now, which $p$ maximizes the likelihood for each sequence? How far is it from the true $p = \frac{1}{2}$ for a fair coin?

Blueyedaisy
  • 1,126
  • Great thank you, this is helpful. I've edited the question adding one more case. Both your tests seem to fail on that one. Any comments? – Weather Report Jan 28 '20 at 21:26
  • I see.. But then you are asking about whether or not there is a pattern in the sequence.. I don't know if I can help you with that. You can count the appearance of specific pairs - how many (11), (01) and so on are in the sequence, instead of single digit numbers, but of course you will be able to find an example where that also does not work. – Blueyedaisy Jan 28 '20 at 21:36
2

You can distinguish your three sequences in terms of their period.

The constant sequence $00000000...$, as well as $1111111111...$ have period $1$ and can be generated by the difference equation $a(n)=a(n-1)$. Closed forms for the sequence are $a(n)=0$ and $a(n)=1$

Sequences $010101...$ and $1010101...$ have period 2 and follow the recurrence $a(n)=a(n-2)$. The corresponding closed forms are $a(n)=\frac{1-(-1)^n}{2}$ and $a(n)=\frac{1+(-1)^n}{2}$. These are simple deterministic formulas, so these sequences are seen to be less random than the first (not random at all).

The patterns can be predicted linearly with zero prediction error after the initial values. One single value is enough for predicting sequence (2) and two values are needed for sequence (3), corresponding to the order of the linear models (first and second order).

The first sequence suggests no period. If it was periodic, the period would be at least $11$, eleven (the last two bits $01$ echoing the first two bits).

From another point of view, let us map your sequences to numbers. Interpret each bit in a positional system, each bit having weight $2^{-n}$, where $n$ is its position.

Your second sequence maps to the integer number $0$. Your third sequence maps to the rational number $$\sum_{k=0}^\infty \frac{1}{2^{2k+1}}=\frac{2}{3}$$

The first sequence would likely map to an irrational number, unless some periodicity appeared later on.

Since most numbers are irrational (Probability of Getting a Rational Number), sequences like the first one are more likely.

Jaume Oliver Lafont
  • 5,212
  • What would your benchmark say about the sequence of 100 coin flips where the first 50 are zeroes and the last 50 are ones? – Weather Report Feb 12 '20 at 12:57
  • If this is repeated periodically, you get $a(n)=a(n-100)$. But when trying to predict it with a simple first order system, even $a(n)=a(n-1)$ gets 98% bits right. This result is very different from the 50% one would get from a fair coin. – Jaume Oliver Lafont Feb 15 '20 at 05:54
  • Your third sequence extended to 100 bits may be represented by $(01)^{50}$ This one in your comment above is quite similar, but $0^{50}1^{50}$ – Jaume Oliver Lafont Feb 15 '20 at 06:04
  • I think you've switched gears when said that $a(n)=a(n-1)$ gets 98% right. Formally this is a sequence with period 1, while $0^{50}1^{50}$ has no period. But I see what you mean: there is a simple way to reliably predict the next flip given previous one. However, in my view this is closer in spirit to string complexity answers than to your original "period" test. What about $0^11^90^21^8\dots0^91^1$? – Weather Report Feb 15 '20 at 11:12
  • I did not estimate autocorrelations for all lags, but maybe a good one is a(n)=a(n-10), which gets 90% values correct. – Jaume Oliver Lafont Feb 15 '20 at 12:30
1

As mentioned in the comment by Spencer, essentially the intuition comes from entropy and what you might call the micro-state/macro-state distinction. You actually have the answer in your question. I've highlighted it

  1. Say the result is a sequence like 0110101011101...
  2. The result is 000000000000...

A sequence like 0110101011101 is way, way more likely than 000000000000. There's loads of sequences like that. 1011011101001 is one of them, 0101101010110 is another, and so on. My guess is that for well over 90% of sequences that long we'd both easily classify it as like your first sequence.

Now it could be that you chose your first sequence very carefully. It could be the precise launch sequence of a missile, for all I know, and you're sitting in a bunker bored out your mind at the moment. Now, if that is the case, you would say it's very, very unlikely to happen by a coin toss, right? What are the chances of that.

Similarly, for all you know, I'm the one sitting in the bunker and I've just spotted that you've written my launch code and I'm on the phone to the secret police to say someone's written our launch code on the internet. I mean, they say it's about tossing a coin but what are the chances of them choosing that randomly?

(Or it could be the digits of Pi, or "You Suck" in ASCII, or the name of an obscure Merzbow album, or ...).

So, the first thing you need to do when you're thinking about things is to group all of the precise sequences (the micro-state) into broad categories that you care about, know about, can know about, etc (the macro-states). Then you can assign a probability to each macro state.

The other answer suggest counting ones and zeros, that's a good start. But sequences like 0101010101010101010101 would be pretty freaky, too.

Underneath all this the space of detectable patterns to humans is much smaller than the configuration space of coin tosses and that in almost all cases the vast majority of configurations map to a pattern we call "random". So the probability of each pattern is very different. Exactly which depends a lot on the person but, you're right 0000000 probably goes to a pattern other than "random" with a small number of other configurations (and so a low probability) and 0110101011101 firmly into random (and so very likely).

As an aside, another way of looking at the pattern issue is to think of the sequences in terms of an approximation to their "Kolmogorov complexity". Think of how long computer code or a description of how to generate the sequence would be (in characters). The code or description for 00000000.. is going to be pretty short. Some (most!) are going to be so "random" that the only real way to describe them is just to write it down and say "print that". In that way you can put a precise figure on how "patterny" a sequence is. Because some sequences have incredibly short descriptions, by the pigeon-hole principle, most are going to end up in this "I give up" set. This isn't actually much more formally powerful than the former above, though, because it depends heavily on the definition of your instruciton set and the oracle of data it has available: it would easily capture any "mathsy" patterns we might spot (including most simple patterns) but probably not that your sequence is the opening lines to the declaration of independence in morse code or last week's lottery numbers. But it's a more precise definition for compuatation-oriented patterns.

Dan
  • 340
  • I have a problem with entropy considerations because I see no canonical way of grouping "microstates" into "macrostates" here. For any "unlikely" sequence there will be some split of all the states into macrostates, so that this unlikely sequence belongs to the biggest macrostate. – Weather Report Feb 12 '20 at 13:08
  • But the complexity benchmark I really like, we touched on that in the OP comments. This seems to suggest that there is some relation between complexity and randomness. On the surface this seems obvious, but perhaps the precise mathematical formulation could be very non-trivial. Something like "most random sequences of n bits have complexity of order n" could be a cool statement to study quantitatively. – Weather Report Feb 12 '20 at 13:12
  • The mapping of entropy to macrostates is simple in the statistical mechanics case because it's just those states that are macroscopically distinguishable with thermodynamic quantities (probably bounded below by QM uncertainty / Maxwell's daemon, but I'm no expert on that). But these days "entropy" has very much escaped those confines! – Dan Feb 13 '20 at 20:32
  • Fortunately, if you're only interested in computationally distinguishable sequences, you do get a bit of a break with Kologorov-like ideas of complexity: if you are Turing complete, you can show that your measure is within an additive constant of any other Turing Complete measure as you can just implement a VM in the other language as a fixed header. That goes some way to helping intuit that your quantities aren't completely predicated on your choice of coding. – Dan Feb 14 '20 at 00:20