1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random walk in a graph

  1. Jan 1, 2012 #1
    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. jcsd
  3. Jan 1, 2012 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Hello scriby. Welcome to PF !

    How many choices are there at each node ?
     
    Last edited by a moderator: May 5, 2017
  4. Jan 1, 2012 #3
    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 ??
     
  5. Jan 1, 2012 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Starting at g, isn't P(c) = 1 ?
     
  6. Jan 1, 2012 #5
    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
     
  7. Jan 1, 2012 #6
    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
  8. Jan 1, 2012 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
  9. Jan 1, 2012 #8

    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)

    thx for your replies
     
  10. Jan 1, 2012 #9
    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
     
  11. Jan 1, 2012 #10
    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?
     
  12. Jan 2, 2012 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  13. Jan 2, 2012 #12
    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 ?
     
  14. Jan 2, 2012 #13

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  15. Jan 2, 2012 #14
    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.
     
  16. Jan 2, 2012 #15
    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.
     
  17. Jan 2, 2012 #16

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  18. Jan 2, 2012 #17
    Of course there's no need to do this, except for the insights and understanding. That's the whole point.
     
  19. Jan 3, 2012 #18
    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)
     
  20. Jan 3, 2012 #19
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Random walk in a graph
  1. Random walk (Replies: 7)

  2. Random walk? (Replies: 5)

  3. Random walk on circle (Replies: 1)

  4. Random walk? (Replies: 8)

Loading...