# Random walk probability/expected value

With what probability, starting at node $g$, does node $d$ get hit before node $e$ in the graph below?

What is the expected value of number of steps you need to hit $\{d,e\}$ (at least one of them) starting from node $g$? The random walk on the graph is assumed to be uniform.

• What are the probabilities on your graph? Is it always uniformly distributed? Can you go back and forth between nodes? You really need more information here. Jan 2, 2012 at 20:32
• @Patrick I agree that the OP could have given the information you seek, but I think -- in the lack of such information -- it is fairly standard to assume the "usual" random walk on undirected graphs. May be it's just my background talking! :) Jan 2, 2012 at 20:37
• each step leads to a neighboring node with the same probability (regardless of previous steps) - there is no additional information given - thanks Jan 2, 2012 at 20:40
• Can the downvoters please explain? Unexplained downvotes do not help the OP improve either this post or the future ones. Jan 2, 2012 at 20:48
• @Sri: Only a guess (as I did not downvote), but the downvotes came before the edits were made. I suspect part of it was reference to nodes in a graph without an adjacency matrix or some other representation supplied (besides the link to the picture) and no mention of the distribution of the walk on the graph. Of course, new posters can't post images, so I tried to help out by adding it and doing a little further cleanup. Jan 2, 2012 at 20:54

Let $u(x)$ be the probability, starting at node $x$, that you hit $d$ before $e$. Thus $u(d) = 1$ and $u(e) = 0$. For other nodes $x$, $u(x)$ is the average of $u(y)$ over the neighbours $y$ of $x$. Solve the system of equations...
• Note that $u$ is the same for the line e--b--a--d. Starting from g on the tree is equivalent to starting from a on the line hence the probability to hit d before e starting from g is 2/3.
Similar to Robert Israel's answer: Let $t(x)$ be the expected number of steps to hit $\{d, e\}$. Thus $t(d)=0$ and $t(e)=0$. For other nodes $x$, $t(x)=1+$ "the average of $t(y)$ over the neighbours $y$ of $x$". Solve the system of equations...