(Another) random / coin tossing thread

[Ivor the Engineer]

Let's say you're attempting to test a coin for fairness. You toss the coin N times and get N heads (or tails)*. You know getting N heads or N tails should occur with a probability 1/2^(N-1). In other words, over an infinite number of trials of a fair coin, each N tosses long, 100%/2^(N-1) of them would consist of all heads or all tails.

Since any event with non-zero probability can occur, however many heads or tails in a row you get can (should?) be produced by a fair coin over an infinite time period.

What do algorithms which test for the randomness of a generator actually test for, when a generator which produced a constant value over the test period would be as "random" as generators which produced other sequences?

What is randomness from a testing or observer's point of view?

*Ignore the possibility of the coin landing on its edge.

 

[Acleron]

As the probability of N occurrences of a particular value can be measured, a comparison between the random number generator profile and probability can be made and as far as I can remember this is done. The occurrence of specific sequences eg HHTTHH is also tested for.
Being probable and therefore random, there would be nothing to stop the first 10000 values being the same, but very improbable. I found this once when not realising that when multitasking a random event the same seed was used in each calculation. After receiving the same sequence of random numbers three times I sat down and thought out what was happening. That seemed a better use of time than repeating the test.

 

[sol invictus]

What do algorithms which test for the randomness of a generator actually test for, when a generator which produced a constant value over the test period would be as "random" as generators which produced other sequences?

The standard point of view is to adopt a null hypothesis (that the coin is fair, say), an alternative hypothesis (the coin has heads on both sides, or is weighted in some way that affects its flips), collect some evidence (you flip N times and get all N heads) and then ask with what confidence you can reject the null hypothesis (i.e. how likely such an event is, given the null hyp.).

So in your case you could reject the hypothesis that the coin is fair with confidence 1-2^(N-1) in favor of the hypothesis that it has heads on both sides.

You can formulate all of this very precisely - probably Bayes' theorem would be a good thing to read up on.

 

[Jekyll]

What do algorithms which test for the randomness of a generator actually test for, when a generator which produced a constant value over the test period would be as "random" as generators which produced other sequences?

What is randomness from a testing or observer's point of view?

You have to be careful not to confuse randomness with fairness.

Other people have covered fairness, so I'll make a stab at randomness.

Essentially, randomness means patternless, which in turn means uncompress able. Fairness just means unbiased. So H T H T H T... is fair but not random.

A typical test for the randomness of a number generator will assume that the generator is fair and then look for projections of the `random' data in which patterns or clusters arise. We could then use such patterns to compress the data.

Of course any deterministic number generator is not going to be random.The sequence can be compressed to an algorithm and an initial seed, but it can be `good enough' to satisfy a set of standard projections that we concern ourselves with.

So the short answer is a generator is random and fair iff the data from it is incompressible, as the sample size tends to infinity.

 

[Ivor the Engineer]

The standard point of view is to adopt a null hypothesis (that the coin is fair, say), an alternative hypothesis (the coin has heads on both sides, or is weighted in some way that affects its flips), collect some evidence (you flip N times and get all N heads) and then ask with what confidence you can reject the null hypothesis (i.e. how likely such an event is, given the null hyp.).

So in your case you could reject the hypothesis that the coin is fair with confidence 1-2^(N-1) in favor of the hypothesis that it has heads on both sides.

You can formulate all of this very precisely - probably Bayes' theorem would be a good thing to read up on.

Isn't the experimenter, when selecting alpha or interpreting a p-value, implicitly using their (Bayesian) prior belief about the properties of a unfair coin, along the lines of a unfair coin produces long runs of N heads (or tails)?

I think what I'm trying to get at is a hypothesis test cannot tell you if the coin is fair or not, because alpha or the p-value says nothing about the probability of the alternate hypothesis (the coin is unfair). It tells you something you already know: getting all heads (or tails) is unlikely if the coin is fair, but occurs with a non-zero probability and so is possible for a fair coin to produce a such a result.

Yet most sane people would agree a coin which produced 100 heads in a row was biased in some way.

