31
$\begingroup$

I was hoping someone could provide clarity surrounding the following scenario. You are asked "What is the expected number of observed heads and tails if you flip a fair coin 1000 times". Knowing that coin flips are i.i.d. events, and relying on the law of large numbers you calculate it to be:

$$N_{heads} = 500 \; N_{tails} = 500$$

Now, let us have observed/realized the first 500 flips to all be heads. We want to know the updated expected number of realizations of the remaining 500 flips. Because the first 500 events have been realized and they do not effect the underlying physical coin flipping process, we know that the expected number of heads and tails of the remaining 500 flips are:

$$N_{heads} = 250 \; N_{tails} = 250$$

So, here is my question/confusion: I understand that each coin flip is independent and that any single individual coin flip has a probability of $\frac{1}{2}$ coming up heads. However, based on the law of large numbers we know that the (if we value tails as 0 and heads as 1) mean of the tosses will approach $0.5$ as the number of tosses approaches $\infty$. So, based on that, if we have observed 500 heads in a row, why do we not statistically expect to realize more tails going forward? I fully realize the following thought is incorrect, but it feels like we are (statistically) due for a tails and that the probability of tails should be raised and heads lowered. Since this is not the case, it feels as though this is conflicting with the original expectation of $N_{heads} = 500$ and $N_{tails} = 500$.

Again, I realize that this thinking is incorrect, but I am hoping someone can help me understand why this past information (500 realizations of heads in a row) does not provide any new, updated information that updates the probability for the remaining flips? Clearly the coin does not know that it just came up heads $500$ times, so is the correct way to think about this that the law of large numbers doesn't imply that in the following 500 flips tails is more likely, but rather that as $N \rightarrow \infty$ we expect 50% of realizations to be heads and 50% to be tails. In which case my error in reasoning is based on applying a limit theorem that applies in the asymptote to a preasymptotic situation?

I also feel like this has to deal with a bit of confusion between single events (a single coin toss coming up heads), and the collective action of a set of events (1000 coin tosses) that exhibit nonrandom properties. After searching I came across a wonderful quote by Kolmogorov$^1$:

"In reality, however, the epistemological value of the theory of probability is revealed only by limit theorems. ... In fact, all epistemological value of the theory of probability is based on this: that large-scale random phenomena in their collective action create strict, nonrandom regularity. The very concept of mathematical probability would be fruitless if it did not find its realization in the frequency of occurrence of events under large-scale repetition and uniform conditions."

I believe this quote clears up some of my confusion, but if anyone could elaborate on why realizations (based on a known statistical process) cannot be used to update subsequent probabilities, I would greatly appreciate it!

  1. B. V. Gnedenko and A. N. Kolmogorov: Limit distributions for sums of independent random variables. Addison-Wesley Mathematics Series
$\endgroup$
  • 8
    $\begingroup$ You are equating two distinct models of the coin. At the outset you assume its chance of heads is $p=1/2.$ Gradually you transition to a situation in which you assume it has some unknown chance $p$ that you wish to estimate. Therein is the source of the confusion. An interesting question is how much data might be needed to shake your belief in the first model and make you switch to the second: this is what goodness-of-fit testing is about. $\endgroup$ – whuber Dec 9 '19 at 14:40
  • 11
    $\begingroup$ Practically speaking, if I got 500 heads in a row, I would disbelieve the claim that the coin is unbiased and I would guess the next 500 would be heads too. $\endgroup$ – imallett Dec 11 '19 at 1:36
  • 2
    $\begingroup$ This reminds me of a quote I once read in a book - I don't remember which one, unfortunately. The rough translation is: "A strange guy borrowed a fair coin from a mathematician. With any heads flip he'll take a step away from a cliff, with any tails flip he'll take a step towards the cliff. If he does this long enough, he'll eventually fall off the cliff, no matter the initial distance". The reasoning was that the longer you toss, the higher the probability of getting the same outcome several times in a row. Yours is just an extreme case of this observation. $\endgroup$ – Sabine Dec 11 '19 at 20:05
  • $\begingroup$ As an intuitive way to approach it (Not really good for an answer)--Does it matter to you how often the coin came up heads or tails before it came into your possession? Do you think it carries some property of previous flips? Maybe the last 500 flips before you got it were tails and the heads were just averaging that out?? By the way--this thinking is not unique to you! MANY (If not Most) people feel emotionally (Even if they know better) that a die is "Due" to roll a 1 if it goes a couple dozen rolls without one. Ask most D&D players--or gamblers! $\endgroup$ – Bill K Dec 11 '19 at 21:18
  • 1
    $\begingroup$ This question reminds me of stats.stackexchange.com/questions/95643/… $\endgroup$ – Adrian Dec 14 '19 at 20:39
