covers the random walk topic in [[00_Plan]]

Random Walks¶

Markov Chains¶

A random walk that is time homogenous (the only relevant detail is the state we're at, not the time we reach it at) can be represented as a single markov chain - edges are nonzero transition probabilities between states

Transition Matrix¶

• \(W_{i,j}^k\) : Gives the probability of reaching \(j\) from \(i\) after \(k\) steps. Why?
• The \(i,j\)th entry of the \(k\)th power of the transition matrix gives the sum of the weights of \(k\) length paths from \(i\) to \(j\)
  • the weight of each path is the product of the edges in the path
  • which means the weight of each path is the likelihood of taking that path
  • the sum of these path weights therefore gives the likelihood of reaching \(j\) from \(i\) in \(k\) steps
• We can find the probability from an \(n \times 1\) starting distribution \(X\) of ending up in the final distribution by matrix multiplication \(X W\)

Stationary Distribution¶

We can represent a random walk from a starting distribution \(X_0=[\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}]\) (uniform sample of starting node) as \(X_1 = X_0 W\). Since the walk is markovian, then it must be that \(X_2 = X_1W = X_0W^2\) , so \(X_i = X_0W^i\) This equation makes intutive sense because \(W^k_{i,j}\) tells us the likelihood after \(k\) steps of moving from \(i\) to \(j\). So from a starting position \(X_0\), the ending position after \(k\) steps would be modeled by \(W^k\).

Eventually, we have that \(W^i=W^{i+1}\). In such a case, \(X_i = X_{i+1}\), which is known as the stable distribution. This occurs when \(X_0W^i = X_0W^{i+1}\) In other words, for certain transition matrices (strongly connected + aperiodic), \(W^k = W^{k+1}\) for sufficiently large \(k\). intuitively, this connects to the above section: \(W^k_{i,j}\) represents the likelihood of reaching each vertex from any other vertex in \(k\) steps.

Importantly, the stable distribution is seemingly a result of the transition matrix, and not the starting distribution, since it depends on \(W^k=W^{k+1}\)

We denote the stationary distribution as \(\pi\), where \(W\pi = \pi\) For a single \(\pi_i\), the distribution is stationary if \(\pi_i = \sum_{j=1}^n \pi_j W_{j,i}\) We can solve for \(\pi_i\) when the number of states is small or the transition matrix isn't too complicated by matrix multiplication. Simply set \(\pi = [p, 1-p]\) Otherwise, we can try to solve for a single \(\pi_i\) above or try to use the detailed balance condition: \(W_{ij}\pi_j = W_{ji}\pi_i\) This is often true for symmetric transition matrices.

Properties of Stationary Distributions¶

If G is strongly connected, then G has a unique stationary distribution to prove strongly connected, we must show that there's a path between any two vertices by describing how, if we start at an arbitrary vertex, we can find a path to another vertex deterministically. As long as we can reach it through some probability, we know we will reach it If G is aperiodic, then a random walk converges to a stationary distribution aperiodic: the greatest common denominator of all cycles is 1. easiest if there are self-loops.

Key Conceptual Detail¶

a markov chain can be described entirely by a transition matrix. The transition matrix depends on the problem formulation, and doesn't change over time. The distribution describes the probability of being at each state at a given time, and is found by multiplying the starting distribution by the transition matrix raised to the \(k\)th power. The stationary distribution arises when \(W^k = W^{k+1}\), which occurs whenever W is strongly connected. The stationary distribution is therefore a result of the characteristics of the stationary distribution.

Mixing Time¶

The time it takes for the markov chain to get "close" to the stationary distribution.

Coupling¶

we're interested in the case where two random walks on the same graph end up at the same state - they've coupled.

We can study mixing time via coupling by letting one random walk start at the stationary distribution. The mixing time is the time it takes for the walks to couple.

Coupling Strategy: Given two states \(X_t, Y_t\), we can come up with a strategy to couple the two if one is at the stationary distribution then it can walk around as much as it wants without changing the distribution? Simple example: Let a markov chain represent the values of two bits \(b_1, b_2\). A step in the random walk changes a single bit. Then \(X_t = b_1 b_2 X_{t+1}\) - how can we get two states \(X_t, Y_t\) to reach the same state as fast as possible? - coupling strategy: take a step on the random walk for \(X_t\), and take a step in the same direction on \(Y_t\). - a step = randomly choose a bit (b1 or b2) and randomly choose a value (0 or 1) - to take a step in the same direction, we set the same bit to the same value - This is a common motif, that we sample normally for the first state, and then based on the outcome, figure out what to do for the second state. More complicated example, see #Mixing Time Via Coupling for specific example which i don't really understand

