Expectation of 500 coin flips after 500 realizations

Question

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

Answer 1

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$.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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)

Answer 6

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.

Answer 7

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.

Answer 8

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.

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

Answer 9

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.