Re: [math-fun] reverse-engineering biased Galton boards
Very interesting problem. Of course as was mentioned in a later post, all the target probabilities on each SE-NW diagonal must sum to 1. But I'm not sure if this is massively underdetermined. It's easy to check that all transition probabilities are uniquely determined through the NW-SE diagonal i+j = 3. (In fact this imposes some minor constraints on the target probabilities). And it looks as though things may continue that way. (Or do things suddenly start loosening up after this?) --Dan Jim wrote: << Here's a (hopefully clearer) statement of the question. Consider a random walk on ZxZ that starts at (0,0) and progresses n-1 steps upward and rightward, ending at some vertex (i,j) with i,j non-negative integers summing to n-1, such that p_{i,j} is the probability that a walker at (i,j) will go to (i+1,j) (and 1-p_{i,j} is the probability that a walker at (i,j) will go to (i,j+1)). Thus the path taken in the first n-1 steps is determined by all the p_{i,j}'s with i,j non-negative integers with sum no greater than n-2. Suppose we want to choose those n(n-1)/2 probabilities p_{i,j} so that the probability of the walker being at (n-k,k-1) is some specified number p_k (1 leq k leq n). This is a massively underdetermined problem; there are lots of ways to choose biases at the n(n-1)/2 junctions so as to generate this distribution after n steps. But suppose we have the additional goal of minimizing the effect that slight perturbations of the biases will have. Is there a unique best choice of biases, and if so, what is it? . . .
________________________________________________________________________________________ It goes without saying that .
I still assert that the probabilities are underdetermined, even in the case n=3. Consider a situation board in which balls get routed from (0,0) to (1,0) w.p. (with probability) 2/3, from (1,0) to (2,0) w.p. 1/2, and from (0,1) to (1,1) w.p. 0. In the Galton board picture, that's 2/3:1/3 1/2:1/2 0:1 The output distribution is 1/3:1/3:1/3. On the other hand, the biased Galton board 1/3:2/3 1:0 1/2:1/2 also gives output distribution 1/3:1/3:1/3. So the n output probabilities do NOT uniquely determine the n(n-1)/2 biases. My guess is that Dan is solving a different problem. Can anyone reconcile his analysis with mine and explain why we came to such different conclusions? Jim On 6/18/12, Dan Asimov <dasimov@earthlink.net> wrote:
Very interesting problem. Of course as was mentioned in a later post, all the target probabilities on each SE-NW diagonal must sum to 1.
But I'm not sure if this is massively underdetermined. It's easy to check that all transition probabilities are uniquely determined through the NW-SE diagonal i+j = 3. (In fact this imposes some minor constraints on the target probabilities). And it looks as though things may continue that way. (Or do things suddenly start loosening up after this?)
--Dan
Jim wrote: << Here's a (hopefully clearer) statement of the question.
Consider a random walk on ZxZ that starts at (0,0) and progresses n-1 steps upward and rightward, ending at some vertex (i,j) with i,j non-negative integers summing to n-1, such that p_{i,j} is the probability that a walker at (i,j) will go to (i+1,j) (and 1-p_{i,j} is the probability that a walker at (i,j) will go to (i,j+1)).
Thus the path taken in the first n-1 steps is determined by all the p_{i,j}'s with i,j non-negative integers with sum no greater than n-2.
Suppose we want to choose those n(n-1)/2 probabilities p_{i,j} so that the probability of the walker being at (n-k,k-1) is some specified number p_k (1 leq k leq n). This is a massively underdetermined problem; there are lots of ways to choose biases at the n(n-1)/2 junctions so as to generate this distribution after n steps. But suppose we have the additional goal of minimizing the effect that slight perturbations of the biases will have. Is there a unique best choice of biases, and if so, what is it? . . .
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Dan Asimov -
James Propp