Upper bound on the magnitude of eigenvalue of a stochastic matrix

182 Views Asked by At

What is the upper bound for the magnitude of the second largest eigenvalue of the following square matrix $X$ of size $d\times d$?

The entries are given as:

  1. $X[0,0] = \alpha \in (0,1/d]$, $X[0, d-1] = (1-\alpha)$
  2. $X[i,i-1] = 1$ for all $i\in \{1,\dots, d-1\}$
  3. All other enteries are $0$.

I am interested in the case when $\alpha \sim 0$. Bounds uniformly over the state space $d >1$ is preferred.

Relation to a Markov Chain:
The above matrix is a transition matrix for the Markov chain (irreducible and aperiodic) with state $s\in \{0,\dots, d-1\}$.

From state $0$ with probability $\alpha$ the chain remains in state $0$, o/w it moves to state $d-1$.
For any other state $i > 0$, the chain moves to state $(i-1)$.

I am interested in the convergence rate of the Markov chain.