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