[math-fun] how to test whether a coin is fair?
WDS: You have a coin. You want to know whether it is fair. An unbounded testing procedure is as follows:
for(N=1,2,3,...){ Toss coin. Update head and tails counts H & T (with H+T=N). If( |H-T| > F(N,K) ){ output "coin is unfair with confidence>1-K" and stop. } }
The key is the magic function F(N,K). What should it be?
Roughly speaking I think it ought to be F(N,K) =approx= sqrt(2*N*(C*ln(1/K)+ln(A+ln(B+N)))) where A and B and C are appropriate positive constants. Using A=7, B=2, and C=1 seems to work not too horribly provided N>=8. But I do not know what the best values of A,B,C are nor whether this F(N,K) formula really has much validity.
--the following seems to work better: A=8, B=3, C=1.
From: Eugene Salamin <gene_salamin@yahoo.com>
This can be cast as a Bayesian probability. Let x be the probability of heads. We need a prior probability for x, which I will just assume is uniform. Then the posterior probability for x is
P(x) = C x^h (1-x)^t,
where C is a normalizing constant. The matter of whether the coin is "fair" lies outside of probability. It is personal opinion, or, being fancy and minimizing risk over the consequences, is decision theory.
--Well, not quite. First, the whole "personal opinion" jive is only if we are willing to throw all of the theory of designing statistical tests, in the garbage as all bullshit. I'm not. I like your idea of trying to be Bayesian with uniform prior. I personally had been being nonBayesian and thinking about "confidence bounds." However, my test was NOT for one specific number of coin tosses and hence one specific (H,T). It was for keeping on tossing coins forever until one day (maybe) your unfairness criterion is exceeded, whereupon you stop and report the coin is unfair with some "confidence" >=1-K. If it is a fair coin, then with probability>=1-K that day will never come. So basically, the definition of K can be back-deduced from the definition of F(N,K) by asking "what is the probability this procedure will terminate?" Answer P should equal 1-K. If it does not, then our definition of F(N,K) was not quite correct. Mine undoubtably is not quite correct, but seems to come close in the sense that P appears to approximately equal 1-K throughout the range 0.0001 <= K <= 0.25. Specifically with A=8, B=3, and all N from 4 to 10000, the correct value of C always appears to be in [0.91, 1.05]. I'm not sure if what I just said about P=1-K uniquely determines F(N,K). If there still is freedom of choice, then we want the prescription yielding the "most power"... meaning that if the coin is biased, then the expected wait time before detection, is minimized. This if we assume a prior (such as Eugene Salamin's uniform prior, or one could use others) on the coin bias x, is a well defined quantity for any particular correct F(N,K).
From: Kerry Mitchell <lkmitch@gmail.com> It seems to me that |H-T| will tend to infinity as N goes to infinity (albeit at a slower rate),
--true. In fact the "law of the iterated logarithm" says that for a fair coin, with probability=1, we have lim sup |H-T| / sqrt(2*N*lnlnN) = 1 when N=total # coin tosses --> infinity, and H and T are functions of N=1,2,3,... I.e. this limsup both exists with probability=1, and its value is exactly 1 with probability=1. My F(N,K) of course is based on that law, but goes further, offering a considerably more precise statement. Or at least, if would, if my F(N,K) were correct, or could be proven correct to within some known upper & lower bounds.
There's also the question of the distribution of the flips--one could have a coin with the perfect numbers of flips, but, over the long run, if the distribution were exactly predictable (say, H, T, H, T, H, T, etc.), that would be a good argument for the coin not being fair.
--I will allow you to assume, for purposes of this problem, that all flips truly are independent. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The Bayesian method is not for one specific h and t. After each toss, the posterior is updated. If at some point, your decision theoretic criterion for fairness or unfairness is satisfied, you can stop and report your decision. But how can the definition of fairness be anything other than personal opinion? -- Gene From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Friday, March 4, 2016 4:14 PM Subject: [math-fun] how to test whether a coin is fair?
WDS: You have a coin. You want to know whether it is fair. An unbounded testing procedure is as follows:
for(N=1,2,3,...){ Toss coin. Update head and tails counts H & T (with H+T=N). If( |H-T| > F(N,K) ){ output "coin is unfair with confidence>1-K" and stop. } }
The key is the magic function F(N,K). What should it be?
Roughly speaking I think it ought to be F(N,K) =approx= sqrt(2*N*(C*ln(1/K)+ln(A+ln(B+N)))) where A and B and C are appropriate positive constants. Using A=7, B=2, and C=1 seems to work not too horribly provided N>=8. But I do not know what the best values of A,B,C are nor whether this F(N,K) formula really has much validity.
--the following seems to work better: A=8, B=3, C=1.
From: Eugene Salamin <gene_salamin@yahoo.com>
This can be cast as a Bayesian probability. Let x be the probability of heads. We need a prior probability for x, which I will just assume is uniform. Then the posterior probability for x is
P(x) = C x^h (1-x)^t,
where C is a normalizing constant. The matter of whether the coin is "fair" lies outside of probability. It is personal opinion, or, being fancy and minimizing risk over the consequences, is decision theory.
--Well, not quite. First, the whole "personal opinion" jive is only if we are willing to throw all of the theory of designing statistical tests, in the garbage as all bullshit. I'm not. I like your idea of trying to be Bayesian with uniform prior. I personally had been being nonBayesian and thinking about "confidence bounds." However, my test was NOT for one specific number of coin tosses and hence one specific (H,T). It was for keeping on tossing coins forever until one day (maybe) your unfairness criterion is exceeded, whereupon you stop and report the coin is unfair with some "confidence" >=1-K. If it is a fair coin, then with probability>=1-K that day will never come. So basically, the definition of K can be back-deduced from the definition of F(N,K) by asking "what is the probability this procedure will terminate?" Answer P should equal 1-K. If it does not, then our definition of F(N,K) was not quite correct. Mine undoubtably is not quite correct, but seems to come close in the sense that P appears to approximately equal 1-K throughout the range 0.0001 <= K <= 0.25. Specifically with A=8, B=3, and all N from 4 to 10000, the correct value of C always appears to be in [0.91, 1.05]. I'm not sure if what I just said about P=1-K uniquely determines F(N,K). If there still is freedom of choice, then we want the prescription yielding the "most power"... meaning that if the coin is biased, then the expected wait time before detection, is minimized. This if we assume a prior (such as Eugene Salamin's uniform prior, or one could use others) on the coin bias x, is a well defined quantity for any particular correct F(N,K).
From: Kerry Mitchell <lkmitch@gmail.com> It seems to me that |H-T| will tend to infinity as N goes to infinity (albeit at a slower rate),
--true. In fact the "law of the iterated logarithm" says that for a fair coin, with probability=1, we have lim sup |H-T| / sqrt(2*N*lnlnN) = 1 when N=total # coin tosses --> infinity, and H and T are functions of N=1,2,3,... I.e. this limsup both exists with probability=1, and its value is exactly 1 with probability=1. My F(N,K) of course is based on that law, but goes further, offering a considerably more precise statement. Or at least, if would, if my F(N,K) were correct, or could be proven correct to within some known upper & lower bounds.
There's also the question of the distribution of the flips--one could have a coin with the perfect numbers of flips, but, over the long run, if the distribution were exactly predictable (say, H, T, H, T, H, T, etc.), that would be a good argument for the coin not being fair.
--I will allow you to assume, for purposes of this problem, that all flips truly are independent. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (2)
-
Eugene Salamin -
Warren D Smith