Due date: Thursday, Oct 21.
Please submit your solutions by upload on Canvas.
It's absolutely OK if you work together on these problems - and this is especially true for the programming problems, when encourage you to work in pairs at one computer, with one person typing and one person thinking.
We do want everyone to write up each assignment on their own.
Recall that the adjacency matrix $A$ of an undirected graph is the matrix with $A_{ij} = 1$ if there is an edge between $i$ and $j$ in the graph, and $A_{ij} = 0$ otherwise. A $d$-regular graph is one for which the degree of every vertex is exactly $d$.
a. Show that the adjacency matrix of the complete graph on $n$ vertices (i.e., the $(n-1)$-regular graph) has two eigenvalues: $n-1$, with multiplicity 1, and $-1$, with multiplicity $n-1$.
b. Show that the adjacency matrix of any $d$-regular graph has an eigenspace with eigenvalue $d$. What determines the dimension of this eigenspace?
One way to sample a uniform spanning tree of a graph $G$ is the Aldous-Broder algorithm: choose a vertex $r$ of $G$ and perform a random walk on $G$, starting at $r$, until every vertex has been visited. For each vertex $w \neq r$, remember the edge that was traversed by the walk on it's first visit to $w$. These edges are the uniform spanning tree. (For simplicity, we're dealing with an unweighted graph - all weights are 1 - and the "random walk on a graph" is the one that, at each time step, chooses a random edge incident to the vertex it's currently at to move along.)
(a) Implement the Aldous-Broder algorithm on the $m \times n$ grid.
(b) Plot an example or two on a 30x40 grid. (It may be helpful to look at the plotting code here.
(c) How many spanning trees are there of the 30x40 grid?
Use the Metropolis-Hastings algorithm to sample from the Ising model's distribution, and plot the results on a 100x100 grid at $T=0.01$. Explain carefully why your algorithm works. Here is some skeleton code to do this:
class Ising(object):
def __init__(self, n, m):
self.n = n
self.m = m
self.state = np.random.choice([-1, 1], n*m).reshape((n, m))
def plot(self):
fig, ax = plt.subplots()
ax.set_aspect(1)
xy = np.array([[a, b] for a in range(self.n) for b in range(self.m)])
fills = ['black' if (s == 1) else 'white' for s in self.state.reshape((self.n*self.m,))]
ax.scatter(xy[:,0], xy[:,1], c=fills, marker="8", s=5)
def update(self, T):
## FILL ME: should do one Metropolis-Hastings update step
## to self.state
ising = Ising(100, 100)
for _ in range(100000):
ising.update(0.01)
ising.plot()
Let $X$ be the random walk on an unweighted graph $G = (V,E)$, i.e., the transition probabilities are $\mathbb{P}\{X_{k+1} = y \;\|\; X_k=x\} = 1/\text{deg}(x)$ for $(x,y) \in E$ and 0 otherwise.
(a) Show that $X$ is reversible with respect to $$ \pi(x) \propto \text{deg}(x) .$$
(b) Let $A$ be the adjacency matrix of the graph and $D$ be the diagonal matrix with $D_{xx} = \text{deg}(x)$. Show that $P = $D^{-1} A$ is the transition matrix for $X$, so $$ \mathbb{E}[f(X_t) \;|\; X_0 = x] = (P^t f)(x) . $$
(c) How could we minimally modify the random walk so that the stationary distribution was uniform?