Question from section 1.5 of Chung's Spectral Graph Theory

Question

I'm (slowly) reading Fan Chung's Spectral Graph Theory. At the moment, I'm in section 1.5 which is about eigenvalues and random walks. There's a small technical point that puzzles me.

The context is a graph $G$. Let $T$ be the matrix whose $(v,v)^{\text{th}}$ entry is the degree $d_v$ of $v$. Let the volume $\operatorname{vol}(G)$ denote $\sum_v d_v$. A walk on $G$ is a finite sequence of adjacent vertices in $G$, and a random walk is given by a stochastic matrix whose $(u,v)^{\text{th}}$ entry is the probability $P(u,v)$ of walking from vertex $u$ to vertex $v$. If $f :V(G)\rightarrow \mathbb{R}$ is any initial stochastic distribution (i.e., $\sum_v f(v) =1$) then if we think of $f$ as a vector of length $|V(G)|$ the distribution after $k$ steps is simply $fP^k$. The random walk is ergodic if there is a unique stationary distribution $\pi(v)$ satisfying $\lim_{s \to \infty} fP^s(v) = \pi(v)$. This section of Chung's book is devoted to measurements of closeness between $fP^s$ and $\pi$, and estimates of how large $s$ must be for these two distributions to be close to each other.

The following is on page 17.

After $s$ steps, the relative pointwise distance (r.p.d.) of $P$ to the stationary distribution $\pi(x)$ is given by $$ \Delta(s) = \max_{x,y} \ \frac{|P^s(y,x)-\pi(x)|}{\pi(x)} $$ Let $\Psi_x$ denote the characteristic function of $x$ defined by: $$\Psi_x(y) = \begin{cases} 1, & \text{if } y=x, \\ 0, & \text{otherwise}. \end{cases} $$ Suppose $$\Psi_x T^{1/2} = \sum_i \alpha_i \Phi_i $$ $$ \Psi_y T^{1/2} = \sum_i \beta_i \Phi_i $$ where $\Phi_i$'s denote the eigenfunction of the Laplacian $\mathcal{L}$ of the weighted graph associated with the random walk. [Note: Chung discusses edge weights in this section. For the purposes of this discussion, though, I think you can just think about unweighted graphs.] In particular, $$ \alpha_0 = \frac{d_x}{\sqrt{\operatorname{vol}(G)}}$$ $$ \beta_0 = \frac{1}{\sqrt{\operatorname{vol}(G)}}$$

I cannot understand why $\alpha_0 \neq \beta_0$. It looks like $x$ and $y$ are arbitrary vertices and she's expressing the functions $\Psi_x T^{1/2}$ and $\Psi_y T^{1/2}$ that they determine in a canonical basis. Why should those representations be any different?

Answer 1

I suspect that you copied the equation down incorrectly. According to the online version of the notes by the same author (p. 17), the defining equation for $\beta_i$ should read $$ \psi_y T^{\; \color{Red}{-1/2}} = \sum_i \beta_i \phi_i. $$ Notice the negative sign in the exponent. (To be consistent with the linked notes, I use $\psi$ and $\phi$ instead of $\Psi$ and $\Phi$ respectively.)

However, if what you wrote down were correct, it still wouldn't mean that $\alpha_0 = \beta_0$. Since $\alpha_0 = \frac{\color{Red}{d_x}}{\sqrt{\operatorname{vol} G}}$, it would follow from symmetry that $\beta_0 = \frac{\color{Red}{d_y}}{\sqrt{\operatorname{vol} G}}$; certainly related to but not quite the same as $\alpha_0$.

Answer 2

Have a look at page 15. There, a more general computation is carried out to determine $a_0$ in $$f T^{-1/2} = \sum_i a_i \phi_i.$$ Thus, the goal is to compute the coefficients $a_i$ for the representation of $fT^{-1/2}$ according to the base $\{\phi_0, \phi_1, \ldots\}$. This is the same as for $f = \psi_y$ and $a_0 = \beta_0$ in your problem formulation (with corrected exponent). Thus, using that the first eigenvector is known to be $\phi_0 = \mathbf{1} T^{1/2} / vol(G)$, we get for the projection of $fT^{-1/2}$ onto $\phi_0$ that:

$$a_0 = \frac{\left<f T^{-1/2}, \mathbf{1} T^{1/2} \right>}{\|\mathbf{1}T^{1/2}\|_2},$$where the $vol(G)$ in numerator and denominator cancels out (one could also just use that $\phi_i$ is normalized and set the denominator to $1$, keeping $vol(G)^{-1}$ in the numerator).

Here, $\|\mathbf{1}T^{1/2}\|_2 = \sqrt{\sum_i d_i} = \sqrt{vol(G)}$ for the denominator. In the numerator we get with $fT^{-1/2} = (f_1 \frac{1}{\sqrt{d_1}}, f_2 \frac{1}{\sqrt{d_2}}, \ldots)$ and $\mathbf{1} T^{1/2} = (\sqrt{d_1}, \sqrt{d_2}, \ldots)$ that their scalar product is $\sum_i f_i$. Thus, for $f = \psi_y$, the scalar product is $1$, leading to $\beta_0 = \frac{1}{\sqrt{vol(G)}}$.

Now, we also see what's going on in determining $\alpha_0$. Therein, the numerator is $\left<f T^{1/2}, \mathbf{1} T^{1/2} \right> = \sum_i f_i d_i$, which gives $d_x$ for $f = \psi_x$, thus, $\alpha_0 = \frac{d_x}{\sqrt{vol(G)}}$.