Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Patrick Da Silva Jan 2 '12 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! :) –  Srivatsan Jan 2 '12 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 –  danielstefuj Jan 2 '12 at 20:40
    
Can the downvoters please explain? Unexplained downvotes do not help the OP improve either this post or the future ones. –  Srivatsan Jan 2 '12 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. –  cardinal Jan 2 '12 at 20:54

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

share|improve this answer
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. –  Did Jan 2 '12 at 21:06
    
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 –  danielstefuj Jan 3 '12 at 10:32
    
Another note: you say "Thus u(d)=1", what if d might never be reached?? –  danielstefuj Jan 3 '12 at 14:41

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.