Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Formal statement

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.

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$?

Questions

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).

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?

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?

Notes

A note on connectivity: 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.

share|improve this question
    
Is the number of steps fixed? –  fedja Dec 28 '10 at 16:03
    
Also, can I make two different choices if the switch is reached twice? –  fedja Dec 28 '10 at 16:08
    
No, the walk is infinite. However, note that once the walk reaches an absorbing vertex (such as the target $t$), it stays there. –  aorq Dec 28 '10 at 16:10
    
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. –  aorq Dec 28 '10 at 16:26
    
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. –  aorq Dec 28 '10 at 16:33

2 Answers 2

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.

share|improve this answer

Edit: apparently I'm linking to a paper that has a different definition of 'switch'

The reachability problem is NP-complete for unweighted directed switch graphs.

http://www.springerlink.com/content/f2722481747l2170/

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.

share|improve this answer
2  
Sounds fishy. Go back from $t$ and see from where you can reach it, expanding the set $S$. If you see a switch that can reach into the current version of $S$, just point it there and add it to $S$. Perhaps, the notions of a switch are different or they talk about full connectivity rather than reaching a given vertex. –  fedja Dec 28 '10 at 19:44
1  
Yes, switch means something different there. –  Chris Eagle Dec 28 '10 at 19:51
    
@Re your edit: it's understandable that this paper might be related. I feel that I have one reasonable notion of what a switch means in a directed graph, and they have another one. Theirs is another reasonable notion, primarily motivated by the fact that trains cannot make very sharp turns, and so physical train switches can only be used "in one direction". –  aorq Dec 28 '10 at 20:05
    
I'm sorry, have we convinced ourselves this is NP hard? I remember thinking about this problem around Christmas and that was my belief then though I have no expertise here. –  Orange Jan 14 '11 at 22:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.