What is the Probability of Reaching Node D Before Node E Starting from Node G?

[scriby]

http://img844.imageshack.us/img844/8333/1111jx.png

Homework Statement

With which 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?

 

[SammyS]

http://img844.imageshack.us/img844/8333/1111jx.png

Homework Statement

With which 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 ?

 

[scriby]

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

 

[SammyS]

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

 

[scriby]

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

 

[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?

 

[Ray Vickson]

http://img844.imageshack.us/img844/8333/1111jx.png

Homework Statement

With which 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

 

[scriby]

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

 

[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

 

[Joffan]

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?

 

[Ray Vickson]

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

 

[scriby]

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 ?

 

[Ray Vickson]

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

 

[Joffan]

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.

 

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

 

[Ray Vickson]

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

 

[Joffan]

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.

 

[scriby]

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)

 

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