# Question from section 1.5 of Chung's Spectral Graph Theory

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?

-

## 2 Answers

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$.

-
Thanks for your reply. You're correct that I overlooked the minus sign. You're also correct that I should have asked why $\beta_0$ has a 1 in the numerator, rather than why $\alpha_0 \neq \beta_0$. That minus sign probably answers this question, but I don't see how. Can you (or someone) clarify further? –  Dimitrije Kostic Nov 23 '11 at 16:21
@DimitrijeKostic I interpretted the question to mean: why isn't this obvious answer not the correct answer? And my answer does address that: since you overlooked the minus sign. Now I don't see what more you want out of an answer. Do you want the derivation of the expressions for $\alpha_0$ and $\beta_0$? [Note: I haven't given any serious thought to it and that explains my making it CW :).] –  Srivatsan Nov 23 '11 at 16:26
Yes, I'm principally interested in where the formulas for $\alpha_0$ and $\beta_0$ come from. That minus sign is surely the reason why they're dissimilar. I really should have phrased my questions more carefully. I'm sorry for that. –  Dimitrije Kostic Nov 23 '11 at 16:42

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)}}$.

-