# Random walk in a graph

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

## Homework Statement

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

## 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:

Related Calculus and Beyond Homework Help News on Phys.org
SammyS
Staff Emeritus
Homework Helper
Gold Member
http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

## Homework Statement

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

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

How many choices are there at each node ?

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
Staff Emeritus
Homework Helper
Gold Member
Starting at g, isn't P(c) = 1 ?

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

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:
Ray Vickson
Homework Helper
Dearly Missed
http://img844.imageshack.us/img844/8333/1111jx.png [Broken]

## Homework Statement

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

## 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:
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)

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

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
Homework Helper
Dearly Missed
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

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
Homework Helper
Dearly Missed
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

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.

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
Homework Helper
Dearly Missed
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

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.

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)

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.