6
$\begingroup$

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.

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

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Dec 28, 2010 at 19:44
  • 1
    $\begingroup$ Yes, switch means something different there. $\endgroup$
    – Chris Eagle
    Commented Dec 28, 2010 at 19:51
  • $\begingroup$ @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". $\endgroup$
    – aorq
    Commented Dec 28, 2010 at 20:05
  • $\begingroup$ 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. $\endgroup$
    – Orange
    Commented Jan 14, 2011 at 22:09
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Oct 4, 2022 at 13:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .