Re: [math-fun] reverse-engineering Galton boards
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it. We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row). If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)". Jim Propp
Here is an interactive Flash-based simulator: http://www.mathsisfun.com/data/quincunx.html Wikipedia (in their infamous editorial fascism) thinks it should be called a "Bean machine". But their article has two good pictures including the Galton patent: http://en.wikipedia.org/wiki/Bean_machine Googling "quincunx" will likely show things that have only 5 spots (as shown at http://en.wikipedia.org/wiki/Quincunx). On 6/13/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it. [...]
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do. I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.) Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p. Jim Propp On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
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? Jim Propp On Fri, Jun 22, 2012 at 11:55 PM, James Propp <jamespropp@gmail.com> wrote:
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do.
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p.
Jim Propp
On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
Jim Propp
That's a very nice result! Is it well-known, or home-grown? WFL On 6/23/12, James Propp <jamespropp@gmail.com> wrote:
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?
Jim Propp
On Fri, Jun 22, 2012 at 11:55 PM, James Propp <jamespropp@gmail.com> wrote:
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do.
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p.
Jim Propp
On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Re the 11:55 PM post (at bottom), all I can think of is that if all transition probabilities are the same 2-vector: (horizontal, vertical) = (p,q) = (p,1-p), then the coefficients of the polynomial Q(t) := (p+qt)^n are the striking probabilities along the diagonal i+j = n. (More generally, if the transition probabilities for each point on the diagonal D_k = {(i,j) | i+j = k} are all the same 2-vector (p_k, q_k) for 0 <= k < n, then the striking probabilities on D_n are the coefficients of Q(t) := Prod_{0 <= k < n} (p_k + q_k*t).) Re the 1:11 AM post (immediately below): If each time a biased coin with Prob(H) = p is tossed n times, you are told the number #(H;n) of heads, then a statistically indistinguishable simulation of n' <= n tosses of the coin would be to toss, n' times, a biased coin having Prob(H) = #(H;n)/n. (To me, this makes sense only if [the friend tosses the coin n times and you toss it n' times] in each of infinitely many trials; correctly simulating a probabilistic law in only finitely many tosses doesn't seem well-defined to me.) But I'm not seeing right away how that solves the problem of reverse-engineering Galton boards. On 2012-06-23, at 1:11 AM, Jim <jamespropp@gmail.com> wrote:
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?
On Fri, Jun 22, 2012 at 11:55 PM, Jim <jamespropp@gmail.com> wrote:
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do.
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p.
Jim Propp
On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
Jim Propp
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dan writes: "(To me, this makes sense only if [the friend tosses the coin n times and you toss it n' times] in each of infinitely many trials; correctly simulating a probabilistic law in only finitely many tosses doesn't seem well-defined to me.)" This is the standard frequentist view: probability only makes sense as asymptotic frequency. "But I'm not seeing right away how that solves the problem of reverse-engineering Galton boards." The "dithering" scheme I described in my last post on the coin-tossing problem gives an iterative method for choosing target probability distributions at the second-to-last, third-to-last, ..., second, and first levels of the Galton board; from those distributions, one can compute the required bias at each junction. Yes, that's horribly cryptic, and I apologize; I wouldn't even understand the above if I hadn't been the one to write it. I'd try to write something clearer, but I have to give my kids breakfast now. Jim On 6/23/12, Dan Asimov <dasimov@earthlink.net> wrote:
Re the 11:55 PM post (at bottom), all I can think of is that if all transition probabilities are the same 2-vector: (horizontal, vertical) = (p,q) = (p,1-p), then the coefficients of the polynomial Q(t) := (p+qt)^n are the striking probabilities along the diagonal i+j = n.
(More generally, if the transition probabilities for each point on the diagonal D_k = {(i,j) | i+j = k} are all the same 2-vector (p_k, q_k) for 0 <= k < n, then the striking probabilities on D_n are the coefficients of Q(t) := Prod_{0 <= k < n} (p_k + q_k*t).)
Re the 1:11 AM post (immediately below): If each time a biased coin with Prob(H) = p is tossed n times, you are told the number #(H;n) of heads, then a statistically indistinguishable simulation of n' <= n tosses of the coin would be to toss, n' times, a biased coin having Prob(H) = #(H;n)/n.
(To me, this makes sense only if [the friend tosses the coin n times and you toss it n' times] in each of infinitely many trials; correctly simulating a probabilistic law in only finitely many tosses doesn't seem well-defined to me.)
But I'm not seeing right away how that solves the problem of reverse-engineering Galton boards.
On 2012-06-23, at 1:11 AM, Jim <jamespropp@gmail.com> wrote:
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?
On Fri, Jun 22, 2012 at 11:55 PM, Jim <jamespropp@gmail.com> wrote:
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do.
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p.
Jim Propp
On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
Jim Propp
_______________________________________________ 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
Although I don't understand Jim's comment about dithering random variables, I've been able to find a linear map from the simplex S_n (defined as the points in the non-negative orthant of R^(n+1) whose sum of coordinates = 1) of all probability distributions on the set {0,1, . . .,n} of n+1 points (i.e., all possible sets of striking probabilities on the plane diagonal of integer points with i+j=n in the first quadrant), to S_(n-1), that takes the binomial distribution Binomial(p,n) to Binomial(p,n-1) (for each p in [0,1]). I guess these are what Jim is referring to. Since the binomial distributions for all p just form a curve in the simplex S_n, I may have to think a little harder to see that these linear maps L_n : S_n -> S_(n-1) are uniquely determined by the property of taking Binomial(p,n) in S_n to Binomial(p,n-1) in S_(n-1) for each p. --Dan Jim wrote:
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Dan has it exactly right. To see why the solution is unique, write all the equations as linear equations over the ring of polynomials of degree n. With respect to the monomial basis, the system becomes upper triangular. I apologize for the extra head-scratching caused by the over-terseness of my postings. Sometime over the next year I'll write all this up in a careful (and hopefully clear) way. Jim On 6/25/12, Dan Asimov <dasimov@earthlink.net> wrote:
Although I don't understand Jim's comment about dithering random variables, I've been able to find a linear map from the simplex S_n (defined as the points in the non-negative orthant of R^(n+1) whose sum of coordinates = 1) of all probability distributions on the set {0,1, . . .,n} of n+1 points (i.e., all possible sets of striking probabilities on the plane diagonal of integer points with i+j=n in the first quadrant), to S_(n-1), that takes the binomial distribution Binomial(p,n) to Binomial(p,n-1) (for each p in [0,1]).
I guess these are what Jim is referring to.
Since the binomial distributions for all p just form a curve in the simplex S_n, I may have to think a little harder to see that these linear maps
L_n : S_n -> S_(n-1)
are uniquely determined by the property of taking Binomial(p,n) in S_n to Binomial(p,n-1) in S_(n-1) for each p.
--Dan
Jim wrote:
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's a worked example of reverse-engineering a Galton board: Suppose the target distribution is (.1,.2,.3,.4). That is, we want this to be the distribution of "mass" at the bottom of the Galton board. Here's a picture that may be helpful, best viewed in fixed font (is there a good way to imbed fixed-font text in postings sent via gmail?): A / \ / \ / \ B C / \ / \ / \ / \ / \ / \ D E F / \ / \ / \ / \ / \ / \ / \ / \ / \ G H I J We have mass 1/10 at G, mass 2/10 at H, mass 3/10 at I, and mass 4/10 at J. We let the mass flow upward through the diagram in such a way that mass is conserved at each vertex (so that mass .1+.2+.3+.4=1 arrives at A), with the property that the way the mass splits as it goes up is governed by specific ratios. If we let DG denote the amount of mass flowing upward along edge DG, then the ratios are as follows: DH:EH=1:2 EI:FI=2:1 BE:CE:1:1 The general pattern might be clearer if we introduce extra vertices denoted by "*" along the borders of the diagram and write *G:DG=0:3, DH:EH=1:2, EI:FI=2:1, FJ:*J=0:3 *D:BD=0:2, BE:CE=1:1, CF:*F=2:0 *B:AB=1:0, AC:*C=0:1 Anyway, we find the following upward flows along the edges: DG=3/30, DH=2/30, EH=4/30, EI=6/30, FI=3/30, FJ=12/30 BD=1/6, BE=1/6, CE=1/6, CF=3/6 AB=1/3, AC=2/3 Now reverse the flow, so that all the mass flows down, and choose the bias at each junction to be whatever it needs to be to give these same flows. In our case, the biases at A, B, C, D, E, and F turn out to be 1:2, 2:2, 1:3, 3:2, 2:3, and 1:4. I'm sure that's unclear, but hopefully it's unclear in a different way than my earlier postings. As I mentioned, I will be writing this up at some point... Jim On Fri, Jun 22, 2012 at 11:55 PM, James Propp <jamespropp@gmail.com> wrote:
I found the answer I was looking for. It doesn't involve any optimization; it just involves algebra (mostly linear algebra), and it's the Right Thing to Do.
I'll pose the key idea in the form of a puzzle: Find the linear map that sends probability distributions on {0,1,...,n} to probability distributions on {0,1,...,n-1} with the property that for every p, the map sends the distribution Binomial(p,n) to the distribution Binomial(p,n-1). (Here we treat probability distributions as vectors in the obvious way.)
Did any of you already know that such a "one size fits all" linear map exists? A priori you might think that you'd need to know p.
Jim Propp
On 6/12/12, James Propp <jamespropp@gmail.com> wrote:
Dan Asimov rightly points out that I should say what I mean by a Galton board, since some of you may not have heard of it.
We feed a marble into a router at the top of the device (call the router A1) that randomly routes a marble either down and left (to a router we'll call B1) or down and right (to a router we'll call B2). B1 routes marbles randomly to either C1 or C2, while B2 routes marbles randomly to either C2 or C3. And so on. The nth router in some row routes marbles either to the left (to the nth router in the next row) or to the right (to the n+1st router in the next row).
If this is still unclear, let me know, and I'll try to include an ASCII art sketch or find an image and explanation on the web. Note that another word for a Galton board is a quincunx. A more suggestive and apt name would be "That thingy that they have at science museums that's supposed to demonstrate Gaussian distributions (but sometimes doesn't because balls' momentum can lead to fatter tails)".
Jim Propp
participants (4)
-
Dan Asimov -
Fred lunnon -
James Propp -
Robert Munafo