Then why don't you just repeat the first n' coin tosses each time? What advantage do you get from randomly permitting her sequence before truncating it? --Michael On Jun 24, 2012 2:30 PM, "James Propp" <jamespropp@gmail.com> wrote:
Each time the game is repeated, your friend tosses n real coins and you announce the tosses of n' imaginary coins. It's crucial that your friend generates new tosses (using the same bias, of course).
Jim
On 6/24/12, Michael Kleber <michael.kleber@gmail.com> wrote:
What? Maybe I was confused about the problem. Suppose the flip sequence I'm learning from is HH. Then when I predict a single coin flip, I'll predict heads every time, but my friend might well have a fair coin. What am I missing?
--Michael On Jun 24, 2012 10:47 AM, "James Propp" <jamespropp@gmail.com> wrote:
This is correct. Note that you don't need to know the initial sequence of 0's and 1's in order to generate a random permutation of it; it's enough to know the number of 0's and 1's.
The solution I had in mind was an iterative one that successively computes random variables distributed like Binomial(p,n-1), Binomial(p,n-2),...,Binomial(p,n'), where at each stage you throw out one of the bits at random. E.g., at the first stage, you reduce X to X-1 with probability X/n and leave it alone with probability (n-X)/n. Another description of this is Dither(((n-1)/n)X), where Dither(t) denotes a random variable that takes on the values floor(t) and ceiling(t) (and no other values) with expected value exactly t. Then we multiply by (n-1)/(n-2) and dither again, etc.
Jim
On 6/23/12, Warren Smith <warren.wds@gmail.com> wrote:
Jim Propp: Let me phrase the puzzle in a more (math-)fun way. A friend of yours has a biased coin, but she won't tell you what the bias p is ("Hey, I'm not THAT good a friend!"). She tosses the coin n times and tells you how many times it came up heads (call it X), and then she gives you a positive integer n'<n. Your job is to use n, n', and X, along with some supplemental randomness, to generate a number X' that is statistically indistinguishable from the (random) number of heads you would get if you tossed your friend's coin n' times. Note that you do not have access to your friend's coin; that is to say, you don't know its bias. Nonetheless, you can effectively simulate n' tosses of your friend's coin if she does you the favor of tossing it n times, where n'<n, and telling you how many heads she observed. Note that X' need not be independent of X. All we require is that X' is governed by the binomial distribution Binomial(p,n') provided that X is governed by the binomial distribution Binomial(p,n). I stress that the point of the puzzle is to find a way to do this that doesn't require knowledge of p. By the way, what's the quickest way to see that you CAN'T accomplish the above if n' is bigger than n?
--re the final sentence, if n=1 it seems clear you cannot simulate n'=1000 tosses just based on knowing whether that 1 toss came up heads. You need continuum information (value of p) to do so well in the limit of large n', but you have only 1 bit of information (heads/tails).
--re the simulation problem when n'<n, proceed thus. Regard the n old tosses (of which X are heads) as a string of n bits, X of them 1-bits. Randomly permute the bits. Now, as your output, generate the number of 1-bits among the first n' bits in your permuted bitstring. It seems to me that if X is a genuine sample from the binomial(n,p) distribution, then your output must be a genuine sample from the binomial(n',p) distribution.
(By the way, I never looked at Propp's original puzzle since I had no idea what a "Galton board" was. I figured it was something to do with genetics. But googling tells me that guess was totally wrong.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun