[math-fun] reverse-engineering biased Galton boards
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? Here we're dealing with a map from R^{n(n-1)/2} to R^n, so it's not clear to me what the right way to measure sensitivity to perturbations is. But I suspect that this problem has a nice canonical answer if one chooses some natural way to measure sensitivity. What I actually want is not necessarily the most noise-insensitive way of biasing the junctions, but a reasonably noise-insensitive way of biasing the junctions that is also easy to compute and mathematically natural. (Yes, "natural" is even more vague than "noise-insensitive".) When I posted the problem I thought that minimizing noise-sensitivity would lead to a nice way of biasing the junctions, but now I'm not so sure, since I've done some more analysis of my original idea about how to measure noise-sensitivity, and it leads to nasty algebraic expressions (e.g., polynomial equations that can't be solved in terms of radicals). Jim Propp
I was thinking about this problem a lot last week, and I only got as far as what you've just mentioned, i.e. you need a precise definition of how to measure "the effect [of] slight perturbations". I wouldn't hold my breath trying to find closed form solutions, or for that matter, any solution with fewer than n(n-1)/2 terms. The simplest solution might even be a matrix with n columns and n(n-1)/2 rows and some mess of O(n^n) symbols in each element, but that may be a bit pessimistic (-: On 6/18/12, James Propp <jamespropp@gmail.com> wrote:
Here's a (hopefully clearer) statement of the question. [...] 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? [...] What I actually want is not necessarily the most noise-insensitive way of biasing the junctions, but a reasonably noise-insensitive way of biasing the junctions that is also easy to compute and mathematically natural. (Yes, "natural" is even more vague than "noise-insensitive".) [...]
-- 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
you need a precise definition of how to measure "the effect [of] slight perturbations".
a natural definition would be to measure the maximum value of | p_k - P |, where p_k is the probability of passing through (n-k,k-1) and P are all the probabilities of passing through that same point where the individual steps have probability p_{i,j} + - epsilon instead of p_{i,j}. but this seems very hard, and is not likely to give nice results. a slightly different approach: since there are n degrees of freedom here, and the random walk takes n steps, is it possible to make all the p_{i,j} equal if i+j has constant sum (in other words, each step's transition probabilities are independent of the path so far) ? erich
Erich's second idea (if I understand it) won't work for the case of the probability vector (1/2,0,1/2). For this vector, we really have no choice about what biases to use: we must use bias 1/2:1/2 at the top of the quincunx, bias 1:0 in the second row at the left, and bias 0:1 in the second row at the right. (Here I'm reverting to the standard orientation of the quincunx; just take the first-quadrant picture from my last email and rotate it 45 degrees counterclockwise.) Note that the biases 1:0 and 0:1 are different. A variant that Erich's posting suggested to me is the idea of having p_{i,j} depend only on i-j; I'll have to think about it. In the meantime, though, I want to point out that the degrees-of-freedom count is off. As (i,j) varies over all locations where a routing-junction exists, i-j takes on all values between 0-(n-2) and (n-2)-0; so there are 2(n-2)+1 = 2n-3 variables to play with, but there are only n constraints (or maybe just n-1, since p_1,p_2,...,p_n must sum to 1). This discrepancy doesn't appear in the case n=2 (where there's just one routing-junction), but it appears in the case n=3. Jim Propp On Mon, Jun 18, 2012 at 12:54 PM, Erich Friedman <efriedma@stetson.edu>wrote:
you need a precise definition of how to measure "the effect [of] slight perturbations".
a natural definition would be to measure the maximum value of | p_k - P |, where p_k is the probability of passing through (n-k,k-1) and P are all the probabilities of passing through that same point where the individual steps have probability p_{i,j} + - epsilon instead of p_{i,j}. but this seems very hard, and is not likely to give nice results.
a slightly different approach: since there are n degrees of freedom here, and the random walk takes n steps, is it possible to make all the p_{i,j} equal if i+j has constant sum (in other words, each step's transition probabilities are independent of the path so far) ?
erich _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Erich Friedman -
James Propp -
Robert Munafo