I think what people do when they get a result such as 100 heads in a row is compare this property of the coin under test against their beliefs about what properties unfair coins have.

I therefore assert Bayesians are right and Frequentists are wrong.

 

[Ivor the Engineer]

You have to be careful not to confuse randomness with fairness.

Other people have covered fairness, so I'll make a stab at randomness.

Essentially, randomness means patternless, which in turn means uncompress able. Fairness just means unbiased. So H T H T H T... is fair but not random.

A typical test for the randomness of a number generator will assume that the generator is fair and then look for projections of the `random' data in which patterns or clusters arise. We could then use such patterns to compress the data.

Of course any deterministic number generator is not going to be random.The sequence can be compressed to an algorithm and an initial seed, but it can be `good enough' to satisfy a set of standard projections that we concern ourselves with.

So the short answer is a generator is random and fair iff the data from it is incompressible, as the sample size tends to infinity.

I like that definition, probably because it agrees with ideas I'm familiar with as an electronic engineer.

 

[sol invictus]

I therefore assert Bayesians are right and Frequentists are wrong.

I've never been able to understand what that debate is really about. As far as I can tell, frequentists are just Baysians who insist on assigning equal priors to every hypothesis (although of course they have to decide first which hypotheses to consider, which seems just as arbitrary as assigning unequal priors). But presumably it's not that simple, since professional statisticians have been having this argument for years.

Anyway, I fully agree with your post. Yes, of course you have to assign priors - otherwise you couldn't apply Bayes' theorem. However in practice this is rarely an issue, because the precise prior you assign isn't very important. If you get 50 heads in a row, you'd have to have a fanatical faith that the coin is fair to not conclude it's weighted, and in the real world we almost never have such extreme levels of confidence in our theories.

 

[drkitten]

Isn't the experimenter, when selecting alpha or interpreting a p-value, implicitly using their (Bayesian) prior belief about the properties of a unfair coin, along the lines of a unfair coin produces long runs of N heads (or tails)?

Quite the opposite. They're using their beliefs about the properties of a "fair" coin; the properties of an unfair coin are simply defined as anything that isn't fair. Since the properties of an unfair coin cannot be specified in any more detail than not-fair, they can't be used.

And Bayesian reasoning is neither necessary nor appropriate, since we are not calculating the probabilitiy that the coin is fair or not. We are merely accepting or rejecting the (null) hypothesis that it is.

I think what I'm trying to get at is a hypothesis test cannot tell you if the coin is fair or not, because alpha or the p-value says nothing about the probability of the alternate hypothesis

We don't need to know anything about the alternate hypothesis. We merely reject the hypothesis that the coin is fair, which leaves "unfair" as the only hypothesis standing.

 

[drkitten]

Yes, of course you have to assign priors - otherwise you couldn't apply Bayes' theorem.

Yes, but you don't have to apply Bayes' theorem.

Bayes' theorem is appropriate if you want to make a statement like "the probability that the coin is biased is X%." But if you simply want to state that "the coin is biased," without making a probabilistic assessment of the likelihood that it is biased, then you simply apply a frequesting framework and set an appropriate alpha cutoff.

 

[69dodge]

I therefore assert Bayesians are right and Frequentists are wrong.

Yes. Absolutely.

A fair coin tossed twenty times has a probability of about one in a million of landing heads every time. It has exactly the same probability of about one in a million of yielding the sequence HTHTTHTTHTTTTTTHHHTH. The only reason to conclude that the coin probably isn't fair if you get all heads, but not to reach the same conclusion if you get the other result, is that you have a prior belief that the coin is more likely to be unfair in such a way as to produce twenty heads than it is to be unfair in such a way as to produce the other result.

 

[Ivor the Engineer]

<snip>

We don't need to know anything about the alternate hypothesis. We merely reject the hypothesis that the coin is fair, which leaves "unfair" as the only hypothesis standing.

Does it?

50 heads, followed by 50 tails, or 50 Head-Tail pairs would result in the null-hypothesis being accepted (p=0.0). An experimenter with prior belief about the properties of a (not-)fair coin would notice these patterns.

