largest magnitude eigenvalue is 1 and has multiplicity 1, and the corresponding left eigenvector is the stationary distribution. We sort the eigenvalues λiin decreasing order of magnitude, so that 1 = λ1 > |λ2| > **· · ·** > |λs| for some 2 ≤ s ≤ n. It turns out that |λ2| determines the mixing time of the chain.

The following theorem shows that if 1 − β is small compared to 1 − |λ2|, the gradient approximation described above is accurate. Since we will be using the estimate as a direction in which to update the parameters, the theorem compares the *directions* of the gradient and its estimate. In this theorem, κ2(A) denotes the *spectral condition number* of a nonsingular matrix A, which is defined as the product of the *spectral norms* of the matrices A and A−1,

$$\kappa_{2}(A)=\|A\|_{2}\|A^{-1}\|_{2},$$

where

$$\|A\|_{2}=\operatorname*{max}_{x:\|x\|=1}\|A x\|,$$

and kxk denotes the Euclidean norm of the vector x.

Theorem 3. Suppose that the transition probability matrix P(θ) *satisfies Assumption 1 with stationary distribution* π
′ = (π1**, . . . , π**n), and has n *distinct eigenvalues. Let* S = (x1x2 **· · ·** xn) be the matrix of right eigenvectors of P *corresponding, in order, to the eigenvalues* 1 = λ1 > |λ2| ≥ · · · ≥ |λn|. Then the normalized inner product between ∇η and β∇βη *satisfies*

$$1-\frac{\nabla\eta\cdot\beta\nabla_{\!\!S}\eta}{\|\nabla\eta\|^{2}}\leq\kappa_{2}\left(\Pi^{1/2}S\right)\frac{\|\nabla(\sqrt{\pi}_{1},\ldots,\sqrt{\pi}_{n})\|}{\|\nabla\eta\|}\sqrt{r^{2}\Pi r}\frac{1-\beta}{1-\beta|\lambda_{2}|},\tag{27}$$  _where $\Pi=\text{diag}(\pi_{1},\ldots,\pi_{n})$._
Notice that r
′Πr is the expectation under the stationary distribution of r(X)
2.

As well as the mixing time (via |λ2|), the bound in the theorem depends on another parameter of the Markov chain: the spectral condition number of Π1/2S. If the Markov chain is reversible (which implies that the eigenvectors x1**, . . . , x**n are orthogonal), this is equal to the ratio of the maximum to the minimum probability of states under the stationary distribution. However, the eigenvectors do not need to be nearly orthogonal. In fact, the condition that the transition probability matrix have n distinct eigenvalues is not necessary; without it, the condition number is replaced by a more complicated expression involving spectral norms of matrices of the form (P − λiI).

Proof. The existence of n distinct eigenvalues implies that P can be expressed as SΛS
−1, where Λ = diag(λ1**, . . . , λ**n) (Lancaster & Tismenetsky, 1985, Theorem 4.10.2, p 153). It follows that for any polynomial f, we can write f(P) = Sf(Λ)S
−1.

Now, Proposition 1 shows that ∇η − β∇βη = ∇π

shows that $\nabla\eta-\beta\nabla_{\beta}\eta=\nabla\pi^{\prime}(1-\beta)J_{\beta}$. But  $$(1-\beta)J_{\beta}=(1-\beta)\left(r+\beta Pr+\beta^{2}P^{2}r+\cdots\right)$$ $$=(1-\beta)\left(I+\beta P+\beta^{2}P^{2}+\cdots\right)r$$ $$=(1-\beta)S\left(\sum_{t=0}^{\infty}\beta^{t}\Lambda^{t}\right)S^{-1}r$$ $$=(1-\beta)\sum_{j=1}^{n}x_{j}y_{j}^{\prime}\left(\sum_{t=0}^{\infty}(\beta\lambda_{j})^{t}\right)r,$$
$$331$$