50
$\begingroup$

If you "know" that the coin is fair

then we still expect the long run proportion of heads to tend to $0.5$. This is not to say that we should expect more (than 50%) of the next flips to be tails, but rather that the initial $500$ flips become irrelevant as $n\rightarrow\infty$. A streak of $500$ heads may seem like a lot (and practically speaking it is), but

  • if $250$ of the next $500$ flips are heads then the sample proportion becomes $$\hat p = \frac{500 + 250}{1000} = 0.75.$$
  • if $250$ of the next $500$ flips are heads then... $$\hat p = \frac{500+250+250}{1500} \approx 0.67$$
  • if $100000$ of the next $200000$ flips are heads then... $$\hat p = \cdots \approx 0.501.$$

This is the Law of Large Numbers.

On the other hand...

if I were to flip a coin in real life and see $500$ heads in a row, I would start to seriously doubt that the coin is actually fair. (Interesting side note, it is hard (impossible?) to actually bias a coin in real life. The only realistic values of $p$ are $0$, $0.5$ and $1$, but we will ignore this for the sake of an answer).

To account for this possibility, we could use a Bayesian procedure from the outset. Rather than assume $p=1/2$, suppose we specify the prior distribution $$p \sim \text{Beta}(\alpha, \alpha).$$

This is a symmetric distribution, which encodes my a priori belief that the coin is fair, i.e. $E(p) = \frac{1}{2}$. How strongly I believe in this notion is specified through the choice of $\alpha$, since $Var(p) = \frac{1}{8(\alpha+0.5)}$.

  • $\alpha = 1$ corresponds to a uniform prior over $(0,1)$.
  • $\alpha = 0.5$ is Jeffrey's prior - another popular non-informative choice.
  • Choosing a large value of $\alpha$ gives more credence to the belief that $p=1/2$. In fact, setting $\alpha = \infty$ implies that $Pr(p=1/2) = 1$.

Applying Bayes rule directly, the posterior distribution for $p$ is $$p|y \sim \text{Beta}(\alpha+y, \alpha+n-y)$$ where $y = \text{number of heads}$ and $n = \text{number of flips}$. For instance, if you choose $\alpha = 1$ and observe $n=y=500$, the posterior distribution becomes $\text{Beta}(501, 1)$ and $$E(p|y) = \frac{\alpha + y}{2\alpha + n} = \frac{501}{502} \approx 0.998$$ indicating that I should bet on heads for the next flip (since it is highly improbable that the coin is fair).

This updating process can be applied after each flip, using the posterior distribution after $n$ flips as the prior for flip $n+1$. If it turns out that the $500$ heads was just a (astronomically) improbable event and the coin really is fair, the posterior distribution will eventually capture this (using a similar argument to the previous section).

