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

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