Other Characteristic Times¶

Hitting Time¶

The minimum time \(\tau_{x, v}\) it takes from a starting distribution \(v\) to reach another distribution \(x\). - seems analogous to the distance between distributions

The hitting time of a time-homogenous markov process \(X\) is the max hitting time between any two vertices (the most 'far apart' distributions)

First Return Time¶

\(\tau_{x}^+\) the min time it takes to return to the starting distribution \(x\) for example, a graph where there's a highly weighted edge pointing back to the starting node would have a low first return time. For an irreducible markov chain, all hitting and first return times are finite

For an irreducible markov chain, \(\pi(x) = \dfrac{1}{\tau_x^+}\)

The stationary distribution tracks how likely it is to return to a state

Since \(\pi(x)\) tracks the probability of reaching state x from the stationary distribution, the number of steps to return to state x from x is simply the reciprocal of that.

Cover Time¶

The cover time of \(v\) is \(\tau_v\) : the max hitting time between \(v\) and any other distribution \(x\) apparently also the expected time until all states are visited starting from \(v\) The cover time of \(X\) is the max cover time from any starting distribution in \(X\)

As a whole, the hitting time/cover time of the entire markov process is the max time for any starting vertex.

Time relationships¶

For a finite irreducible markov chain, \(\(\tau_{hit} \leq \tau_{cover} \leq \tau_{hit} \sum_{i=1}^{|D|} \frac{1}{i}\)\)

Time to hit less than time to cover makes a lot of sense, since the cover time is just the hit time for the furthest vertex.

Electrical Networks¶

Electrical network is a weighted undirected graph G=(V,E,c), where c are the conductances of the edges (analogous to capacity). We can also identify a source and sink in G. seems analogous to flow problem, but with undirected edges Electrical networks closely related to reversible markov chains

Reversibility¶

Detailed Balance Conditions: Time-homogenous markov process is reversible if \(\pi_uW_{uv} = \pi_v W_{vu}\) for all \(u,v \in D\) A reversible markov chain looks the same regardless of whether we run the random walk forwards or backwards in time. recall that a markov chain is used to describe a time-homogenous stochastic process, like a random walk. think about the pset, where we reversed the random walk and showed that a different algorithm, reversed algorithm was able to produce the same markov chain Not all markov chains are reversible, but random walks on weighted graphs are reversible

Electric Network as Markov Chain¶

For an electrical network \(G=(D, E, c)\), we can represent it as a markov chain by letting the conductance \(c(u,v)\) be the likelihood of reaching vertex \(v\) from \(u\) in the stationary distribution, such that \(c(u,v) = \pi_u W_{u,v}\) Which means \(\pi_v = \sum_{i=1}^{|V(G)|} \pi_i W_{i,v} = \sum_{i=1}^{|V(G)|} c(u,v)\)

Since the electrical network is undirected, we have that \(c(u,v) = c(v,u)\), which means the markov chain is reversible! \(\pi_uW_{uv} = \pi_v W_{vu}\)

Harmonic Function¶

Kind of like the inverse of stationary distribution. instead of \(\pi W = \pi\) (stationary), we have \(W \pi = \pi\) \(f\) is harmonic at \(x \in D\) wrt \(W\) if \(f(x) = \sum W_{xy} f(y)\) for all \(y \in D\) uniqueness: if \(f, g\) are harmonic on \(S \subset D\) and agree on the elements not in the subset, then \(f = g\)

Voltages are harmonic:¶

Before we defined \(c(u,v) = \pi_u W_{u,v}\) \(W_{u,v} = c(u,v)/\pi_u\) where \(\pi_u = \sum_{i=1}^{|V(G)|} c(u,v)\), such that we can define W as $$ W_{xy} = \dfrac{c_{xy}}{\sum_{y \in V} c_{xy}} $$

![[Pasted image 20221111205140.png|600]]

Escape Probabilities are Harmonic¶

\(p_x\) is the probability that a random walk beggining at \(x\) reaches \(u\) before reaching \(v\) \(p_x = \sum_{y \in D} W_{xy}p_y\) Uniqueness implies \(p_x = v_x\)

Tips for solving problems¶

• first and foremost, we must define what a node in the markov chain is.
• then, think about the transition matrix

• from transition matrix, we can do plenty of things like finding the stationary distribution

• finding a stationary distribution mathematically can be difficult. Write out all the relationships we know

• \(\pi_i = \sum_{j=1}^n W_{j,i} \pi_j\)
• \(\sum_{i=1}^n \pi_i = 1\)

Example Slides¶

Mixing Time Via Coupling¶

![[Pasted image 20221111111356.png]]