So you're claiming that, given n Bernoulli trial outcomes, you should simulate more (but at most n more) by drawing from those n without replacement. Would you care to make an argument for why that's "more correct" than drawing *with* replacement? --Michael On Sun, Jun 24, 2012 at 8:41 PM, James Propp <jamespropp@gmail.com> wrote:
Right. There's no way to get rid of this correlation. But that's ok; the terms of the puzzle don't require that X' be independent of X.
Jim
On 6/24/12, Tom Karzes <karzes@sonic.net> wrote:
You can simply draw the values from a hat, or randomly permute a string of H's and T's and then discard all but the first n'. But no matter what you do, your solution will be strongly correlated with the sample provided by your friend, rather than independently random.
Tom
James Propp writes:
You can't truncate the bit-string because you don't know what the individual bits are: just how many H's and how many T's.
Jim
On 6/24/12, Michael Kleber <michael.kleber@gmail.com> wrote:
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
_______________________________________________ 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
-- Forewarned is worth an octopus in the bush.