Intuition for choosing $\alpha$: To help understand the role of $\alpha$ in the Bayesian procedure, we can use the following argument. The mean of the posterior distribution is equivalent to the maximum likelihood estimate of $p$, if we were to augment the data with a series of $2\alpha$ "hypothetical flips", where $\alpha$ of these flips are heads and $\alpha$ of these flips are tails. Choosing $\alpha=1$ (as we did above) suggests that the augmented data is $501$ heads and $1$ tails. Choosing a larger value of $\alpha$ suggests that more evidence is required to change our beliefs. Still, for any finite choice of $\alpha$, these "hypothetical flips" will eventually become irrelevant as $n\rightarrow\infty$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Quick follow up, based on second approach, what should be the minimum repetition to raise "doubt" about the fairness? Is this a valid approach or should we expect to see 500 heads in a row eventually? $\endgroup$ – shyos Dec 11 '19 at 16:18
  • 2
    $\begingroup$ That depends on how strongly you believe in the fairness of the coin a priori. If you choose $\alpha = 1$, it takes $4$ consecutive heads before the posterior probability that $p > 0.5$ is $0.97$. For different values of $\alpha$ and different values of $y=n$ you can evaluate this probability in R as 1-pbeta(0.5, alpha+y, alpha). In real life, I would probably use a much larger $\alpha$ indicating a strong belief in the fairness of the coin. If the coin really is unbiased, I'll pick up on this eventually. $\endgroup$ – knrumsey Dec 11 '19 at 16:24
  • 1
    $\begingroup$ To build on knrumsey-ReinstateMonica's comment: To get an intuition about how large to set $\alpha$, you can think of the $\beta(\alpha, \alpha)$ distribution as (approximately?) encoding the what distribution over all possible $P(heads)$ distributions for the coin would be, assuming you started with no assumptions, then flipped it $2\alpha$ times and had half turn up heads. $\beta(0,0)$ is undefined since we have no information or assumptions in that case. $lim_{\alpha\to\infty} \beta(\alpha,\alpha)$ is absolutely certain that $P(heads) = 1/2$ and nothing will convince it otherwise $\endgroup$ – Ray Dec 11 '19 at 19:11
17
$\begingroup$

The law of large numbers doesn't state that some force will bring the results back to the mean. It states that as the number of trials increases the fluctuations will become less and less significant.

For example, if I toss the coin 10 times and get 7 heads, those two extra heads seem pretty significant. If I toss the coin 1,000,000 times and get 500,002 heads, those two extra heads are almost completely insignificant.

In your example, those 500 extra heads are going to be HUGELY significant in a trial of 1,000 tosses. However, if you continue that trails out to 10,000 tosses those 500 heads only amount to a 5% difference. After 1,000,000 trials of 50/50 flips those 500 extra heads only account for a 0.05% difference. Going all the way to 1,000,000,000 trials and that initial run of crazy luck only amounted to a 0.00005% difference. You can see that as the number of trials increase, the results become closer to the expected value.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is a fantastic explanation. $\endgroup$ – Jetpack Dec 10 '19 at 3:45
  • 1
    $\begingroup$ This is correct but it misses the point: even in the extremely long trials you discuss, getting 500 heads in a row is an astronomically rare event. $\endgroup$ – whuber Dec 10 '19 at 15:34
  • 5
    $\begingroup$ @whuber he/she is not missing the point at all -- you seem to be applying special significance to "500 heads in a row." It's not special at all. Yes it's a particular combination that is significant to us humans' weird little brains, but for the universe (or statistical math) it's the same as any other sequence of results. $\endgroup$ – x0n Dec 10 '19 at 21:30
  • 2
    $\begingroup$ @x0n I'm afraid you are trivializing something fundamental. Yes, 500 heads in a row has the same chance as any singleton event under the null hypothesis, but this one is clearly distinguished by all the alternative hypotheses. That is, when the null does not hold and $p\ne 0.5$, 500 heads in a row is either the most probable or the least probable possible sequence. This provides a clear, mathematical, objective distinction between long sequences of the same observation and any other long sequence anyone would care to name. $\endgroup$ – whuber Dec 10 '19 at 23:44
  • 2
    $\begingroup$ @x0n (1/2) you really aren't applying this idea correctly. All flips being the same value is absolutely a significant (and extraordinarily unlikely) event-- it can only happen two ways. Meanwhile there are all sorts of ways to achieve a result where about half are heads and half are tails. $\endgroup$ – eps Dec 11 '19 at 17:22
8
$\begingroup$

The notion of the one side being "due" is the "gambler's fallacy" in a nutshell. Boiled down, the gambler's fallacy is the false belief that the short run must mirror the long run.

The coin does not know or care that you plan to stop flipping. For the coin, an infinity of flips remain, and against that infinity, a mere 500 is nothing at all. Keep in mind that, once an outcome has been observed, that outcome is no longer random. The model p(heads) = 0.5 does not govern the past observed values. Each of those values is "heads" with probability 1.

As you state the problem, you persevere with the model p(heads) = 0.5. This model says that history is irrelevant. One might, at some point, consider an alternate model.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This could use some more text. People in general fall for the gambler's fallacy to some degree. In particular, it leads to underestimating variance. Poker forums are full of threads where OP fell for this. $\endgroup$ – JollyJoker Dec 10 '19 at 13:35
6
$\begingroup$

The straight answer, I suppose, is that you don't. The chance that a fair coin will get $500$ heads on $500$ flips is $1$ in $2^{500}\approx3\times10^{150}$. For reference, this is one in ten billion asaṃkhyeyas, a value used in Buddhist and Hindu theology to denote a number so large as to be incalculable; it is about the number of Planck volumes in a cubic parsec. I tried to come up with a snappy "marbles in the observable universe" comparison, but I can't. Nothing is small enough and the universe isn't big enough.
In terms of probability, you are almost a googol times more likely to shuffle a deck of cards into perfect increasing order, aces low, clubs-diamonds-hearts-spades ($1$ in ${52!}$).
At this point, you should be assuming you have been flipping a two-headed coin by mistake. Two-headed coins are not especially rare; they're a mildly popular novelty item. Estimates say some tens of thousands (let's assume twenty thousand) filter into circulation⁠—an easy mistake with a well-made trick coin (and perfectly legal: trick coins are made by machining down two coins and sticking them together, but I wouldn't try arguing they're worth double).
If there are 20,000 double-headers circulating amongst the roughly 3.82 billion US coins in circulation right now, the odds that you've picked one up by mistake are 1 in 191,000. If there's a 99% percent chance you'd notice the coin didn't have a reverse side, that's still a thousand asaṃkhyeya times more likely than this outcome. With one two-header amidst the $793,464,097,826$ coins produced by the US mint since 1890, and a one-in-a-trillion chance you'd let it slip by, that's still a vacuum catastrophe more likely than the alternative.


I think that's what's messing you up: this scenario is so phenomenally improbable that you just can't accept it as conforming to normal probability. Of course, if you've magically verified that the coin really truly is fair, then the odds remain as unchanged as ever: 50/50. I'm just inclined to suspect it isn't.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I tried to come up with a snappy "marbles in the observable universe" comparison, but I can't. Nothing is small enough and the universe isn't big enough. I may need to steal that line next time I need to describe a number that is beyond astronomically large. $\endgroup$ – Ray Dec 11 '19 at 18:40
  • $\begingroup$ I remind myself that there's some chance (1 in 1000? 1 in 1000000?) that I could be asleep and dreaming this all. If I see anything too unlikely, it starts to become more likely I just imagined/dreamed/hallucinated it than that it actually happened. $\endgroup$ – Ask About Monica Dec 12 '19 at 0:37
5
$\begingroup$

There are some great answers here already, but I wanted to add another way of thinking about the problem that may be more intuitive than reviewing the math (to address the feelings described in the question). This reasoning holds for any particular arbitrary number of trials, but does not address the situation of arbitrarily more trials towards infinity. Those are handled elegantly and well in the already-posted, math-based answers.

