Is there any relation between random walk and eigen-vectors of adjacency matrix other than the first one in graph?

Question

I want to know more about what the relation is between random walk and eigen-vectors of adjacency matrix of graph. I know that the first eigen-vector of adjacency matrix is related to the stationary state of random walk. But I couldn't find any relation between random walk and other eigen-vectors.

Answer 1

Everything pretty much. Let us assume for simplicity's sake that $G$ is $d$-regular (for some positive integer $d$) and connected for simplicity. Then the adjacency matrix $A$ of $G$ multiplied by $d^{-1}$ is the transition matrix. In particular: Let $\chi_0$ be the probability distribution on the starting point of a random walk $W$. [$\chi_0$ can be 1 at one vertex and 0 everywhere else but more generally any stochastic vector will do for $\chi_0$.] Then

1. $\chi_0$ can be rewritten uniquely $\sum_{i=1}^n x_i$ where $x_i$ is a scalar multiple of the $i$-th eigenvector of $A$ and in fact the $x_i$s are mutually orthogonal and in particular the coordinates of $x_i$ for all $i > 2$ add to 0, and $x_1$ is the vector of all $\frac{1}{n}$s, and $\sum_{i=1}^n ||x_i||^2_2 = ||\chi_0||^2_2$.

2. The distibution of where the random walk is after $k$ steps is $\left(d^{-1}A\right)^k\chi_0 = x_1 + \sum_{i=2}^n d^{-k}\lambda^k_ix_i$, where $\lambda_i$ is the eigenvalue of $x_i$.

Therefore, note the following: If the size of every eigenvalue but the 1st is significantly less than $d$ i.e., $\lambda_i \le (1-\epsilon)d$ for some $\epsilon \in \theta(1)$ for all $i =2,\ldots, n$, then $\left(d^{-1}A\right)^k\chi_0$ converges quickly with $k$ to the unique stationary distribution. If the graph is bipartite, then $\lambda_2$ is $-d$, and $\left(d^{-1}A\right)^k\chi_0$; $k$ even; converges to $x_1 + x_2$; while $\left(d^{-1}A\right)^k\chi_0$; $k$ odd; converges to $x_1 - x_2$.

Something to think about: What if $G$ is $d$-regular but not connected?