Notes for 10/8/98
* random walks on graphs Chap 6.1, 6.3, 6.4, 6.5
============================================================================
Turn to new topic: random walks on graphs.
Lots of applications:
- approximation/estimation problems: estimating permanent, volumes
- random selection: pick a random consistent linear separator.
- derandomizing randomized algs.
Plus, it's neat by itself. Say you're lost in a maze and don't want to
make a map. How long will it take to get out if you just move around randomly?
Random walk on a graph: Start at some initial vertex. Pick neighbor
at random and go there, etc. Equivalently, think of as currently on
some edge heading in some direction. Then move to random neighboring
edge in forward direction.
Interesting quantities to look at:
H_uv = "hitting time" from u to v: E[#steps to first reach v | start at u]
C_uv = "commute time: E[# steps to go from u to v then back to u]
C_uv = H_uv + H_vu. Why?
(linearity of expectation: X = # steps to first hit v.
Y = # steps to hit u after first hit v.)
C_u = "cover time from u" is the expected time to visit entire graph
when we start at u.
C_G = "cover time of G" = max_u ( C_u )
THEOREM: If G is connected, n vertices, m edges, then C_G <= 2m(n-1).
We will prove this in two ways.
Implication: s-t connectivity in "randomized log space". Only have
O(log n) bits of read/write memory, and required to halt in poly time,
can determine connectivity with 1-sided error.
------------------------------------------------------------------------------
Method 1:
For convenience, let's think of ourselves as at each time step being
on some edge heading in some direction (as opposed to being at a
node).
Lemma: average time between successive visits to directed edge u-->v = 2m.
Note: this implies that if u and v are neighbors, then C_vu <= 2m. Why?
(the expected time to go from v to u to v <= expected time if we
wait until we actually take the u-->v edge)
Proof of lemma:
Suppose we started by picking an edge and direction at random. So,
our distribution has prob 1/2m on each directed edge. What is our
distribution after one step?
Answer: the same. Pr( we're now on edge v-->w) = Pr( we were on an
edge u-->v) * Pr( took v-->w | we were on u-->v) = [d(v)/2m]*[1/d(v)] = 1/2m
So this is a fixed-point.
[Aside: in fact, no matter how we start, so long as graph is connected
and has an odd cycle, we'll approach this distribution. If no odd
cycles then alternate b/w odd times t and even times t]
So, over a sequence of t steps, the expected number of times we
traverse edge u-->v is t/2m.
Now, we want to invert this to say that the expected time between two
consecutive traversals of u-->v is 2m.
.........u->v..............u->v.......u->v....................u->v
"in t steps expected # u->v's is t/2m so average gap must be 2m, right?"
Let's be careful about this: eg, if graph was two disconnected
equal-size pieces, then the expected time between consecutive
traversals of u->v would be m, since with prob 1/2 there would be no
visits and with prob 1/2 there would be about t/m visits. And,
expected time to the first visit would be infinite.
Formally, the property we need to make this inference is that the
variance of the RV "length of the jth gap" is finite. If graph is
connected, can see variance is finite since in each n steps (no matter where
we start), have at least a 1/2^n chance of crossing this edge (this is
way undercounting).
The reason we want this is imagine the experiment "keep walking
until have made s visits to u->v edge". Since variance is finite,
this will occur in finite time with probability 1. Now use Law of
Large Numbers which says that if repeat an experiment indepdendently s
times then as s->infinity, the observed average value will with
probabiltiy 1 approach its expectation. In our case, this means that
observed average gap length approaches its expectation. This means
that with probability 1, the observed number of traversals (which is
t/[observed average gap length]) is approaching t/E[gap length]. This
must be t/2m since it can't be the case that the observed number of
traversals approaches with probability 1 something that is not its
expectation, since it is a bounded quantity.
Where are we now: we have that the average time between successive
traversals of some edge u-->v is 2m.
---------------------------------------------------------------------
To finish the proof about the cover time of graph:
Let's consider some spanning tree of the graph. Has n-1 edges.
Consider some fixed tour on the spanning tree. --> traverses each
edge twice. So,
E[time to visit nodes in that order] = sum, over all directed edges
(u,v) in the tree, of H_uv. For each {(u,v), (v,u)}, get
H_uv + H_vu = C_uv <= 2m.
Since n-1 edges, we get:
2m(n-1).
===========================================================================
Proof 2.
Something different: resistors.
Resistive network is a graph with resistors on the edges. E.g.,
*-----2 Ohms------*
| |
1 Ohm 2 Ohms
| |
*-----3 Ohms------*
Say we hook up a battery. Then each node has a voltage ("potential")
and each edge has a current.
Kirchoff's law: current is like water flow. For any node, sum
entering equal sum leaving.
Ohm's law: V=IR. (V = voltage difference across resistor).
Voltage is a property of a node. Sometimes called "potential".
Two resistors in series add resistance:
*-------R1--------*-------R2-------*
V0 V1 V2
Say I = current flowing from left to right. Then V1 = V_0 - I*R_1.
V2 = V0 - I*R1 - I*R2 ==> delta(V) = I(R1 + R2).
_____R1______
/ \
Two resistors in parallel: V0* *V1
\_____R2______/
1/R = 1/R1 + 1/R2.
See via: I1 = (V0 - V1)/R1, I2 = (V0-V1)/R2. and I=I1+I2.
Neat fact:
THEOREM: Take a graph G and think of each edge as a unit resistor.
Let R_uv = effective resistance between u and v. Then an exact expression
for the commute time is
C_uv = 2m R_uv.
I.e., say we set voltage at v to 0, voltage at u to V_u such that
current flowing = 2m. Then, V_u = C_uv.