5
$\begingroup$

For my master's thesis research, I stumbled upon a question concerning the Metropolis-Hasting transition matrix $W$.

Context $\quad$ Let me start with some context. I consider connected undirected graphs $G=(V,E)$; here $V=\{1,\ldots, M\}$ and $E$ is the edge set. I denote the neighbor sets by $\mathcal{N}_i$ and the degree of each node by $d_i$. In this context, I consider the Metropolis-Hasting transition matrix $W=[w_{ij}]$, defined by: \begin{equation*}\label{eq:N} w_{ij} := \left\{ \begin{array}{ll} \frac{1}{\max\{d_i, d_j\}+1} & \text{if} \: j \in \mathcal{N}_i, \\ 1-\sum_{j\in\mathcal{N}_i}w_{ij} & \text{if} \: j=i, \\ 0 & \text{otherwise}. \end{array} \right. \end{equation*} It is known that this matrix is symmetric doubly stochastic, such that we have real eigenvalues $1=\lambda_1>\lambda_2\geq \cdots\geq \lambda_M > -1$.

Question $\quad$ Now, i would like to show a sharper lower bound for $\lambda_M$, namely: $$\lambda_M\geq-\frac{1}{2}.$$

I don't know if this is true actually, but I considered (in Matlab) many randomly produced graphs with $M=100$. I varied the amount of edges from $0.05k_\max$ up to $0.9k_\max$, where $k_\max=\frac{1}{2}(M^2-M)$. In this way I considered over $10\:000$ matrices, and there was no counter example found. Otherwise, if there is a way to find a counter example then that would be helpful as well.

Findings so far $\quad$ I came up with an alternative formulation, using the definition for the field of values. It can be shown that it is equivalent to show that: $$\sum_{i=1}^M\left( \: \sum_{j\in \mathcal{N}_i} \frac{x_i^2 - x_ix_j}{\max\{d_i,d_j\}+1} \right) = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \frac{3}{2},$$ for any $x = [x_i] \in \mathbb{R}^M$ with $x^Tx =\sum_{i=1}^Mx_i^2=1$. Here the equality sign is not to difficult to prove, but the upper bound is. Does this maybe bring any ideas to mind for somebody? I got stuck here and could really use some help!


Edited on June 1, 2016 $\quad$ I am still working on this problem and this is what I am at now. So obviously, I want to relate the problem to relevant graph matrices and in the specific case that $d := d_1 = d_2 = \cdots = d_M$ this is easy. Namely, we can write $W$ as:

$$W = I - \tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}} = I - \tilde{D}^{-1}L, \quad \text{with} \quad \tilde{D} = D + I.$$ In this specific case we simply have $\tilde{D}=(d+1)I$. In all other cases (arbitrary $d_i$), I hope to show that either: $$(i) \quad x^TWx \geq 1 - x^T\tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}}x,$$ or: $$(ii) \quad x^TWx \geq 1 - x^T\tilde{D}^{-1}Lx, \quad$$ for all $x$ with $\sum_{i=1}^Mx_i^2=1$ and $\sum_{i=1}^Mx_i = 0$. This equivalent to showing that either: $$(i) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i}{\sqrt{d_i+1}}-\frac{x_j}{\sqrt{d_j+1}}\right)^2 $$ or: $$(ii) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i^2-x_ix_j}{d_i+1}+\frac{x_j^2 - x_ix_j}{d_j+1}\right) $$ By the way, you are free to consider edges in $E$ as either $(i,j)$ or $(j,i)$, so you may assume w.l.o.g. that: $$\sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{d_i+1},$$ where $d_i\geq d_j$ for each edge. Unfortunately, element-wise comparison for both (i) and (ii) does not work for any $x$ that satisfies the constraints.

edit some plus and minus signs are corrected

$\endgroup$
1
  • $\begingroup$ By the way, in the alternative representation we are implicitly interested in the normalized eigenvector $x=v_M$, this would give the upper bound here. As all eigenvectors are orthogonal to the vector of ones $\mathbf{1}$, an additional restriction may be given by $$\sum_{i=1}^Mx_i=0$$. $\endgroup$
    – Koen
    May 28 '16 at 7:29
1
$\begingroup$

One way of obtaining a simple lower bound (strictly larger than $-1$) is the following: consider the Gershgorin circles $G_i$ given by $$G_i = \left\{z \in \mathbb{C} : |z - W_{ii}| \le R_i \right\}$$ where $R_i$ are the off-diagonal absolute row sums of $W$. Since the elements of $W$ are all non-negative, it follows that $$ R_i = \sum_{j \in \mathcal{N}_i} \frac{1}{\max\{d_i, d_j\} + 1} \le \sum_{j\in\mathcal{N}_i} \frac{1}{d_i + 1} = \frac{d_i}{d_i+1}.$$ Moreover $W_{ii} = 1 - R_i$ from which it follows that $$\lambda \in \bigcup_{i=1}^m [1 - 2R_i, 1] \subset \left[-\frac{d_\text{max} - 1}{d_\text{max} + 1}, 1\right].$$

This bound is not very sharp though. Consider for instance $d_1 =\ldots = d_m = m - 1$, then $W$ has eigenvalues $$\lambda_1 = 1, \lambda_2 = \ldots = \lambda_{m} = 0,$$ however the lower bound tends to $-1$ as $m$ gets larger.

$\endgroup$
0
$\begingroup$

Here is the relief to my question: It is (unfortunately for me) simply not true. As mentioned by Ronn3y, there is always a lower bound of $-\frac{d_\max-1}{d_\min+1}$ but there exists an example for which the the bound is sharp. Consider a complete bipartite graph with two sets of $d$ vertices (so each vertex has a common degree $d=d_\min=d_\max$), then the Metropolis-Hasting matrix is given by: \begin{equation} W = \frac{1}{d+1} \begin{bmatrix} I_d & J_d \\ J_d & I_d \end{bmatrix}, \end{equation} with $I_d, J_d \in \mathbb{R}^{d\times d}$; $I_d$ is the identity matrix and $J_d:=\mathbf{\mathbf{1}_d\mathbf{1}_d^T}$ is the matrix of ones ($\mathbf{1}_d \in \mathbb{R}^d$ is the vector of ones). Then we claim that $\lambda = -\frac{d-1}{d+1}$ is an eigenvalue; first we observe \begin{equation} W - \lambda I = \frac{1}{d+1} \begin{bmatrix} I_d & J_d \\ J_d & I_d \end{bmatrix} + \frac{d-1}{d+1} \begin{bmatrix} I_d & 0_d \\ 0_d & I_d \end{bmatrix} = \frac{1}{d+1} \begin{bmatrix} dI_d & J_d \\ J_d & dI_d \end{bmatrix}. \end{equation} It is straighforward to see that a corresponding eigenvector is given by: \begin{equation} v = \begin{bmatrix} \:\:\mathbf{1}_d \\ -\mathbf{1}_d \end{bmatrix}. \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.