The NY Times Science Section (11 January 2011) has an article relating to the testing of a coin suspected of being biased in favor of Heads. It discusses the following hypothetical results. A coin is tossed 1000 times & lands heads 527 times. A true coin would result in 526 or fewer Heads about 95.3% of the time. 5% is usually considered the cutoff indicating a statistically significent result. The above would be traditionally viewed as indicating that the coin is biased. The article makes the following statement (paraphrase, not true quote). The article does not indicate how to calculate the probability of tossing exactly 527 heads with a biased coin. I have no idea how to calculate this probability, which obviously requires assumptions or data relating to the characteristics of the allegedly biased coin. Does anyone here have an idea relating to such a calculation? It would be incredibly time consuming, but one could make 1000 sets of tosses with 100 tosses in each set or 100 sets with 1000 tosses in each set. Having done all that coin tossing, the results could be plotted & compared with the bell-shaped curve associated with tossing a true coin. BTW: The article mentions ESP Testing originally done at Duke University & later done at various other colleges/universities. The testers generally claimed statistically significant results, which I (& many others) do not accept due to considering the experimental design to be flawed.
Although this doesn't answer your query, it is on the subject of coin tosses. I've noticed that if you have a sufficiently bright enough light to reflect the top of the coin, you can stop the flip any way up you choose. You just have to wait for the visual cue. So I guess I've just added the parameter that the coin has to be flipped and free fall to the ground with no further assistance to designate an outcome. (Of course then you can start querying the rate of torque applied, the arc and the height of the flip, since this too would fortify an outcome.)
I have lots to say about this since I do work on related things (statistics wise, not coin wise Please Register or Log in to view the hidden image!), but don't have time to get into just now, maybe I'll come back later. For now though, I'll answer your actual question: "calculate the probability of tossing exactly 527 heads with a biased coin" So, the probability of getting exactly some sequence of tosses HHTTHT...HHTH etc for n tosses, in which H of them are heads, where the probability of tossing a head is \(PrH=whatever\), is \(P=(PrH)^H (PrT)^T\) where of course PrT = 1-PrH and T=n-H But you don't care which exact sequence it is, so you have to multiply by the number of such sequences which give you the same number of heads. This number is \(mult=\frac{n!}{H!T!}\), or \(C^n_H\) (n choose h) if you prefer (the n,h binomial coefficient) So overall the probability is prob(H heads in n throws)\( = P \times mult\) So for the fair coin PrH=0.5, so the calculation is prob(527 heads in 1000 throws)\( = (0.5)^{1000} \times C^{1000}_{527}=0.58742%\) Also quickly, regarding the hypothesis test, keep in mind that 5% is 1 in 20, so 1 in 20 such experiments you expect to see this result. It is "statistically significant" according to the doctrine, but really that just means it is worth doing the experiment again to see if it happens again. I wouldn't base any important decisions on it. And prior information is very important, for instance if the coin just came out of a change machine it is pretty damn unlikely to be biased a priori, so the probability that the observed result is just a fluke is much much higher than if you are watching some magician flip a coin.
Kurros: Some of your notation is a bit unfamiliar to me. You moved a decimal point on your calculation of probability(527 Heads in 1000 tosses). It is 0.5874% not 5.874%
Whoops, so I did, fixed. What in particular concerns you? I can explain any part in more detail if you like or resolve whatever notation issues there are. Was it the choose? i.e. \(C^a_b=\frac{a!}{b!(a-b)!}\)?
Here's a somewhat related, pretty easy interview question, slightly rephrased. (I got it right.) Suppose you have a coin which you know is not fair. Using this unfair coin, and only this coin, how can you simulate a toss from a fair coin?
What if we have to pick a sequence of two tosses instead, HT vs TH? Throw away HH and TT as garbage if they come up. Maybe you can do it with less wastage though *shrugs*.
How about choosing any sequence with parity? (e.g. TH vs HT, HHTT vs HTHT vs THTH vs TTHH...) The problem with this is that it requires an unknown, potentially infinite, number of tosses. Here's an idea: toss the coin, player A chooses "H or T" while at the same time player B chooses "keep or conjugate" which decides what player A's actual choice is...hah
If it helps to see the same thing in slightly different notation, then if p is the probability of tossing the biased coin and getting heads, the probability of tossing N coins and getting k heads is \(C^{N}_{k} p^{k} (1-p)^{N-k} \;.\)As kurros explained, the \(p^{k} (1-p)^{N-k}\) bit is the probability of getting a particular sequence with k heads in it (eg. HHTT) and the \(C^{N}_{k}\) bit is the total number of sequences with k heads (eg. HHTT, HTHT, HTTH, ...). Note that this only works if both players commit their choices before tossing the coin (eg. by noting them down and putting them in envelopes). But if you think the players will make good random bit generators then you don't even need a coin: just have each player choose a random bit and xor them to get the result.
. Yep I thought of that, which is why I said they have to choose "at the same time", which must occur before the coin lands. You're also right that this is no different than one of the players choosing "odds or evens" followed by both players throwing up either 1 or 2 fingers. Maybe we could say the coin toss throws in an extra layer of randomness, whereas a game that relies completely on human decision could be more easily exploited (e.g. a really rotten "rock paper scissors" player could be beaten every time). Is there another answer to Ben's question that isn't possibly subject to infinite coin tosses?
No, the coin is fair. Stryder is tossing it from beneath a sufficiently bright light source. Please Register or Log in to view the hidden image!
You could, though remember you're doing this in the first place because the coin is biased. Your idea could dampen that bias, but it wouldn't eliminate it unless the players themselves made perfectly unbiased random choices. What's wrong with the idea kurros suggested? Granted there's no guaranteed upper bound on the number of coins you'd have to toss, but in practice it should produce a result reasonably fast unless the coin is heavily biased. Personally I doubt it's going to be possible to come up with a protocol much better than the one he suggested that actually uses the coin as the source of randomness. Actually, here's a shot at a proof (by contradiction) of that: suppose I have a general protocol that could always produce a perfectly fair result in a guaranteed finite number n(p) of coin tosses, where I'm allowing that number to depend on the probability p that a single toss of the coin produces the result "heads". More formally, I can think of a protocol as a function f[sub]p[/sub], intended for use if the coin has bias p, that associates either 0 or 1 to each binary string of length n(p) (representing the possible sequences of n(p) coin tosses). Now, the problem is that there are an uncountable infinity of possible values of p, but only a countable infinity of possible values of n. That means that at least some values of n are going to have to be shared by different values of p. Even there, for a fixed number n of coin tosses, there are only a finite number of possible protocols (specifically, 2[sup]2[sup]n[/sup][/sup] of them), so there will exist protocols that have an (uncountably) infinite number of biases p associated with them. Now take such a protocol f, that has an infinite number of biases p associated with it, and say it employs n coin tosses. Given f and p, the probability of obtaining the result "1" is \( P(1) \,=\, \sum_{ \{ a_{k} \} } f(a_{1},\, \ldots,\, a_{n}) \, p^{\sum_{k=1}^{n} a_{k}} \, (1-p)^{n - \sum_{k=1}^{n} a_{k}} \)where the outer sum is over all the possible binary sequences where each a[sub]k[/sub] takes on the values 0 or 1. If the protocol works, then I'm claiming that P(1) = [sup]1[/sup]/[sub]2[/sub] for this fixed protocol f for the uncountably infinite number of biases p this protocol is supposed to work for. Or stated differently, I'm claiming the finite polynomial \( \sum_{ \{ a_{k} \} } f(a_{1},\, \ldots,\, a_{n}) \, p^{\sum_{k=1}^{n} a_{k}} \, (1-p)^{n - \sum_{k=1}^{n} a_{k}} \,-\, \frac{1}{2} \)has uncountably infinite roots. Of course, finite polynomials of degree n have at most n real roots, so this isn't possible. Conclusion: if you have a biased coin that has a probability p of producing "heads" when tossed, there are necessarily values of p for which it is impossible to simulate a perfectly fair coin toss in a guaranteed finite number of tosses of the biased coin. (It's also obvious that these values of p will include all the transcendental numbers.)
Is this a lateral thinking type question? Is there an answer for the extreme case: P(head)=1? Does "using... only this coin" mean you can't mark the coin (you can use your hands, obviously, so why not the marker pen I usually carry)?
That's pretty impressive przyk. I'm not sure where the line of pedantry lies but since we're trying to relate abstract theory to the real world, and given the finite number of quantum states of a coin, are we sure of the following? Putting it another way, if p were limited to rational values are we still unable to come up with a method that is guaranteed to terminate? When I asked the question I suspected the answer was no because of the case when the coin produces nothing but H, for example (Pete mentioned this also). Notice that this also breaks Kurros' method. This is why I suggested what I did, even if it was tongue-in-cheek, because my method survives the limiting case even if it's a bit of a hack Please Register or Log in to view the hidden image!
My point relates to the magazine article sited in post 1. Because the results differ by 1 from the 'ideal' statistical pattern is no reason to suspect bias (maybe in a paranoid world). The randomness of coin tosses, even assuming 'ideal' coins, is time independent, therefore you can't predict when any specific pattern occurs. If a lottery produced the same numerical sequence x days in a row, many would suspect the results are manipulated. What the're really saying, based on a misunderstanding of randomness and a false sense of determinism is 'it can't happen in my lifetime'. An appeal to long periods of time, and the notion of a 'rare' event. This is based on an actual event many years ago involving a state lottery and the reaction by a group of university students, which was published in the local city paper. For quality control purposes, if you plot the results of a process in real time using sampling, and notice changes that form a trend, you can then isolate the factors to determine the cause. That would be my suggested method for resolution if needed. In a world history with dishonesty at so many social levels, suspicion will usually require/demand it.
Phyti: Do you really need an answer to the following? I would call it biases. 1000 tosses of a true (or unbiased coin) would be expected to result in approximately 500 Heads & 500 Tails. A True coin would occasionally favor Heads over Tails (or vice versa) by 520 (or more) to 480 (or less). Perhaps 1000 to zero might be described by some word other than biased (Like 2-Headed), since 600 Heads to 400 Tails would indicate a definite bias in favor of Heads.
Er, why should a coin only have a finite number of quantum states? (You might have meant "discrete" rather than "finite". Even there, I'm not sure I'm convinced.) Intuitively I'd expect it to be possible for rational biases. I haven't sat down to try to figure out a specific method, though for a rational bias of p/q (in simplest terms) I'd expect the number of necessary coin tosses to be q or some multiple or power of it, which would be consistent with the protocol breaking for a perfectly biased coin. (Thinking about perfectly biased coins is also the sort of thing I was thinking about that eventually got me to the impossibility proof I posted earlier. It seems just about everyone had that idea. Obviously a protocol that still works if the coin is perfectly biased isn't actually using the coin as the source of randomness.)
Actually: I take that back. It's clearly impossible for P(Heads) = 1/3, since the probability of any sequence of n tosses will always be (some integer)/3[sup]n[/sup], and there will be no way of adding these to get 1/2.
