Random walk in a graph

  • Thread starter scriby
  • Start date
  • #1
7
0
http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

Homework Statement



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


Homework Equations





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:

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,326
1,009
http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

Homework Statement



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


Homework Equations





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?
Hello scriby. Welcome to PF !

How many choices are there at each node ?
 
Last edited by a moderator:
  • #3
7
0
Hello scriby. Welcome to PF !

How many choices are there at each node ?
Hi SammyS , thanks for your reply


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
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,326
1,009
Starting at g, isn't P(c) = 1 ?
 
  • #5
7
0
Starting at g, isn't P(c) = 1 ?
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
473
13
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:
  • #7
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

Homework Statement



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


Homework Equations





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?
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:
  • #8
7
0
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?

I guess 1 in all cases.


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
I guess undirected (this is not specifically mentioned in the task but the image clearly shows an undirected graph since the arrows are missing)

thx for your replies
 
  • #9
7
0
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
473
13
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
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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?
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
7
0
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?
1/3 ????

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
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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 ?
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
473
13
Once we reach a, what is the chance of reaching d before b?
1/3 ????
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
473
13
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
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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.
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
473
13
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
Of course there's no need to do this, except for the insights and understanding. That's the whole point.
 
  • #18
7
0
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
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
473
13
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.
 

Related Threads on Random walk in a graph

  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
466
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
326
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Top