0
$\begingroup$

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 2

2

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

  • 0
    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.2011-11-23
0

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}{\|\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 = \sum_i f_i d_i$, which gives $d_x$ for $f = \psi_x$, thus, $\alpha_0 = \frac{d_x}{\sqrt{vol(G)}}$.