Electric Networks and Random Walk Interconnection
Explore the intriguing relationship between random walks on graphs and electric networks. Discover how concepts from electric networks can enhance the mathematical theory of random walks, leading to surprising connections between these seemingly unrelated fields.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 21 Random Walk and Electric Networks 1
What do we know about Random walk till now? We have discussed uniform random walk on A line. A complete graph. Two complete graphs joined by an edge (Mid-sem Exam). We analyzed the random walk by writing equation for each case. We could solve these equations because of Symmetry of the our graphs (line graph, complete graph). Uniformity of random walk. Question: Is there a compact formula for expected duration of a random walk on any graph ? What if the random walk is not uniform ? 3
An answer from mathematics Let ? = (?,?) be an undirected graph on ? vertices and ? edges. Theorem: Let ?,? ?. Expected length of a random walk that starts from ? and terminates on reaching ? is ?(??). The above result is derived using theory of Markov Chains. Unfortunately, it is a loose result for many graphs . Exercise: Show that for complete graph, the above result is very loose. 4
A surprising discovery Random walk on a graph is closely related to electric networks. A graph can be viewed as a electric network where each edge corresponds to a resistance of one ohm. Various aspects of random walk are defined as a fundamental characteristics (resistance, power, voltage) of the corresponding electric network. Physics of electric network helps in mathematical theory of random walk ! Isn t it surprising ? 5
Random walk on a line home bar ? ? ? ? ? + ? ? ? ? ? Question: Suppose the random walk starts at ?. What is the probability that the drunkard reaches home before reaching bar ? Let ?(?)be the corresponding probability. ? ? = ? ? ? = ? ? ? = ? ? ? ? ?? ? ? + ? ?? ? + ? 7
Random walk on a line current ? ? ? ? ? + ? ? ? ? ? ?Volt Each resistance is 1 ohm. ? ? : Potential at point ?. ? ? = ?,? ? = ?, Current entering? = Current leaving?. ? ?+? ? ? ? ? ? ? ? = ? ? ? ? =? ?? ? ? + ? ? + ? 9
Random walk on a line home bar ? ? ? ? ? + ? ? ? ? ? ? ? =? ? ? = ?,? ? = ?, ?? ? ? + ? ? + ? current ? ? ? ? ? + ? ? ? ? ? ?Volt ? ? : Potential at point ? ? ? = ?,? ? = ?, ? ? =? ?? ? ? + ? ? + ? Hence ? ? and ? ? satisfy the same set of equations. Since these equations have unique solution, therefore? ? = ? ? for all ?.
Generalization to graphs ? ? home ? bar ? ? ? ? ? ? ? Question: What is ??, probability of reaching home before bar ? ??= ?, ??= ?, ? deg(?) ? ?(?)?? ??= 11
Generalization to graphs ? ? ? ? ? ? ? ? ? ? Question: What is relation between ?? and ?? s where ? ?(?) ? ??= ?, ??= ?, Net current leaving ? is 0. ? ?(?)(?? ??) =0 ? ??= deg(?) ? ?(?)?? 12
Generalization to graphs ? ? ? ? ? ? ? ? ? ? Question: What is relation between ?? and ?? s where ? ?(?) ? ??= ?, ??= ?, ? deg(?) ? ?(?) ??= ?, ??= ?, ? ??= ?? ??= ?? deg(?) ? ?(?) Hence ?? and ?? satisfy the same set of equations. Since these equations have unique solution, therefore ??= ?? for all ?. 13
Generalization to graphs ? ? ? ? ? ? ? ? ? ? Exercise: Use your knowledge of electric circuits to find exact value of ?? in the above circuit. This will also be the value of ??. Try to realize that you would not have been able to calculate ?? using other mathematical tools that you are aware of. Isn t it surprising. Fully internalize it before proceed further for another more surprising result. We shall revise the theory of electric circuits which perhaps you might have forgotten by now. 14
REVISITING THEORY OF ELECTRIC CIRCUITS 15
Kirchoffs Current Law ? ? ? ? ? ? For any node ?in the circuit, Current entering node ? = Current leaving node? Note: This law holds for the entire circuit as well. For example, Let the above circuit is connected to outside circuit through wires at nodes ?,?,?. Question: If 5 Amperes of current enters ? and 10 Amperes of current enters ? from outside, then what current leaves/enters ?? Answer: 15 Amperes of current must leave ?. 17
Notion of Resistance and Ohms Law ? ? ? ? The current ? passing through a piece of wire is proportional to the potential difference ? applied across the two ends of it. The constant of proportionality is called resistance . ? = ?? Thus the resistance can be defined in terms of voltage and current as follows. The resistance of a wire is the potential difference that needs to be applied across its ends to pass a current of 1 ampere through it. 18
Notion of Resistance and Ohms Law ?? ?? ?? ? ? ?? ?? What made you conclude that the resistance between ? and ? is ?.???? Series law Parallel law This introduces the notion of effective resistance between two points? and ? in a given circuit. Question : In a circuit, if we increase (decrease) the value of any resistance, what will be its effect on effective resistance between ? and ? ? Answer: the effective resistance between ? and ? may only increase(decrease). 19
Notion of Resistance and Ohms Law ? ? ? ? If ? amperes of current flows from ? to ?, then ???: the potential difference from ? to ? or the potential of ?relative to ? Relation between ???and ???? ???= ??? Question: What is ??? if ? is not directly connected to ? in the circuit ? (see next slide) 20
Electric Potential is conservative ? ? ? ? ? ? Question: What is ??? ? (the battery and other wires not shown in the figure above) Answer: Consider any path from ?to ?. ??? is the sum of the potential difference at each edge on this path. ???= ???+ ???+ ??? = ???+ ???+ ??? FACT: ??? is path independent (electric potential is conservative). 21
Three simple principles Fully understand these principles so that you may apply them later on. 22
Reversibility Let ? be a valid current flow in a circuit. Question: Let ? be a flow obtained by reversing the direction of current flow in each branch of circuit. is ? also a valid current flow in the circuit ? Answer: Yes. Question: Let ??? be potential of ? relative to ? for the flow ?. ? ?? be potential of ? relative to ? for the flow ?. What is relation between ??? and ? ??? Answer: ???= ? ?? 23
Linearity of current flow Let ? and ? be any two valid current flows in a circuit. Question: Is ? + ? a valid current flow ? Answer: Yes. Question: Let ? ?? be potential of ? relative to ? for the flow ? . ? ?? be potential of ? relative to ? for the flow ? . What is potential of ? relative to ? in ? + ? ? Answer: ? ??+? ?? 24
Uniqueness ? ? ? ? ? ? If we assign any assignment of potential to nodes in the above circuit, there exists a unique and valid current flow in the circuit satisfying these potential. However, note that, this will require that you connect external wires to allow residual current to enter/leave a node to satisfy Kirchoff s law. Interestingly the converse of the above rule is also true . 25
Uniqueness ? ? ? ? ? ? If we inject and extract any arbitrary amount of current into a circuit from outside, then provided that the current satisfies Kirchoff s law (net current into circuit is 0), the current distributes itself within the circuit to give a unique and valid assignment of potentials to all nodes. The reason behind this uniqueness principle lies in the fact that there is a set of linear equations for each circuit on the basis of Kirchoff s law and Ohm s law. These equations have a unique solution. Interested students might like to explore this fact. But for this course, it is fine if you just understand this principle of uniqueness. 26
Notations ? ? ? = (?,?) ? ? ? ? ? ? ? ? ???:Expected no. of steps of the walk that starts from ? and finishes as soon as it reaches ?. Question: Any relation between ???and???? Hitting time NO ???: Expected no. of steps of the walk that starts from ?and finishes at ?after visiting ? at least once. ???= ???+ ??? Commute time 28
Expressing ???through a circuit ? ? ? ? ? ? ? ? ? ? ? deg(?) ? ?(?)??? ???= ? + 29
Expressing ???through a circuit ? ? ? ? ? ? ? ? ? ? When there is no external current into ?, Question: What is relation between ??? and ??? s where ? ?(?) ? ? ? deg(?) ? ?(?)??? ???= ? + deg(?) ? ?(?)??? An additive term of ? in equation of ??? is missing in the equation of ???. Why ? No numerical additive term appears in the equation of ??? because we derived it assuming net current into ? is 0. So in order to make the two equations similar, we need to augment the above circuit with external wires. ???= 30
Expressing ???through a circuit ? ? ? ? ? ? ? ? ? ? Let ?? be the current injected into ? from outside. Question: What be the new relation between ??? and ??? s where ? ?(?) ? ?? ? ? deg(?) ? ?(?)??? ???= deg(?)+ deg(?) ? ?(?)??? ???= ? + Question: What should be ?? in order to equate equations of ??? and ???? Observation: To equate ??? with ??? for each ? ?\{?}, we need to inject current of deg(?) into each node ?. We must extract 2? deg(?) current from ? to satisfy Kirchoff s current law. ??= deg(?) 31
Expressing ???through a circuit ? ? ? ? ? ? ? ? ? ? ??? is the potential of ? relative to ? in circuit with the following current flow ?: 1. Inject deg(?) current into each ? ?\{?}, 2. Extract 2? deg(?) current from ?. It follows from the uniqueness principle that ? will be a valid current flow in the circuit. In a similar manner, could you express ??? ? 32
Expressing ???through a circuit ? ? ? ? ? ? ? ? ? ? ??? is the potential of ? relative to ? in circuit with the following current flow ? : 1. Inject deg(?) current into each ? ?\{?}, 2. Extract 2? deg(?) current from ?. 33
??? + ???= ?? ? ? ? ? ? ? ? ? ? ? Apply principle of Reversibility ???= ??? in circuit(?) with current flow ?. ? ? ? ? ? ? ? ? ? ? 34 ???= ??? in circuit(?) with current flow ? .
??? + ???= ?? ? ? ? ? ? ? ? ? ? ? Apply principle of Linearity ???= ??? in circuit(?) with current flow ?. ? ? ? ? ? ? ? ? ? ? ???= ??? in circuit(?) with current flow ? . 35
??? + ???= ?? ? ? ? ? ? ? ? ? ? ? ???+ ??? = ??? in circuit(?) with current flow ? ? . Question: What does the circuit(?) with current flow ? ? look like ? Hint: External current cancels at each node except at ? and ?. 36
??? + ???= ?? ? ? ? ? ? ? ? ? 2? ? 2? ? ???+ ??? = ??? in circuit(?) with 2? current entering ?and 2? current leaving ?. = 2? ???, where ??? is the effective resistance between ? and ?. 37
Theroem: Given an undirected graph ? = (?,?) on ? edges, commute time between any pair of vertices ? and ? is 2? ???, where ??? is the effective resistance between ? and ? in the circuit associated with ?. 38
Commute Time of some well studied graphs 39
Useful tips You may use one or more of the following principles to calculate effective resistance any pair of vertices ? and ?. Increasing resistance of some edges to infinity (equivalent to removal of those edges) will only increase the effective resistance between ? and ?. Apply series and parallel law of resistance can be a useful tool sometimes. Any flow from ? to ? in the circuit will consume same or more amount of power than the corresponding current flow of same value from ? to ?. So effective resistance between any pair of vertices is bounded by the power dissipated due to any flow of 1 ampere from ? to ? in the circuit. (This is called the least power law) 40
Two complete graphs joined by an edge Let ? and ? be two complete graphs on ? vertices. We add an edge between a vertex in ? and a vertex in ?. What is the maximum commute time in this combined graph ? 41
Grid Given ?-by-? grid, calculate commute time between vertices ? and ?. Use least power law, and distribute 1 ampere of current evenly from ? to ?. ? ? (the solution was sketched in the lecture class) 42
