[math-fun] Propp's coin tossing puzzle
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.)
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
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
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
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
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
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
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
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.
Great question! To see why sampling with replacement doesn't work for this problem, it's helpful to take n=n'=2. (I know the original problem stipulated n'<n, but let's pretend I'd written n' \leq n istead.). The number of heads my friend tosses (call it X) will be Binomial(p,2); if I toss a coin of bias X/2 twice, will the number of Heads I toss (call it Y) have unconditional distribution Binomial(p,2)? I say no, because Prob(Y=1) < Prob(X=1). (Indeed, Prob(Y=1) = Prob(X=1)/2, because the only way Y can be 1 is if X is neither 0 nor 2, in which case X is 1, and the conditional probability of Y being 1 is 1/2.) I fear I'm being too terse here, so if this is unclear please let me know and I'll be glad to elaborate! Jim Propp On 6/24/12, Michael Kleber <michael.kleber@gmail.com> wrote:
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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
What was left unclear to my mind was just how one decides whether the "procedure" that was asked for is in fact "statistically indistinguishable" from tossing the biased coin n' times. As Michael points out, a single run of n' (imaginary) tosses won't do the trick. I commented earlier that this made sense to me only if there were infinitely many tosses. I should not have said "only" (and there are subtler objections to this idea, anyway). (I am not a "frequentist", but this earlier suggestion would at least be *one* way to define "statistically indistinguishable . . . with probability 1.) Rather, perhaps one should imagine *all* 2^n ways that the friend's n tosses could come out, and for each of these -- using Warren's procedure -- all n-choose-#(H) ways of ordering the number #(H) of heads among the n tosses. Now consider all the the initial length-n' strings (with multiplicity) of the resulting however-many-bit-strings that is. Call this multiset S. Finally, the procedure was "statistically indistinguishable" from using actual length-n' runs of coin tosses in the first place if each sequence of K heads out of n' tosses occurs in S with the correct frequency. That is, the exact proportion n'-choose-K p^k (1-p)^(n'-k) of all of S. --Dan P.S. I'm still, alas, not yet seeing the connection between this problem and the one of reverse-engineering Galton boards. Jim 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). . . . Michael 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?
. . . [Warren's procedure] is correct. Note that you don't need to know the initial sequenceof 0's and 1's in order to generate a random permutation of it; it'senough to know the number of 0's and 1's The solution I had in mind was an iterative one that successivelycomputes 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.
participants (5)
-
Dan Asimov -
James Propp -
Michael Kleber -
Tom Karzes -
Warren Smith