1
$\begingroup$

I've been doing some old competitive programming tasks and found one, for which I cannot find a general solution or a solving principle.

The math part of the question is:
You have N vertices, labeled $1$ to $N$. For each vertex $v$, you are given a neighbour $u$ and a probability $p_{vu}$, that you will visit $u$ from $v$. You finish this random walk when you reach $N$. Backwards loops are possible ($p_{vv}$ can be greater than $0$). Also, a probability of a $vu$ path can be $0$.

What is the expected time $T$ of this random walk, if one passage from $v$ to $u$ symbolises $1$ time unit? If reaching N is impossible, you stop and say it is impossible.

I am thinking of a backwards approach but don't know, how to find a general system of equations that solve this, that aren't case specific.

$\endgroup$
2
  • $\begingroup$ Is this for the complete graph (ie every vertex $u$ is connected to every other vertex $v$), or a line, or what? :) -- sorry, I see you have mentioned "a probability of a path $vu$ can be 0", so you're looking at a general chain. Apologies $\endgroup$
    – Sam OT
    Commented Nov 13, 2017 at 22:02
  • $\begingroup$ We can say that is it for a complete graph, but those edges that have $p_{vu}=0$ can be ignored as we will never traverse them. Also, I have already determined if the vertex is actually reachable from $1$. $\endgroup$
    – Ravonrip
    Commented Nov 13, 2017 at 22:06

1 Answer 1

Reset to default
1
$\begingroup$

You want to look at hitting times of Markov chains. You can check out Markov Chains by James Norris for an excellent account here. On that link, only the first chapter is available, but that's all you need. In particular, look at Section 1.3. (Note that these links are from James Norris' homepage, so are the genuine link. You may well be able to find the whole pdf elsewhere, or look in a library for the book.)

Other books on Markov chains will also be helpful, eg by Geoffrey Grimmett.

The method linked above gives a set of equations to solve, which may or may not be helpful since you're looking at it from a programming point of view. In general I expect this is pretty difficult to implement, however. If you have structure on the graph, then you can do some analytic stuff to reduce the equations, but for general Markov chains... going to be slow to solve computationally for large $N$ (at least methods that I know)

$\endgroup$
2
  • $\begingroup$ Thank you. It helped me a great deal. But I have just one more question. How can I deduce, from the equations, that I have a positive probability of never getting to the end? Lets say $N=5$, meaning I have 5 vertices. $p_{12}=1/2$ and $p_{15}=1/2$. Vertex 2 is connected only to vertices {3,4} and those vertices are inner connected, so I have a "closed" system of {2,3,4} vertices, from which I cannot get out to 5. Is there a way to see this from the equations? $\endgroup$
    – Ravonrip
    Commented Nov 14, 2017 at 1:44
  • $\begingroup$ Personally, I'd just show analytically that there is no (directed) path, say from $2$ to $5$, and hence the probability, upon starting from $2$, of reaching $5$ is $0$. From the set of equations, observe that the hitting probabilities are the minimal non-negative solution. If you can solve it by putting $h_5 = 0$, then this is the solution (for vertex $5$), by minimality. Does that answer your question? :) $\endgroup$
    – Sam OT
    Commented Nov 14, 2017 at 13:57

You must log in to answer this question.

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