[math-fun] how to test whether a coin is fair
The definition of a "fair coin" is exactly 1/2 probability of heads and of tails. No "opinion" is involved. I am allowing you to assume all coin tosses are truly independent. Clearly, an unfair coin, no matter how tiny its unfairness, could be detected with confidence 1-K, for given K as small as one would like, after a large enough number of tosses. A fair coin, however, could never be proven fair, and then the testing procedure will simply keep going (or, with probability<=K, terminate and wrongly report coin is unfair -- that is what "confidence" means). Gene Salamin's remark about using another (H,T) is not correct, or at least highly inefficient, because previous experiment was subset of new experiment, and his formulas ignore that. So the question is a simple one: how should we best test the fairness of a coin? (With some specified confidence?) But it is not so easy to answer. In fact so far no math-funner besides me even seems to have comprehended the question... But I believe there probably is a unique answer, i.e. a uniquely optimal statistical test, and have sketched how to characterize that answer as a certain constrained variational problem. This characterization is unsatisfying as matters presently stand.
What's your take on https://en.wikipedia.org/wiki/Checking_whether_a_coin_is_fair ? On Fri, Mar 4, 2016 at 5:17 PM, Warren D Smith <warren.wds@gmail.com> wrote:
The definition of a "fair coin" is exactly 1/2 probability of heads and of tails. No "opinion" is involved.
I am allowing you to assume all coin tosses are truly independent.
Clearly, an unfair coin, no matter how tiny its unfairness, could be detected with confidence 1-K, for given K as small as one would like, after a large enough number of tosses.
A fair coin, however, could never be proven fair, and then the testing procedure will simply keep going (or, with probability<=K, terminate and wrongly report coin is unfair -- that is what "confidence" means).
Gene Salamin's remark about using another (H,T) is not correct, or at least highly inefficient, because previous experiment was subset of new experiment, and his formulas ignore that.
So the question is a simple one: how should we best test the fairness of a coin? (With some specified confidence?) But it is not so easy to answer. In fact so far no math-funner besides me even seems to have comprehended the question... But I believe there probably is a unique answer, i.e. a uniquely optimal statistical test, and have sketched how to characterize that answer as a certain constrained variational problem. This characterization is unsatisfying as matters presently stand.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Assuming a fixed probability per toss, with each toss independent of each other toss, I believe The Law of Large Numbers says that h/(h+t) must converge to the true probability of the coin landing on "heads". Tom Mike Stay writes:
What's your take on https://en.wikipedia.org/wiki/Checking_whether_a_coin_is_fair ?
True, but not useful if one can only perform finitely many tosses. -- Gene From: Tom Karzes <karzes@sonic.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, March 4, 2016 6:28 PM Subject: Re: [math-fun] how to test whether a coin is fair Assuming a fixed probability per toss, with each toss independent of each other toss, I believe The Law of Large Numbers says that h/(h+t) must converge to the true probability of the coin landing on "heads". Tom Mike Stay writes:
What's your take on https://en.wikipedia.org/wiki/Checking_whether_a_coin_is_fair ?
Not *exactly* true. A fair coin can have any sequence in {H, T}^omega show up. The probability is often 0, but that doesn't keep something from happening. —Dan
On Mar 4, 2016, at 6:48 PM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
True, but not useful if one can only perform finitely many tosses.
-- Gene
From: Tom Karzes <karzes@sonic.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, March 4, 2016 6:28 PM Subject: Re: [math-fun] how to test whether a coin is fair
Assuming a fixed probability per toss, with each toss independent of each other toss, I believe The Law of Large Numbers says that h/(h+t) must converge to the true probability of the coin landing on "heads".
The probability of every sequence will be zero. Even the subset of all sequences in which |H-T|<2 will be of measure zero. So if you actually want an operational test you need to define some range (0.5-e, 0.5+e) you will consider "fair". Then you can define a test have specified probabilities of alpha/beta errors. Brent On 3/4/2016 9:00 PM, Dan Asimov wrote:
Not *exactly* true. A fair coin can have any sequence in {H, T}^omega show up. The probability is often 0, but that doesn't keep something from happening.
—Dan
On Mar 4, 2016, at 6:48 PM, Eugene Salamin via math-fun <math-fun@mailman.xmission.com> wrote:
True, but not useful if one can only perform finitely many tosses.
-- Gene
From: Tom Karzes <karzes@sonic.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, March 4, 2016 6:28 PM Subject: Re: [math-fun] how to test whether a coin is fair
Assuming a fixed probability per toss, with each toss independent of each other toss, I believe The Law of Large Numbers says that h/(h+t) must converge to the true probability of the coin landing on "heads".
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Perhaps (I am not optimistic) the following will make things clearer. This is the best coin-testing protocol currently known to me (although its validity is not currently proven, it appears valid in some tests): COINTEST(K){ //unfairness test with confidence>=1-K of correctness assert(0<K and K<1); A=7.1; B=2.7; C=1.02; N=1; LoopForever{ TossCoin and let D=T-H where T=#tails and H=#heads so far and T+H=N; X = (D*D)/(2*N) - ln(A+ln(B+N)); if(X>C*ln(1.0/K)){ return( COIN_SEEMS_UNFAIR ); } N = N+1; } } This procedure does not give a damn whether your coin is biased to 0.51, or 0.5001, or 0.500001, or any number at all. No matter what number it is, if the number is not exactly 0.5, then this procedure will eventually (with probability=1) return "UNFAIR". If the coin is fair, i.e. the bias is exactly 0.5, then this procedure will either never terminate (with probability >= 1-K) or will terminate wrongly reporting UNFAIR (with probability <= K). The question is whether this procedure really meets those guarantees, and what is the "best" procedure which does. Here "best" has a precise meaning, e.g. least expected runtime before termination if coin bias uniform[0,1]. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
WDS: Your definition is a legitimate one, but nonconstructive, in the sense that, as you already acknowledge, a coin can never be certified to be fair. That's an unhelpful definition to a manufacturer of fair coins. "Gene Salamin's remark about using another (H,T) is not correct, or at least highly inefficient, because previous experiment was subset of new experiment, and his formulas ignore that." I don't understand. If you have h heads and t tails, the posterior is known, and is independent of the sequence of heads and tails. This assumes a "fair" coin tossing procedure, and a particular prior. Yes, one can argue that the choice of prior is a personal opinion, but if h+t >> 1, the data overwhelms the prior. A Bayesian would say that a coin is (e1,e2,e3) certified if, from the posterior, we have (where x is the probability of heads) Prob(0.5 - e1 < x < 0.5 + e2) > 1 - e3. The manufacturer can then test and certify to this standard. You want smaller e's? You pay more. -- Gene From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Friday, March 4, 2016 5:17 PM Subject: [math-fun] how to test whether a coin is fair The definition of a "fair coin" is exactly 1/2 probability of heads and of tails. No "opinion" is involved. I am allowing you to assume all coin tosses are truly independent. Clearly, an unfair coin, no matter how tiny its unfairness, could be detected with confidence 1-K, for given K as small as one would like, after a large enough number of tosses. A fair coin, however, could never be proven fair, and then the testing procedure will simply keep going (or, with probability<=K, terminate and wrongly report coin is unfair -- that is what "confidence" means). Gene Salamin's remark about using another (H,T) is not correct, or at least highly inefficient, because previous experiment was subset of new experiment, and his formulas ignore that. So the question is a simple one: how should we best test the fairness of a coin? (With some specified confidence?) But it is not so easy to answer. In fact so far no math-funner besides me even seems to have comprehended the question... But I believe there probably is a unique answer, i.e. a uniquely optimal statistical test, and have sketched how to characterize that answer as a certain constrained variational problem. This characterization is unsatisfying as matters presently stand.
participants (6)
-
Brent Meeker -
Dan Asimov -
Eugene Salamin -
Mike Stay -
Tom Karzes -
Warren D Smith