All a frequentist would say is he'll make a mistake 100*alpha% of the time and reject a coin which was actually fair, or even more uselessly just quote a p-value (zero in the above cases) and let some other sucker make the decision. (Let's ignore type-II/beta-errors.)

ETA: 69dodge beat me to it!

 

[tsg]

Yes. Absolutely.

A fair coin tossed twenty times has a probability of about one in a million of landing heads every time. It has exactly the same probability of about one in a million of yielding the sequence HTHTTHTTHTTTTTTHHHTH. The only reason to conclude that the coin probably isn't fair if you get all heads, but not to reach the same conclusion if you get the other result, is that you have a prior belief that the coin is more likely to be unfair in such a way as to produce twenty heads than it is to be unfair in such a way as to produce the other result.

Firstly, I'll admit to my ignorance concerning Bayesian vs Frequentist, but isn't the prior belief that a coin that produces all heads is unfair rather more reasonable than the belief that a coin that produces roughly equal amounts of heads vs tails is? I can think of at least two ways to influence a coin to land on all heads. I can't think of any (at least, not without some sophisticated machinery that would likely be pretty obvious) that would cause a coin to land in a specific pattern of roughly equal numbers of heads and tails.

 

[drkitten]

Does it?

Yes. If the coin is provably not fair, then it is unfair. By definition. And that's about all the definition of "not fair" that can be usefullly offered.

50 heads, followed by 50 tails, or 50 Head-Tail pairs would result in the null-hypothesis being accepted (p=0.0).

