wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Random Walks <--> Resistors Networks
        
(Message started by: william wu on Nov 6^th, 2002, 12:09am)

Title: Random Walks <--> Resistors Networks
Post by william wu on Nov 6^th, 2002, 12:09am

Learned this in my randomized algorithms class today, and it was pretty interesting so I thought I'd share it. There is apparently a dual between computing resistance in a resistor network, and computing expected hitting time of a random walk in a graph! The problems at first seem completely unrelated and yet they are duals -- that is, if you solve one you've also solved the other.

Taken from CMU's 15-750 Graduate Algorithms:
http://www.ocf.berkeley.edu/~wwu/documents/cmu_rwrn.txt

A paper by Doyle and Snell:
http://www-ee.technion.ac.il/~adam/FUN/RWEN.pdf