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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Patrick Da Silva
    Commented Jan 2, 2012 at 20:32
  • $\begingroup$ @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! :) $\endgroup$
    – Srivatsan
    Commented Jan 2, 2012 at 20:37
  • $\begingroup$ each step leads to a neighboring node with the same probability (regardless of previous steps) - there is no additional information given - thanks $\endgroup$
    – danielstefuj
    Commented Jan 2, 2012 at 20:40
  • $\begingroup$ Can the downvoters please explain? Unexplained downvotes do not help the OP improve either this post or the future ones. $\endgroup$
    – Srivatsan
    Commented Jan 2, 2012 at 20:48
  • $\begingroup$ @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. $\endgroup$
    – cardinal
    Commented Jan 2, 2012 at 20:54

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Did
    Commented Jan 2, 2012 at 21:06
  • $\begingroup$ 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??? thanks $\endgroup$
    – danielstefuj
    Commented Jan 3, 2012 at 10:32
  • $\begingroup$ Another note: you say "Thus u(d)=1", what if d might never be reached?? $\endgroup$
    – danielstefuj
    Commented Jan 3, 2012 at 14:41
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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