Each flip is completely independent, and so preceding flips don't have any influence on subsequent flips. But you aren't describing individual flips, because you are imposing information about previous trials.

In this scenario, you are using 500 previous trials to inform your thinking about the result of the next flip. This doesn't work, as each flip is independent from all others. If you are imposing information about 500 previous flips on the problem, then you are interpreting the process as a collection of flips. In that case it may be more intuitive to consider trials not as individual flips but as sets of flips.

As a simpler example, if we're flipping the coin three times we have eight possible outcomes:

  • HHH
  • HHT
  • HTH
  • THH
  • HTT
  • THT
  • TTH
  • TTT

Summarized, those results are:

  • Three Heads: 1 combination
  • Two Heads, One Tails: 3 combinations
  • One Heads, Two Tails: 3 combinations
  • Three Tails: 1 combination

So from the summary descriptions (where flip ordering doesn't matter) it is more likely that we'll see a 2:1 outcome, simply because there are six individual combinations that produce that result compared with the 3:0 possibilities, of which there are only two possible combinations. But each specific combination of three flips appears in the list once, and is just as likely as the others.

The same logic holds for more trials, though the combinations become tedious to list. Luckily for us, if we're asserting a string of 500 flips with results of heads that takes most of the combinations out of the picture-- we need to start with 500/501 flips showing heads.

From that starting point we now look at how many outcomes are possible for the remaining flip, and for that we have the base probability of a single coin flip offering two outcomes:

  • 500 heads flips, and then another heads flip
  • 500 heads flips, and then a tails flip

Every possible combination of flips in a set with a given number of individual trials is equally likely, but the summary of each set produces lots of overlapping results (there are a lot of combinations that produce 250 heads and 250 tails, since the order doesn't matter for the summary, but exactly one combination which would produce all heads across all individual trials).

There are only two combinations which can describe the situation in the question: every single one of the first 500 flips must show heads (assumed in the problem, so the probability of that outcome is not important), and then after those initial 500 flips, you can get your 1st tails result or your 501st heads result.

So that's my suggestion to help internalize the intuition behind this scenario:

  • Each individual flip of a fair coin is memoryless and totally independent, and so each result is equally likely on any particular flip
  • The number of possible combinations of flip results across 500 trials is large, but each specific combination only appears on that list once. Each possible combination of 500 flips is exactly as likely as any other (each has a single entry in the possible outcome list)
  • There are only two possible combinations of 501 flips which begin with 500 flips that show a heads result: one in which another heads result occurs, and one in which a tails result occurs. Each of those results is equally likely (being decided by the 501st flip alone)
| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

The key thing to remember is that throws are IID. Realization could be included when it is considered in the design of your model. One of the example is if your model is a markov model, in fact many models that use bayesian framework includes realization on updating the probability. This is a great example to what I mentioned earlier. The reason that it does not apply for your case because realization is not included by design of your model.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Intuition can often lead us astray in the realm of inifinty because infinity is not experienced in the real world.

A good rule of thumb to help you think about it is that every finite number looks like zero to infinity. A million heads in a row still looks like zero to infinity. If you were to "flip the coin an infinite number of times"--which you can't do, but what we really mean is "keep flipping"--then a run of a million heads eventually becomes a near certainty.

But infinity is a tricky concept, and we have to work hard to make sure we know what we're saying. For example what we mean by "it becomes a near certainty" is: if you give me a percentage, say, 99.99; I will then calculate how many coin flips X you must do to have a 99.99% probability of seeing a run of a million heads in there. You define what "near" means--if you want it to be 99.999999%, fine, I'll just recalculate and give you a bigger number Y of coin flips to do. But even the Y flips won't guarantee the million-head run. All I am guaranteeing is that if you do a bunch of runs of Y flips, then you can expect 99.999999% of them to have a million-head run (and the more you do, the closer to 99.999999% we can expect the outcome to be).

In the universe of possibilities, starting a run with any number of heads is a possibility. What the law of large numbers is saying is that if you go long enough, that particular run is more and more immaterial because there are so many other experiments being done. Yes, you might get a billion heads in a row. But if you give me a percentage and a target, like, say, "I want to be 99.8 percent sure that my head-tail ratio is between .499 and .501, and I know I start out with a billion heads" I can tell you a number Z that will give you a 99.8% chance of achieving that.

Infinity is not a number. It's a concept beyond number, and when we talk about it, we have to be really careful that we know what we really mean, or we will end up confusing ourselves. The law of large numbers talks about what happens when N "goes to infinity" (actually toward infinity, you don't "get there"), and so it's not surprising that reasoning about what it is really telling you can lead to some pitfalls. Everything we experience is finite, and, in the real world, if an accountant was looking over your shoulder you would be getting more and more nervous about how many tails you're going to need to "balance this run out". Infinity has the time for that, even if the full span of the existence of humanity might not.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Really enjoyed this answer! $\endgroup$ – ndake11 Dec 12 '19 at 17:18
0
$\begingroup$

Different schools of probability is a bit confusing, so let's do that on the computer as experiments.

What your confusion is that

  1. If I have (say) 300 tails in the first 500 flips, should I expect 200 tails in the next 500 flips?

  2. If I have (say) 200 tails in the first 200 flips, should I expect (only) 300 tails in the next 800 flips?

  3. If I have $x$ tails in the first $y$ flips, should I expect (only) $500-x$ tails in the next $1000-y$ flips?

Or if we set tail to be -1 and head to be +1:

If I have in the first $y$ flips the sum is $s_1 = x$, should I expect in the next $n-y$ flips the sum to be $s_2 = -x\frac{y}{n-y}$?

If we flip many many runs, with each run $n$ flips, and we plot $s_1$ and $s_2$, if your statement is true, we should see a nice line for fixed $y$, for $s_2 = -s_1 \frac{y}{n-y}$.

Here is a python code for your problem:

import random
from matplotlib import pyplot as plt


def run():
    n_trial = 1000
    flip = 1000
    deviation = []
    prediction = []
    for trial in range(n_trial):
        result = [random.choice([-1, 1]) for _ in range(flip)]
        current = 500
        deviation.append(sum(result[:current]))
        prediction.append(sum(result[current:]))

    return deviation, prediction


deviation, prediction = run()
plt.scatter(deviation, prediction)
plt.show()

The result is a giant ball of mess.

y=500

which means that they are unrelated, even from a "experimental" point of view.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Whether you flipped a coin many times in the past is irrelevant. Every time you throw a coin the expectation is there is a 50% chance it will be heads. If you are going to throw it 500 times it should be heads about 250 times. But there is no guarantee. All 500 times could be heads, or 0 times.

Taken altogether, after you finished with your 1000th throw you could have had heads from 500 to 1000 times. The precise combination of heads and tails you got had the same chances of occurring, even if the first 500 flips were heads.

To visualize it lets say you were flipping it 4 times. Your first two flips were H, H. Your outcome could then be:

H, H, H, H
H, H, H, T
H, H, T, H
H, H, T, T

You can see the heads and tails have a 50% chance. Let's say the outcome was H, H, H, T. That outcome was one of a possible

H, H, H, H
H, H, H, T   <---yours  
H, H, T, H
H, H, T, T 
H, T, H, H 
H, T, H, T 
H, T, T, H 
H, T, T, T 
T, H, H, H 
T, H, H, T 
T, H, T, T 
T, H, T, T 
T, T, H, H 
T, T, H, T 
T, T, T, H 
T, T, T, T

so 16 combinations. Any of those could have happened and one of them did. Just because you say the first two were H, H doesn't change the outcome of the last two. The first two could have been T, T or T, H and the outcome of the last two would have still being independent.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.