Random Walks on Graphs

At any node, go to one of the neighbors of the node with equal probability.

Let’s start simple…We’ll just walk in a straight line.

Random walk on a line

You go into a casino with , and at each time step, you bet on a fair game. You leave when you are broke or have .

Question 1: What is your expected amount of money at time ? Let be a random variable for the amount of money at time .

where is a random variable for the change in your money at time . , since for all situations at time - either you are at or and not moving, or you have an equal probability of increasing your money by and decreasing your money by . So, .

Question 2: What is the probability that you leave with ? The expected value may be rewritten to reflect the expected values for different values of :

As approaches , approaches 0. Also, is clearly 0. These two terms drop out, and ; so the whole equation may be reduced to . Hence, .

Or...The line may be thought of as a simple graph, with a red node at 0 and a green one at .

So, considering a general graph, what is the probability that you reach green before red? Consider what happens if we build a circuit based on the graph, where the resistors in the circuit correspond to edges on the graph. Then, add in a 1-volt battery: connect the positive end to the green node, and the negative end to the red node. Now, measure the difference in voltage between the starter node and the red node. It turns out that this voltage difference is exactly the same as the probability that you'll reach green before you reach red.

Why is this true? Let denote the probability of reaching the green node first, when starting from the node . Look at the equations for :

• ,
• Otherwise, Average of the probabilities of the surrounding nodes.

These equations are exactly the same as the physical equations describing the voltage in a circuit (assuming that all resistors are identical). Electrical networks save the day!

voltage() !!!

Of course, it holds for general graphs as well. Let's move on to some other questions on general graphs

Getting back home

Lost in a city, you want to get back to your hotel. How should you do this? Depth First Search requires a good memory and a piece of chalk? Will walking randomly with just coins work? Is Pr[ reach home ] = 1? When will you get home? What is E[ time to reach home ]?
Yes, . Furthermore:
If the graph has nodes and edges, then is at most this.

Cover times

Let us define a couple of useful things:
Cover time (from vertex )

Cover time of the graph:

Cover Time Theorem

If the graph G has n nodes and m edges, then the cover time of G is

Any graph on vertices has edges. Hence for all graphs G.

First, let's prove that

We will eventually get home
Look at the first steps.
There is a non-zero chance that we get home.
Suppose we fail.
Then, wherever we are, there a chance that we hit home in the next n steps from there.
Probability of failing to reach home by time

In fact
Recall:
An averaging argument
Suppose I start at .

Hence, . Why? Else this average would be higher. (called Markov's inequality.)

Markov's Inequality

Random variable X has expectation A = E[X].
A = E[X]
= E[X | X > 2A ] Pr[X > 2A] + E[X | X ≤ 2A ] Pr[X ≤ 2A]
≥ E[X | X > 2A ] Pr[X > 2A]
Also, E[X | X > 2A] > 2A, so
A ≥ 2A × Pr[X > 2A]
½ ≥ Pr[X > 2A]
Pr[ X exceeds k × expectation ] ≤ 1/k.

Suppose I start at u.
E[ time to hit all vertices | start at u ] ≤ C(G)
Hence, by Markov’s Inequality
Pr[ time to hit all vertices > 2C(G) | start at u ] ≤ ½.

So let's walk some more!

Pr [ time to hit all vertices > 2C(G) | start at u ] ≤ ½.
Suppose at time 2C(G), am at some node v, with more nodes still to visit.
Pr [ haven't hit all vertices in 2C(G) more time | start at v ] ≤ ½.
Chance that you failed both times ≤ ¼ !

The power of Independence

It is like flipping a coin with tails probability .
The probability that you get k tails is . (because the trials are independent!)
Hence,
Pr[ havent hit everyone in time k × 2C(G) ]
Exponential in k!
Hence, if we know that Expected Cover Time
C(G) < 2m(n-1)
then Pr[ home by time 4km(n-1) ] ≥ 1 –

Random walks on infinite graphs

A drunk man will find his way home, but a drunk bird may get lost forever- Shizuo Kakutani
On an infinite, 3-D grid, you are not guaranteed to return to where you start.

Random Walk on a line

Flip an unbiased coin and go left/right.
Let be the position at time t
Pr[ ]
= Pr[ #heads - #tails = i]
= Pr[ #heads – (t - #heads) = i] =

Unbiased Random Walk

Pr[ = 0 ] =
Stirling's approximation:
Hence:

Pr[ ] =
= indicator for ()
E[ ] =
= number of visits to origin in 2n steps.
E[ ] = E[ ] =

In n steps, you expect to return to the origin times!
Simple Claim
Recall: if we repeatedly flip coin with bias p
E[ # of flips till heads ] = 1/p.
Claim: If Pr[ not return to origin ] = p, then
E[ number of times at origin ] = 1/p.
Proof: H = never return to origin. T = we do.
Hence returning to origin is like getting a tails.
E[ # of returns ] = E[ # tails before a head] = 1/p – 1.
(But we started at the origin too!)
We will return…
Claim: If Pr[ not return to origin ] = p, then
E[ number of times at origin ] = 1/p.
Theorem: Pr[ we return to origin ] = 1.
Proof: Suppose not.
Hence p = Pr[ never return ] > 0.
E [ #times at origin ] = 1/p = constant.
But we showed that E[ ] =

How about a 2-d grid?
Let us simplify our 2-d random walk: move in both the x-direction and y-direction…
Returning to the origin in the grid means both “line” random walks return to their origins
Pr[ visit origin at time t ] = Θ(1/√t) × Θ(1/√t) = Θ(1/t)
E[ # of visits to origin by time n ] = Θ(1/1 + 1/2 + 1/3 + … + 1/n ) = Θ(log n)

We will return (again!)…
Claim: If Pr[ not return to origin ] = p, then
E[ number of times at origin ] = 1/p.
Theorem: Pr[ we return to origin ] = 1.
Proof: Suppose not.
Hence p = Pr[ never return ] > 0.
E [ #times at origin ] = 1/p = constant.
But we showed that E[ ] =

But in 3-d
Pr[ visit origin at time t ] =
E[ # of visits by time n ] < K (constant)
Hence
Pr[ never return to origin ] > 1/K.