Random walk in a graph

1. Jan 1, 2012

scriby

http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

1. The problem statement, all variables and given/known data

With wich probability, starting in g, node d gets hit before node e?

2. Relevant equations

3. The attempt at a solution

I think the probability of hitting each node starting in g is the following:

p(g) = 1
p(c) = 1/2
p(a) = 1/3
p(d) = 1
p(b) = 1/3
p(f) = 1
p(e) = 0

Do I just have to add the probabilities from g to d and that's it?

Last edited by a moderator: May 5, 2017
2. Jan 1, 2012

SammyS

Staff Emeritus
Hello scriby. Welcome to PF !

How many choices are there at each node ?

Last edited by a moderator: May 5, 2017
3. Jan 1, 2012

scriby

g has 1 choice
c has 2 choices
a has 3 choices
d has 1 choice
b has 3 choices
f has 1 choice
e also has 1 choice , but I think since it should not be relevant for the solution we can put it =0 ??

4. Jan 1, 2012

SammyS

Staff Emeritus
Starting at g, isn't P(c) = 1 ?

5. Jan 1, 2012

scriby

yes of course...I got a little confused since c has two choices, but yes starting at g there's only one choice and that is c

6. Jan 1, 2012

Joffan

On a random walk that terminates on reaching either d or e:

- from g, what is the probability of reaching a?
- from c, what is the probability of reaching a?
- from f, what is the probability of reaching b?

Last edited: Jan 1, 2012
7. Jan 1, 2012

Ray Vickson

Are the arcs directed or undirected? For example, from 'a' can we go just to 'b' and 'd', or can we also go back to 'c'? That will make a big difference to the probabilities.

RGV

Last edited by a moderator: May 5, 2017
8. Jan 1, 2012

scriby

I guess 1 in all cases.

I guess undirected (this is not specifically mentioned in the task but the image clearly shows an undirected graph since the arrows are missing)

9. Jan 1, 2012

scriby

is this right?

probability of hitting d (starting in g): 1+1+1/3
probability of hitting e (starting in g): 1+1+1/3+1/2

10. Jan 1, 2012

Joffan

You need to keep your probabilities on a tighter rein... the total allocation of possible events should still only be 1

Once we reach a, what is the chance of reaching d before b?

11. Jan 2, 2012

Ray Vickson

Modify the system by making both states d and e absorbing. Then, the probability of reaching d before e in the original system is the same as the probability of reaching d (at all) in the new system. Now apply standard equations for first-passage probabilities. In this way, if p(x) denotes the probability of reaching d (before e) starting from x, we have p(a) = 2/3, p(b) = 1/3, p(c) = 2/3, p(f) = 1/3 and p(g) = 2/3.

RGV

12. Jan 2, 2012

scriby

1/3 ????

I can't follow your idea here. Making the states d and e absorbing means it is impossible to return once reaching those states right? This would mean their probabailities are always = 1 ???
Why is p(a)=2/3 , shouldn't it be only 1/3 ?
and why is p(c) = 2/3 , we only got 2 options to move away from c ?

13. Jan 2, 2012

Ray Vickson

Yes, exactly: making them absorbing means you cannot return once reaching them. That is exactly why the probability of reaching d before e in the original system is the same as reaching d in the new system. Of course the probabilities of reaching d are not 1; d might never be reached. This is just like a game with two outcomes "win" or "lose", which ends when either of these outcomes is reached. However, you do not win with probability 1!

RGV

14. Jan 2, 2012

Joffan

No. From a, there is clearly a 1/3 chance to go to b, c or d on the next step, but if we go to c the walk has not finished. This 1/3 branch will eventually (inevitably) return to a, generating more probabilty for going to either b or d.

15. Jan 2, 2012

Joffan

I set up a little illustration in Excel that propagates probability through the network (but d and e are set as "sticky" - they retain all probability and send none to other nodes). Initial values (row 3) are g=1 and all others are zero.

(A4) =C3/2+B3/3
(B4) =A3/3+F3
(C4) =G3+A3/3
(D4) =A3/3+D3
(E4) =B3/3+E3
(F4) =B3/3
(G4) =C3/2

- then propagate these formulas down to extra rows.

It doesn't give the reasoning, but it illustrates the ideas and solution quite nicely.

16. Jan 2, 2012

Ray Vickson

There is no need to do this, although doing this might lead to some extra insights and help the OP better understand the problem. Instead, you can just write down the coupled linear equations for p(a), p(b), etc., and solve them. This is easy enough to do by hand, but if you insist on using EXCEL you can use the Solver tool to get the solution of the equations.

RGV

17. Jan 2, 2012

Joffan

Of course there's no need to do this, except for the insights and understanding. That's the whole point.

18. Jan 3, 2012

scriby

Could you please tell me how to do that? Because I think that's the point I don't really understand (how to add the probabilities)

19. Jan 3, 2012

Joffan

I think, scriby, that you need to understand how to apportion the probabilities - adding is simple.

Starting with the initial known state which is prob=1, subsequent steps will typically subdivide that probability across different nodes. If you have reached node a with probability of (say) 0.6 at a certain point in the walk, then the allocation of probability from that node is 1/3 of 0.6 to each of the branch nodes - 0.2 each to b, c and d - for the next step.

There are simplifications that can be made in this case, because there is no need to consider the system in a strict step-by-step fashion to answer the question. But the basic understanding of how the probability divides out amongst the nodes is important too.