Biased Coins (Posted on 2005-02-17)

	Submitted by David Shin
Rating: 4.0000 (3 votes)
Solution:	(Hide)
1. No such value exists. To see this, suppose the contrary. Assume that there is some (a/b)-coin that can simulate both a 1/2-coin and a 1/3-coin, where a and b are relatively prime positive integers. Let n be the number of required flips (choose it large enough so that it is the required number to simulate both coins). Let S2 be the set of sequences considered pseudo-heads when simulating the 1/2-coin, and let S3 be the set of sequences considered pseudo-heads when simulating the 1/3-coin (these sets may overlap). For each sequence x, define a function f(x) that outputs the number of heads in that sequence. Now, we have 1/2 = SUM((a/b)^(f(x))(1-a/b)^(n-f(x)), x in S2) and 1/3 = SUM((a/b)^(f(y))(1-a/b)^(n-f(y)), y in S3). Rearranging, these become: b^n = 2*SUM(a^f(x)(b-a)^(n-f(x)), x in S2) and b^n = 3*SUM(a^f(y)(b-a)^(n-f(y)), y in S2) The key observation is that f(x) can equal n for only one sequence x (namely, a sequence of n heads). Thus, looking at the top equation modulo (b-a), we have: a^n = 0 OR 2*a^n (mod (b-a)) where the OR depends on whether the sequence of all heads is included in the sets S2. We see that the two possibilities are actually equivalent, so that a^n = 0 (mod (b-a)). Using the fact that a is relatively prime to (b-a) whenever a is relatively prime to b, this implies that b-a = 1. Applying to Equation 2, and looking modulo a, we similarly get: 1 = 0 OR 3 (mod a) depending on whether the sequence of all tails is included in the sets S3. Since 1=0 (mod a) is impossible, we necessarily have 1=3 (mod a) and so a=2, and so b=3. However, the equation b^n = 2*SUM(a^f(x)(b-a)^(n-f(x)), x in S2) shows that b must be even, a contradiction. 2. Let us attempt a p so that if the coin is flipped twice, the probability of getting HT is 1/6. Such a p satisfies p(1-p)=1/6, and so p may be taken to be (3+sqrt(3))/6. This p clearly simulates 1/3, as the two flip event "HT or TH" occurs with probability 1/6+1/6=1/3. By lucky coincidence, the 3-flip event "HHH or TTT" occurs with probability 1/2, for p^3+(1-p)^3 = (9+5sqrt(3))/36 + (9-5sqrt(3))/36 = 1/2.

	Subject	Author	Date
	Final Part II Thoughts	Steve Herman	2005-02-21 15:34:46
	More part II Thoughts	Steve Herman	2005-02-21 11:39:19
	Part II thoughts	Steve Herman	2005-02-19 10:53:43
	re(3): Simple solution	Steve Herman	2005-02-19 10:34:02
	re(2): Simple solution	Charlie	2005-02-19 02:55:00
	No Subject	Steve Herman	2005-02-18 23:11:25
	re: Simple solution	Steve Herman	2005-02-18 19:01:39
	re: Simple solution	Federico Kereki	2005-02-18 13:27:34
	Simple solution	Old Original Oskar!	2005-02-18 10:51:17