Timeline for Optimally directing switches for a random walk
Current License: CC BY-SA 2.5
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 8, 2011 at 22:15 | answer | added | Peter Shor | timeline score: 2 | |
| Dec 29, 2010 at 0:28 | comment | added | Omer | @fedja: I made no claim about the rate of convergence, which of course can be very bad. by setting 0/1 initial conditions for n=0, we get lower and upper bounds, so it is easy to know how close we are to the optimal solution after a given number of steps. Also, we can skip times we outside $S$, and reduce the graph to a Markov chain on $S$, where at each place we choose from two (or several) distributions. | |
| Dec 28, 2010 at 20:46 | comment | added | aorq | @optima: And I think that locality cannot occur. Suppose two different assignments connect $s$ and $t$, through paths $p$ and $q$ respectively. Look at the last place in $p$ where it goes through a switch that is in the opposite position for the $q$ path. You can safely switch the $q$ path there, because no later switches in $p$'s tail disagree. Repeat until the $q$ path is identical with the $p$ path and then switch any irrelevant switches. | |
| Dec 28, 2010 at 20:13 | comment | added | aorq | @optima: That is a very reasonable notion of locality. I'm sorry I didn't think of it. | |
| Dec 28, 2010 at 20:07 | comment | added | optima | @Rex: I guess I meant looking for two switch configurations which both connect $s$ to $t$, and where you can't get from one configuration to the other configuration by flipping single switches at a time unless $t$ becomes unreachable from $s$ at some point. These two configurations would be in different 'islands' of the solution space, and this is the kind of locality I was talking about. | |
| Dec 28, 2010 at 19:58 | comment | added | aorq | @fedja: I know that in those coordinates it isn't linear. But it is linear in other coordinates, which shows the maximum is at a corner, which you then use the Markov property on to show that the optimum is actually at a time-invariant strategy. But then if you switch coordinates to the ones you're analyzing, the function isn't linear anymore, which happens because the change of coordinates map isn't linear itself. Regarding maximization: yes, that's the hope. The motivation I'm working with is that I can't figure out how to encode any sort of coordination/computation in this problem. | |
| Dec 28, 2010 at 19:53 | comment | added | aorq | @optima: In the original question, I am maximizing a probability, which is between 0 and 1, that is, in the closed interval $[0, 1]$. If we just care whether or not there is a path, that appears to be maximizing a function that takes only the values 0 (if there is no path) and 1 (if there is a path) themselves, that is, the endpoints of the interval. But perhaps you mean something different. | |
| Dec 28, 2010 at 19:32 | comment | added | fedja | ----"I believe that the target probability is in fact linear on the right space of coordinates"----. Actually, if you consider only time-independent strategies, then it is a ratio if two polylinear forms in switch parameters. But, even if you forget "the ratio", finding the global maximum of a general polylinear form in the cube is not easy at all. Optima's link suggests the same. There is a faint hope that your form is somehow special though. | |
| Dec 28, 2010 at 19:12 | answer | added | optima | timeline score: 0 | |
| Dec 28, 2010 at 19:04 | comment | added | optima | @Rex: "I don't know what it means for a 0/1-valued function to have a local but not global optimum." Then what did you mean by "That is, is there a local optimum that is not a global optimum?" in the original question? | |
| Dec 28, 2010 at 19:01 | comment | added | aorq | @optima: I don't know what it means for a 0/1-valued function to have a local but not global optimum. | |
| Dec 28, 2010 at 18:56 | comment | added | optima | To solve a simpler problem, what if you forget the weights and consider only the question of setting switch states so that there is a directed path from $s$ to $t$. Does the solution need to coordinate switches in this simpler case? This might help with the question about local vs global optimality in the weighted case. | |
| Dec 28, 2010 at 18:24 | comment | added | aorq | @Omer: Yes of course. Thanks for the correct choice of words ("time homogeneous"). | |
| Dec 28, 2010 at 18:23 | comment | added | aorq | @fedja: I believe that the target probability is in fact linear on the right space of coordinates, one for each pure strategy. By "pure strategy" I mean a complete description of whether to switch one way or the other in every possible state, with a separate state for every possible way of getting to a place. (For example, suppose you have a switch with options X and Y. Then a pure strategy would tell you what to do in all of the possible ways of getting there: X, Y, XX, XY, YX, ...) You are correct of course that the convergence could be exponentially poor in the size of the graph. | |
| Dec 28, 2010 at 18:19 | comment | added | Omer | determinism (or more precisely, a time homogeneous strategy) follows from the Markov property for the process. | |
| Dec 28, 2010 at 18:09 | comment | added | fedja | @ Omer: First, you change the equations, not the solutions in the linear way when you manipulate probabilities. Second, the convergence can be terribly slow. Indeed, let's combine all the vertices from which you cannot reach the target into one absorbing vertex $f$ (if there are no vertices like that, you end up at $t$ with probability $1$ no matter what). Assume that there is one switch that either sends you to a fork between $t$ and $m$ (1/2 for any decent number of steps), or sends you to a long path to $t$ with a lot of backtracking edges, so the expected time to reach $t$ is $5^{100}$. | |
| Dec 28, 2010 at 17:58 | comment | added | aorq | @Omer: The graph is finite, as I am interested in an algorithm. I guess you're right that you can compute optimal strategies for the time-bounded case in $O(n \abs{G})$. How fast does it converge? (Is it completely obvious that it does converge to the optimal strategy? Hmm.) | |
| Dec 28, 2010 at 17:55 | comment | added | aorq | @Omer: That proves that there is a pure strategy (as indicated in one of my comments above). Unfortunately, I seem to have co-opted "deterministic", which often means the same thing as "pure", into a stronger notion. A pure strategy in this context always makes a decision to either 100% go one way or 100% go the other way. My notion of "deterministic" adds the condition that it makes the same decision every time it approaches a switch (a pure strategy need not do that) and that this doesn't depend on the starting node. | |
| Dec 28, 2010 at 17:49 | comment | added | Omer | Is the graph infinite? If so, we can truncate it by replacing the outside of a large ball by a sink. If the number of steps is bounded by $n$, then we can recursively compute the probability of success and optimal strategy in $O(n|G|)$. These should converge to an optimal strategy for unbounded time. | |
| Dec 28, 2010 at 17:48 | history | edited | aorq | CC BY-SA 2.5 |
Added a note and some headings
|
| Dec 28, 2010 at 17:44 | comment | added | Omer | By convexity there is indeed a deterministic optimal strategy: The probability of success is a linear function on the space of strategies, so takes its extremal values at extremal points. | |
| Dec 28, 2010 at 17:13 | comment | added | aorq | @optima: Yes, that seems like a plausible heuristic. Strategies like that motivate my question regarding local versus global optima. I am really interested only in a global optimum. But if they're one and the same, then everything's great. (Unfortunately, my experience tells me that one should rarely assume local optima are global optima also.) | |
| Dec 28, 2010 at 17:07 | comment | added | optima | One hack could be to initialize both out edges from each switch with a nonzero weight, say 0.5. Then for each switch sink compute the probability of ending up at the target. For each switch, upvote the outgoing edge which has the higher probability of ending up at the target (and similarly downvote the other edge). Iterate. Maybe this will converge to switch edge weights near 0.0 and 1.0; if so then discretizing to 0 and 1 will give decisions which are in some sense locally optimal. | |
| Dec 28, 2010 at 16:33 | comment | added | aorq | Here's my proof sketch of "determinism". Look at a strategy as a probability distribution on choices, where repeated choices are treated separately. Then, by the usual argument, there is an optimal strategy that is pure (any mixed strategy is a convex combination of pure strategies). Now suppose the walk reaches vertex $v$ at time $a$ and time $b$ and you made different decisions. Why would you do that -- if the decision at $b$ was optimal, then you should make the same decision at $a$. Finally, it shouldn't matter where you start because all that matters is where you are now. | |
| Dec 28, 2010 at 16:26 | comment | added | aorq | Yes, you may make a separate choice each time a switch is reached. My intuition says you won't, but I'll be happily surprised if you prove me wrong. | |
| Dec 28, 2010 at 16:10 | comment | added | aorq | No, the walk is infinite. However, note that once the walk reaches an absorbing vertex (such as the target $t$), it stays there. | |
| Dec 28, 2010 at 16:08 | comment | added | fedja | Also, can I make two different choices if the switch is reached twice? | |
| Dec 28, 2010 at 16:03 | comment | added | fedja | Is the number of steps fixed? | |
| Dec 28, 2010 at 15:49 | history | asked | aorq | CC BY-SA 2.5 |