What's $z$? ${}$

I'm inclined to think about it this way: you have $\pi_j=(E_j[\tau_j])^{-1}$, so given $\pi_1 \geq m$ you get $E_1[\tau_1] \leq 1/m$, hence $P_1(\tau_1 \geq n) \leq 1/mn$ by Markov's inequality. You could get such a lower bound on $\pi_1$ if you know $C'$ such that $\sum_{k \neq 1} \pi_k \leq C'<1$. Getting any better than $O(1/n)$ will require much more careful ergodicity analysis I think, because proving that will require you to demonstrate that Markov's inequality is far from tight, which means the tail distribution is "spread out" rather than concentrated near one point.

I assume you want smoothness in $x$, but do you intend $t>0$? Without $t>0$ you don't have good decay properties to force the sum to converge. Also, why should $\lambda_k$ be $O(k)$? Under "typical" circumstances it is $O(k^2)$.

@NikWeaver That's an interesting way to think about it. (I've also edited in the detail that my matrices have nonnegative real entries.)

@Dirk This is a good point. In fact the latter form is how my question came about in the first place; I expected that this permutation would be easier to manage because of the symmetry of $B$.

@CarloBeenakker The entrywise formula, i.e. $\frac{\sum_{i=1}^n \sum_{j=1}^n a_{ij} b_{ij}}{\sum_{i=1}^n a_{ii}}$, is not really good enough, because in my context $n$ is going to infinity. So I'm looking for something I can use to estimate this ratio in this situation.

OK, yes, I phrased it poorly. The point is that the chain itself has the selection probabilities and acceptance probabilities given. The algorithm computes $q_{ij}$ but this is truly just a function of $(i,j)$, even though it is generated only as needed instead of stored in advance. In other words to me the non-Markov feel is just that the algorithm "takes a shortcut": it would not look non-Markov if you precomputed $q_{ij}$ before running the algorithm. This would just be an absolutely awful thing to do in most situations (e.g. for the Ising model with Glauber dynamics).

I'm not sure why Metropolis is so surprising. You are given selection probabilities $p_{ij}$ and acceptance probabilities $q_{ij}$. You go from $i$ to $j$ with probability $p_{ij} q_{ij}$, and so you must go from $i$ to itself with probability $1-\sum_j p_{ij} q_{ij}$. Now the algorithm takes $p$ and the stationary distribution $\pi$ as given and cooks up $q$ such that $\pi_i p_{ij} q_{ij}=\pi_j p_{ji} q_{ji}$. Where is the "non-Markov" feel?