That is correct. (More accurately, p = 0.5, but that's minor). In this case, the frequentist should have used a runs test instead of a simple t-test, but that's his lookout. Bayesian stats offer no defense against running the wrong test.

An experimenter with prior belief about the properties of a (not-)fair coin would notice these patterns.

Only if he had the right kind of prior belief --- if his belief about the properties of a not-fair coin was defined as an imbalance of heads over tails, then, no, he wouldn't. If his belief was that the coin flips were not independent, then yes, he would. But you can't magically intone "Bayes theorem" and conjure omniperceptance into the researcher.

In particular, if a Bayesian calculates the probability that the coin is fair given the proportion observed of heads to tails, then he'll also conclude that the 50 heads followed by 50 tails is a fair coin. If the Bayesian calculates the probability that the coin is fair given the distribution of runs observed, he will similarly conclude that the coin is unfair.

if the Bayesian is on the lookout for any pattern whatsoever, then he will automatically conclude that the coin is unfair (and was biased to show exactly the pattern that was observed). An omniperceptive Bayesian is therefore nothing more nor less than a paranoiac who sees predestined bias in everything.

Vacuous, at best.

 

[69dodge]

[...] isn't the prior belief that a coin that produces all heads is unfair rather more reasonable than the belief that a coin that produces roughly equal amounts of heads vs tails is?

Certainly.

I didn't mean that it's not reasonable, just that it is necessary.

 

[69dodge]

if the Bayesian is on the lookout for any pattern whatsoever, then he will automatically conclude that the coin is unfair (and was biased to show exactly the pattern that was observed).

But what about the prior probabilities that the coin is biased in various ways?

Someone who doesn't take those probabilities into account can hardly be called a Bayesian.

 

[drkitten]

But what about the prior probabilities that the coin is biased in various ways?

They're irrelevant.

Someone who doesn't take those probabilities into account can hardly be called a Bayesian.

Not at all. If I want to know what the odds are that I have hepatitis given that the test came back positive, I can calculate that very simply from the incidence of hepatitis and the known error rate of the test. I do not need to consider the entire spectrum of things that I might have in order to determine the likelihood of my having a specific named thing.

 

[sol invictus]

Yes, but you don't have to apply Bayes' theorem.

Bayes' theorem is appropriate if you want to make a statement like "the probability that the coin is biased is X%." But if you simply want to state that "the coin is biased," without making a probabilistic assessment of the likelihood that it is biased, then you simply apply a frequesting framework and set an appropriate alpha cutoff.

OK, you sound like you're a frequentist (or at least understand their position). Can I ask you some questions? I've honestly never been able to understand this reasoning.

What's the difference between saying the prob the coin is biased is X%, and setting up a cutoff and saying you're past that cutoff? The second simply contains less information than the first (as far as I can tell).

EDIT - the stuff about patterns in the flips is a red herring (I think). Neither a Bayesian nor a frequentist would notice them if she didn't look. I think we should focus just on the total (heads-tails).

 

[69dodge]

They're irrelevant.

They are quite relevant. If they're taken into account, as they should be, we won't "automatically conclude that the coin is unfair (and was biased to show exactly the pattern that was observed)."

Not at all. If I want to know what the odds are that I have hepatitis given that the test came back positive, I can calculate that very simply from the incidence of hepatitis and the known error rate of the test. I do not need to consider the entire spectrum of things that I might have in order to determine the likelihood of my having a specific named thing.

You need to know (1) the prior probability of having the specific thing, (2) the probability, supposing you have it, of getting the test result you ended up getting, and (3) the probability, supposing you don't have it, of getting the test result you ended up getting.

Translating back to the coin case, if you're trying to decide how likely a coin is to be fair, by tossing it n times and observing the resulting sequence, you need to know (1) the prior probability that it is fair, (2) the probability, supposing it's fair, of getting that sequence, and (3) the probability, supposing it's not fair, of getting that sequence.

Notice that (2) always has the same value, namely 1/2ⁿ, regardless of what sequence is observed. All the interesting stuff happens in (3). And (3) depends on the relative prior probabilities of the various ways in which the coin might be unfair.

 

[Jekyll]

OK, you sound like you're a frequentist (or at least understand their position). Can I ask you some questions? I've honestly never been able to understand this reasoning.

What's the difference between saying the prob the coin is biased is X%, and setting up a cutoff and saying you're past that cutoff? The second simply contains less information than the first (as far as I can tell).

EDIT - the stuff about patterns in the flips is a red herring (I think). Neither a Bayesian nor a frequentist would notice them if she didn't look. I think we should focus just on the total (heads-tails).

My understanding is that frequentist deny that you can assign probabilities to distributions that you can't sample from.

So given a particular coin, it is either biased, or it isn't. The probability is either 0 or 1, it's just that we don't know which one it is. This also holds for individual coin tosses, they each either come up heads of tails, there is no distribution to consider.

As they don't approve of assigning probabilistic weights to uncertainty, they can't apply Bayes theorem to the problem. On the other hand, a bayesian can and so would say that the probability of a coin being unbiased is P(S|unbiased)P(unbiased) where S is the relevant sample information and P(unbiased) your initial a priori probability.

As a frequentist doesn't have this initial P(unbiased), they will:
1)assign different weights to the possible outcomes compared to a bayesian using informative priors.
2)not look to generate an updated probability,as they believe the idea to be meaningless.They just want to know if it is reasonable to continue holding their initial assumptions.

 

[Walter Wayne]

Does it?

50 heads, followed by 50 tails, or 50 Head-Tail pairs would result in the null-hypothesis being accepted (p=0.0). An experimenter with prior belief about the properties of a (not-)fair coin would notice these patterns.

All a frequentist would say is he'll make a mistake 100*alpha% of the time and reject a coin which was actually fair, or even more uselessly just quote a p-value (zero in the above cases) and let some other sucker make the decision. (Let's ignore type-II/beta-errors.)

ETA: 69dodge beat me to it!

Well if your null hypothesis is that the coin is 'fair' then it has been confirmed. But when you consider coin mechanics, you want your null hypothesis to be that it is fair, that the process is "stationary" (the probability doesn't change over time) and that coin tosses are statistically independent of each other (the result of one coin toss is not affected by the result of previous coin tosses).

If you look at the two-sequences you mentioned, they pass a test of the mean, but fail tests showing individual tosses to be independent of eachother.

Walt