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