4
$\begingroup$

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

Simple tree graph

Please help me answering the questions, I have no idea where to start.

The random walk on the graph is assumed to be uniform.

  • 0
    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.2012-01-02
  • 0
    @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](http://en.wikipedia.org/wiki/Random_walk#Random_walk_on_graphs). May be it's just my background talking! :)2012-01-02
  • 0
    each step leads to a neighboring node with the same probability (regardless of previous steps) - there is no additional information given - thanks2012-01-02
  • 0
    Can the downvoters please explain? Unexplained downvotes do not help the OP improve either this post or the future ones.2012-01-02
  • 0
    @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.2012-01-02
  • 0
    @cardinal, Thanks for your edits and your explanation. [As I mentioned before, I really think it isn't terribly non-standard to talk about a uniform random graph on a graph, hiding the details of the transition matrix since that is implicit in the graph itself. That said, from the OP's reply, it seems more likely that they are not very familiar with the underlying probability concepts mentioned. Oh, well.]2012-01-02

2 Answers 2

2

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

  • 1
    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.2012-01-02
  • 0
    Thank you all for your replies, but I'm still having difficulties understanding "u(x) is the average of u(y) over the neighbours y of x"....let's say we take u(a)...then we have u(b)+u(c)+u(d) / 3 ...but how do I find out what u(b),u(c) and u(d) are??? thanks2012-01-03
  • 0
    Another note: you say "Thus u(d)=1", what if d might never be reached??2012-01-03
1

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