most recent 30 from http://mathoverflow.net 2013-05-18T14:43:16Z http://mathoverflow.net/feeds/question/50572 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50572/optimally-directing-switches-for-a-random-walk aorq 2010-12-28T15:49:10Z 2011-02-08T22:20:49Z

<p><strong>If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?</strong></p> <h2>Formal statement</h2> <p>More specifically, suppose you are given a directed graph $G$ with edge weights, two designated vertices $s$ and $t$, and a subset of the vertices $S$. The edges weights represent the transition probabilities of the random walk, the vertex $s$ the start, the vertex $t$ the target, and the set $S$ the set of switches. You are guaranteed that the weights on the out-edges of any node are non-negative and sum to one, that $t$ is absorbing (i.e., $t$ has one out-edge directed towards itself), and that the out-degree of any vertex in $S$ is exactly two.</p> <p>A random walk is taken on $G$, starting at $s$. For any given vertex not in $S$, the weight on an out-edge is the probability that the walk will travel in that direction. Every time that the walk reaches a switch (a vertex in $S$), you are allowed to choose which of the two edges the walk will travel along (and you are allowed probabilistic strategies). How should you direct the path if you want to maximize the probability that the walk ends up at your target $t$?</p> <h2>Questions</h2> <p>I am most interested in this as an algorithmic question. How fast can you find the optimal strategy with respect to the size of the graph? My specific application has about 100 switches among 200 vertices in a fairly sparse graph (say out-degree bounded above by 6).</p> <p>But we can also ask purely mathematical questions. For example, my intuition says (and I can hand-wave a proof) that there exists an optimal strategy that is deterministic in the sense that it always chooses the same direction for a given switch and this direction does not depend on the initial vertex $s$. Is this actually true?</p> <p>Also, is there a sense in which the optimal strategy needs to "coordinate" among the switches? That is, is there a local optimum that is not a global optimum?</p> <h2>Notes</h2> <p><em>A note on connectivity</em>: we may assume that the graph is sufficiently connected. If not, we can identify all vertices that cannot be reached from the start node, as well as all of those that cannot reach the target node, into a single, absorbing fail state. We may assume the start node is not the fail node.</p>

http://mathoverflow.net/questions/50572/optimally-directing-switches-for-a-random-walk/50588#50588 optima 2010-12-28T19:12:05Z 2010-12-28T19:59:30Z

<p>Edit: apparently I'm linking to a paper that has a different definition of 'switch'</p> <p>The reachability problem is NP-complete for unweighted directed switch graphs.</p> <p><a href="http://www.springerlink.com/content/f2722481747l2170/" rel="nofollow">http://www.springerlink.com/content/f2722481747l2170/</a></p> <p>This means that in the weighted case it is NP hard to even find switch settings that can reach the target from the starting vertex, let alone reach the target with maximum probability.</p>

http://mathoverflow.net/questions/50572/optimally-directing-switches-for-a-random-walk/54821#54821 Peter Shor 2011-02-08T22:15:10Z 2011-02-08T22:20:49Z

<p>This is the simple stochastic games problem, but for only one player, and there is a polynomial-time algorithm for it based on linear programming, which is described in Anne Condon's paper "On Algorithms for Simple Stochastic Games." Look in this paper for the linear programming algorithm for SSG's with no min vertices. In one of her papers on simple stochastic games, Condon does indeed prove that the setting of the switches is independent of the start node, and that in the optimal strategy, the switch settings never need to change.</p>