Diffusion on the discrete cube

I wanted to say a few more words about the "diffusion process" on the discrete cube, mentioned in Lecture 1. Actually, on any graph you can set up an analogous process - basically, a "continuous-time" random walk on the graph.

Given a graph $G = (V,E)$, its Lapalacian $L$ is usually defined to be the $V \times V$ symmetric matrix that has a $-1$ in entries $(i,j)$ and $(j,i)$ when this is an edge, deg($v$) in the $(v,v)$ diagonal entry, and zeroes elsewhere.

In our case we considered the discrete cube, $G$, with $V = \{-1,1\}^n$ and $(x,y) \in E$ iff $x$ and $y$ have Hamming distance 1.

You can see now that the diffusion equation I gave in Lecture 1 says that for functions $f : V \to \mathbb{R}$, the rate of change of $f(x)$ with respect to time is defined to be $(-1/2)L f$. (The factor $-1$ is important here, but the factor $1/2$ is not; it just slows down time by a factor of $2$.) The same diffusion process can be set up for any graph.

Further, the "basic solutions" to this differential equation - by which I mean those $f : V \to \mathbb{R}$ that just decay with time but don't change their "shape" - are the eigenvectors of the matrix $L$; i.e., the functions such that $L f = \lambda f$ for some constant $\lambda$. On the discrete cube, it's easy to check that the $2^n$ parity functions are all eigenvectors, and since they are linearly independent in a space of dimension $2^n$, linear algebra tells us this is all of them.

I'm not sure if there's a more principled way to derive the fact that the parity functions are the eigenvectors of $L$, as opposed to just observing that they are and that they are sufficient in number. Maybe someone can figure this out.

For way more on this than you might want to know, see this paper by Bobkov and Tetali. It can be hard reading, but you might want to at least check that the quantity $\mathcal{E}(f,f)$ they introduce on line 4 is our "energy" $\mathbb{I}(f)$, up to a constant. (Indeed, $\mathcal{E}$ stands for "energy" in their paper.)