a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})(\alpha+\beta
x)+\frac{\sigma_{x}^{2}(A+\theta
a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})^{2}}{2}(\iota+\gamma x)$
$\displaystyle+(\theta a_{1}+\frac{\sigma_{y}^{2}\theta^{2}b_{1}}{2})x+\theta
a_{3}+\frac{\sigma_{y}^{2}\theta^{2}b_{3}}{2}\bigg{\\}}$ $\displaystyle=$
$\displaystyle\exp\left\\{\left(\theta
a_{1}+\frac{\sigma_{y}^{2}\theta^{2}b_{1}}{2}+\beta(A+\theta
a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})+\frac{\gamma\sigma_{x}^{2}(A+\theta
a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})^{2}}{2}\right)x\right\\}$
$\displaystyle\times\exp\left\\{\left(\theta
a_{3}+\frac{\sigma_{y}^{2}\theta^{2}b_{3}}{2}+\alpha(A+\theta
a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})+\frac{\iota\sigma_{x}^{2}(A+\theta
a_{2}+\frac{\sigma_{y}^{2}\theta^{2}b_{2}}{2})^{2}}{2}\right)\right\\}$
$\displaystyle=$ $\displaystyle e^{\Lambda(\theta)+Ax}.$

###### Example 14.2

Consider a general regime-switching $AR(1)$ model:

$Y_{t+1}=\mu(X_{t+1})+\beta(X_{t+1})Y_{t}+\sigma(X_{t+1})\epsilon_{t+1},$

where $X_{t}$ is an aperiodic, irreducible and positive recurrent Markov chain
on a finite state space with transition matrix $P\in\mathbb{R}^{m\times m}$
and stationary distribution $\pi_{x}$, that is
$\pi_{x}^{\top}P=\pi_{x}^{\top}$. We use $P[x,]$ to denote the $x$-th row in
the transition matrix (which is a row vector). In addition,
$\epsilon_{t+1}\sim\mathcal{N}(0,1)$ and is independent of other variables.
Moreover, we denote ${\mu},\beta,{\sigma}^{2}$ by column vectors formed by
arranging $\mu(X),\beta(X),\sigma^{2}(X)$ accordingly.

First, under the joint stationary distribution $\pi$,
$\mathbb{E}_{\pi}[Y_{t+1}]=\pi_{x}^{\top}{\mu}+\pi_{x}^{\top}{\beta}\mathbb{E}_{\pi}[Y_{t+1}]$.
Hence the stationary mean for $Y$ is
$\mathbb{E}_{\pi}[Y_{1}]=\frac{\pi_{x}^{\top}{\mu}}{1-\pi_{x}^{\top}{\beta}}$.

Consider the Poisson equation

$g(x,y)-\mathbb{E}_{x,y}[g(X_{1},Y_{1})]=\mathbb{E}_{x,y}[Y_{1}]-\mathbb{E}_{\pi}[Y_{1}],$

where
$\mathbb{E}_{x,y}[Y_{1}]-\mathbb{E}_{\pi}[Y_{1}]=P[x,]({\mu}+{\beta}y)-\frac{\pi_{x}^{\top}{\mu}}{1-\pi_{x}^{\top}{\beta}}$,
where $P[x,]$ denotes the $x$-th row of the transition matrix.

We notice that the solution to the Poisson equation has the form of
$g(x,y)=\bar{g}(x)+A(x)y$, where as a vector, $A$ satisfies
$A-Pdiag\\{{\beta}\\}A=P{\beta}$, and $\bar{g}$ satisfies
$\bar{g}-P\bar{g}=P{\mu}-\frac{\pi_{x}^{\top}{\mu}}{1-\pi_{x}^{\top}{\beta}}+Pdiag\\{{\mu}\\}A$.
In particular, when $\beta$ is a constant that does not depend on $X$, then we
can verify that
$A=(\frac{\beta}{1-\beta},\cdots,\frac{\beta}{1-\beta})^{\top}$ is the
solution, in which case $A$ is also a constant that does not depend on $X$.

On the other hand, consider the eigenvalue problem:

$\mathbb{E}_{x,y}[e^{\theta Y_{1}}r(X_{1},Y_{1})]=e^{\Lambda(\theta)}r(x,y).$

When $\beta$ is a constant that does not depend on $X$, we realize that the
eigenfunction takes the form of
$r(x,y)=\bar{r}(x)e^{\frac{\theta\beta}{1-\beta}y}$, and $e^{\Lambda(\theta)}$
is the largest eigenvalue associated with the matrix
$Pdiag\\{\exp\\{\frac{\theta}{1-\beta}{\mu}+\frac{1}{2}\frac{\theta^{2}}{(1-\beta)^{2}}{\sigma}^{2}\\}\\}$,
and as a vector, $\bar{r}$ is the corresponding eigenvector. However, when
$\beta$ is not a constant, the eigenvalue problem cannot be easily solved.

##  15 Proofs

###  15.1 Proof of Lemma 3.2

We provide a detailed argument for interchanging the order between the
expectation and differentiation. To this end, we present the following variant
of the dominated convergence theorem:

###### Lemma 15.1

Let $f_{n},g_{n},h_{n}\in L^{1}$ such that $g_{n}\geq 0,h_{n}\geq 0$ almost
surely for all $n$. Suppose $f_{n}\to f_{\infty}$ almost surely, and
$|f_{n}|\leq g_{n}+h_{n}$. In addition, we assume $g_{n}\to g_{\infty}$ in
$L^{1}$ and almost surely, and $\mathbb{E}[h_{n}]\to 0$. Then $f_{n}\to
f_{\infty}$ in $L^{1}$.

Proof. By Fatou’s lemma,
$\mathbb{E}[|f_{\infty}|]\leq\liminf_{n\to\infty}\mathbb{E}[|f_{n}|]\leq\mathbb{E}[|g_{\infty}|]<\infty$,
hence $f_{\infty}\in L^{1}$.

Note that $|f_{n}-f_{\infty}|\leq g_{n}+h_{n}+|f_{\infty}|$, hence we apply
Fatou’s lemma again to $g_{n}+h_{n}+|f_{\infty}|-|f_{n}-f_{\infty}|\geq 0$ and
obtain

$\mathbb{E}\left[\liminf_{n\to\infty}\left(g_{n}+h_{n}+|f_{\infty}|-|f_{n}-f_{\infty}|\right)\right]\leq\liminf_{n\to\infty}\mathbb{E}[g_{n}+h_{n}+|f_{\infty}|-|f_{n}-f_{\infty}|].$

That is,

$\mathbb{E}\left[g_{\infty}+|f_{\infty}|+\liminf_{n\to\infty}h_{n}\right]\leq\mathbb{E}[g_{\infty}]+\mathbb{E}[|f_{\infty}|]-\limsup_{n\to\infty}\mathbb{E}[|f_{n}-f_{\infty}|].$

Therefore,
$\limsup_{n\to\infty}\mathbb{E}[|f_{n}-f_{\infty}|]+\mathbb{E}[\liminf_{n\to\infty}h_{n}]\leq
0$. This proves $\mathbb{E}[|f_{n}-f_{\infty}|]\to 0$, i.e., $f_{n}\to
f_{\infty}$ in $L^{1}$. $\hfill\Box$

The following moment estimate is also needed in the proof.

###### Lemma 15.2

Under Assumptions 3.1, 3.1, and 3.1, for a fixed $n$, the following statements
hold.

  1. (i)

When $\theta$ lies in the interior of $\Theta$ and sufficiently small,
$\mathbb{E}_{\nu}\left[e^{\theta^{\top}S_{n}}|S_{n}|^{q}\right]<\infty$ for
any $q\geq 0$.

  2. (ii)

We denote $\tilde{S}_{n}=\sum_{i=1}^{n}|X_{i}|$. For any $\ell$ sufficiently
small and any $q\geq 0$,
$\mathbb{E}_{\nu}[e^{\ell\tilde{S}_{n}}\tilde{S}_{n}^{q}]<\infty$.

  3. (iii)

When $\theta$ lies in the interior of $\Theta$ and $\theta,\eta$ sufficiently
small,
$\mathbb{E}_{\nu}\left[e^{\theta^{\top}S_{n}+\ell\tilde{S}_{n}}\left(|S_{n}|^{q}+\tilde{S}_{n}^{p}\right)\right]<\infty$
for any $p,q\geq 0$.

Proof.

  1. (i)

When the additive part does not degenerate, by Proposition 1(i) in Fuh (2004),
under Assumptions 3.1 and 3.1, and when $\theta$ is sufficiently small,
$\mathbb{E}_{\nu}\left[e^{|\theta||S_{n}|}\right]<\infty$. Hence
$\mathbb{P}_{\nu}(|S_{n}|>t)\leq\mathbb{E}_{\nu}\left[e^{|\theta||S_{n}|}\right]e^{-|\theta|t}$.
Then for any $q>0$,

$\mathbb{E}_{\nu}[|S_{n}|^{q}]=\int_{0}^{\infty}qt^{q-1}\mathbb{P}_{\nu}(|S_{n}|>t)\mathrm{d}t\leq
q\mathbb{E}_{\nu}\left[e^{|\theta||S_{n}|}\right]\int_{0}^{\infty}t^{q-1}e^{-|\theta|t}\mathrm{d}t<\infty.$

Since $\theta$ lies in the interior of $\Theta$, there exists $v>1$ such that
$v\theta\in\Theta$ and
$\mathbb{E}_{\nu}\left[e^{v|\theta||S_{n}|}\right]<\infty$. By Hölder’s
inequality,

$\mathbb{E}_{\nu}\left[e^{\theta^{\top}S_{n}}|S_{n}|^{q}\right]\leq\left(\mathbb{E}_{\nu}\left[e^{v|\theta||S_{n}|}\right]\right)^{1/v}\left(\mathbb{E}_{\nu}\left[|S_{n}|^{qu}\right]\right)^{1/u}<\infty,$

where $\frac{1}{v}+\frac{1}{u}=1$.

When the additive part degenerates, it reduces to $(ii)$.

  2. (ii)

We only need to prove the case when $\mathcal{X}$ is unbounded. When
$\ell<\frac{L}{1+C_{0}+\cdots+C_{0}^{n}}$, by Assumption 3.1(iv), we have

$\mathbb{E}_{\nu}\left[e^{\ell\tilde{S}_{n}}\right]=\mathbb{E}_{\nu}\left[e^{\ell\tilde{S}_{n-1}}\mathbb{E}_{\nu}\left[e^{\ell|X_{n}|}\Big{|}\mathcal{F}_{n-1}\right]\right]\leq
e^{C_{0}\ell}\mathbb{E}_{\nu}\left[e^{\ell\tilde{S}_{n-2}+(\ell+C_{0}\ell)|X_{n-1}|}\right]\leq\cdots\leq
e^{C}\mathbb{E}_{\nu}\left[e^{\ell(1+C_{0}+\cdots+C_{0}^{n})|X_{0}|}\right],$

for some finite constant $C$. Hence
$\mathbb{E}_{\nu}\left[e^{\ell\tilde{S}_{n}}\right]<\infty$ for any $\ell$
sufficiently small. Moreover, for any $q>0$, for the same reason,
$\mathbb{E}[\tilde{S}_{n}^{q}]<\infty$. Finally,
$\mathbb{E}_{\nu}[e^{\ell\tilde{S}_{n}}\tilde{S}_{n}^{q}]<\infty$ follows by
Hölder’s inequality.

  3. (iii)

The conclusion follows from (i) and (ii) by Hölder’s inequality.

$\hfill\Box$

#### Fixed-time events

We first consider the case of a finite-state Markov random walk.

$G(\theta,\eta)=\mathbb{E}_{\nu}[\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}].$

Fix a sufficiently small $\delta>0$, such that
$\\{(\theta^{\prime},\eta^{\prime}):|\theta^{\prime}-\theta|+|\eta^{\prime}-\eta|<2\delta\\}\subset\Theta\times
H$. Because $X_{i}$ only takes finite many values, we denote

$\displaystyle C_{\delta}=$
$\displaystyle\sup_{x,x^{\prime},|\theta^{\prime}-\theta|<\delta}|\frac{\partial}{\partial\theta}\psi(x,x^{\prime},\theta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\frac{\partial}{\partial\eta}k(x,x^{\prime},\eta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\frac{\partial}{\partial\eta}\phi(x,x^{\prime},\eta^{\prime})|$
$\displaystyle\vee\sup_{x,x^{\prime},|\theta^{\prime}-\theta|<\delta}|\psi(x,x^{\prime},\theta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|k(x,x^{\prime},\eta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\phi(x,x^{\prime},\eta^{\prime})|.$

We have

$\displaystyle\left|\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)\right|$
$\displaystyle\leq$ $\displaystyle nC_{\delta}(2|\Delta\eta|+|\Delta\theta|).$

We consider the case where
$|\Delta\theta|\vee|\Delta\eta|<\frac{1}{4nC_{\delta}}\wedge\delta$. The
difference has an estimate:

$\displaystyle\Big{|}\mathbbm{1}_{\\{S_{n}>c\\}}e^{-(\theta+\Delta\theta)S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta^{\top}S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}$
$\displaystyle\times\bigg{\\{}\left|e^{-\Delta\theta
S_{n}}-1\right|e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}$
$\displaystyle+\left|e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}-1\right|\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+3nC_{\delta}}\bigg{\\{}\mathbbm{1}_{\\{|\Delta\theta||S_{n}|\leq
1\\}}C|\Delta\theta||S_{n}|+\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-\Delta\theta
S_{n}}+1\right]+nCC_{\delta}(2|\Delta\eta|+|\Delta\theta|)\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
S_{n}}\left(|S_{n}|+1\right)(|\Delta\theta|+|\Delta\eta|)+\tilde{C}\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-(\theta+\Delta\theta)S_{n}}+e^{-\theta
S_{n}}\right].$

Hence

$\displaystyle\frac{1}{|\Delta\theta|+|\Delta\eta|}\Big{|}\mathbbm{1}_{\\{S_{n}>c\\}}e^{-(\theta+\Delta\theta)S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
(31)
$\displaystyle-\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta^{\top}S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
S_{n}}\left(|S_{n}|+1\right)+\frac{\tilde{C}}{|\Delta\theta|}\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-(\theta+\Delta\theta)S_{n}}+e^{-\theta
S_{n}}\right].$

To analyze (31), we first note that under Assumptions 3.1, 3.1, and 3.1, Lemma
15.2 holds, then $\mathbb{E}[e^{-\theta S_{n}}\left(|S_{n}|+1\right)]<\infty$.
Next we need to show that
$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-(\theta+\Delta\theta)S_{n}}+e^{-\theta
S_{n}}\right]\right]\to 0$ as $\Delta\theta\to 0$.

Here we have

$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}e^{-\theta
S_{n}}\right]\leq\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}|S_{n}|e^{-\theta
S_{n}}\right]\to 0$

due to $\mathbb{E}[e^{-\theta S_{n}}|S_{n}|]<\infty$ and the monotone
convergence theorem.

The last term requires to estimate the probability
$\mathbb{P}\left(|S_{n}|>\frac{1}{|\Delta\theta|}\right)$. Under Assumptions
3.1, 3.1, and 3.1, from the proof of Lemma 15.2, it is known that
$\mathbb{P}\left(|S_{n}|>\frac{1}{|\Delta\theta|}\right)\approx
e^{-\frac{Kn}{|\Delta\theta|}}$ for some $K>0$. Then by the Hölder’s
inequality,

$\displaystyle\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|S_{n}|>\frac{1}{|\Delta\theta|}\\}}e^{-(\theta+\Delta\theta)S_{n}}\right]\leq$
$\displaystyle\frac{1}{|\Delta\theta|}\left(\mathbb{P}\left(|S_{n}|>\frac{1}{|\Delta\theta|}\right)\right)^{1/q}\left(\mathbb{E}\left[e^{-p(\theta+\Delta\theta)S_{n}}\right]\right)^{1/p},$

where $\frac{1}{p}+\frac{1}{q}=1$. We may pick $p>1$ but sufficiently close to
1 such that $-p(\theta+\Delta\theta)\in\Theta$ for any
$|\Delta\theta|<\delta$. Hence
$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}e^{-(\theta+\Delta\theta)S_{n}}\right]\to
0$ as $\Delta\theta\to 0$.

When the state space of the underlying Markov chain is unbounded, we have
Assumption 3.1 $(iii)$ on the growth condition.

Note that on the event
$\\{\tilde{S}_{n}\leq\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}$,
we have

$\displaystyle\left|-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)\right|$
$\displaystyle\leq$ $\displaystyle
3C_{\delta}(n+2\tilde{S}_{n})(|\Delta\theta|\vee|\Delta\eta|)\leq
3nC_{\delta}(|\Delta\theta|\vee|\Delta\eta|)+6C_{\delta}\tilde{S}_{n}(|\Delta\theta|\vee|\Delta\eta|)\leq
1.$

We consider the similar estimate on the difference:

$\displaystyle\Big{|}\mathbbm{1}_{\\{S_{n}>c\\}}e^{-(\theta+\Delta\theta)S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta^{\top}S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}$
$\displaystyle\times\bigg{\\{}\left|e^{-\Delta\theta
S_{n}}-1\right|e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}$
$\displaystyle+\left|e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}-1\right|\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+3nC_{\delta}+6C_{\delta}\tilde{S}_{n}}\bigg{\\{}\mathbbm{1}_{\\{|\Delta\theta||S_{n}|\leq
1\\}}C|\Delta\theta||S_{n}|+\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-\Delta\theta
S_{n}}+1\right]\bigg{\\}}$
$\displaystyle+\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}+\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\mathbbm{1}_{\\{\tilde{S}_{n}\leq\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}3CC_{\delta}(n+2\tilde{S}_{n})(|\Delta\theta|+|\Delta\eta|)$
$\displaystyle+\mathbbm{1}_{\\{S_{n}>c\\}}e^{-\theta
S_{n}}\mathbbm{1}_{\\{\tilde{S}_{n}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}\Big{|}e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
S_{n}+6C_{\delta}\tilde{S}_{n}}\left(|S_{n}|+\tilde{S}_{n}+1\right)(|\Delta\theta|+|\Delta\eta|)+\tilde{C}\mathbbm{1}_{\\{|\Delta\theta||S_{n}|>1\\}}\left[e^{-(\theta+\Delta\theta)S_{n}}+e^{-\theta
S_{n}}\right]e^{6C_{\delta}\tilde{S}_{n}}$
$\displaystyle+\tilde{C}\mathbbm{1}_{\\{\tilde{S}_{n}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
S_{n}}e^{6C_{\delta}\tilde{S}_{n}}.$

It suffices to show

$\mathbb{E}\left[e^{-\theta
S_{n}+6C_{\delta}\tilde{S}_{n}}\left(|S_{n}|+\tilde{S}_{n}+1\right)\right]<\infty,$

and when $|\Delta\theta|,|\Delta\eta|\to 0$,

$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|S_{n}|>\frac{1}{|\Delta\theta|}\\}}\left[e^{-(\theta+\Delta\theta)S_{n}}+e^{-\theta
S_{n}}\right]e^{6C_{\delta}\tilde{S}_{n}}\right]\to 0,\
\frac{1}{|\Delta\theta|+|\Delta\eta|}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{n}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
S_{n}}e^{6C_{\delta}\tilde{S}_{n}}\right]\to 0.$

The first expectation is finite due to the Hölder’s inequality and Lemma 15.2.
The second limit holds by the same argument for the finite state-space case.
The last limit holds because

$\frac{1}{|\Delta\theta|+|\Delta\eta|}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{n}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
S_{n}}e^{6C_{\delta}\tilde{S}_{n}}\right]\leq
24C_{\delta}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{n}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}\tilde{S}_{n}e^{-\theta
S_{n}}e^{6C_{\delta}\tilde{S}_{n}}\right]\to 0$

by the monotone convergence theorem and the fact
$\mathbb{E}\left[\tilde{S}_{n}e^{-\theta
S_{n}}e^{6C_{\delta}\tilde{S}_{n}}\right]<\infty$.

#### First-passage-time events

To make the derivation transparent, we first consider the i.i.d. case. Note
that for given $\mu>0$, the second moment has the form

$G(\theta)=\mathbb{E}[\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
S_{\tau_{b}}+\tau_{b}\psi(\theta)}]=\mathbb{E}[\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}]e^{-\theta b},$

where $R(b)=S_{\tau_{b}}-b$ is the overshoot.

Define $\tilde{G}(\theta)=\mathbb{E}[\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}]$. It suffices to show

$\tilde{G}^{\prime}(\theta)=\mathbb{E}\left[\left(-R(b)+\tau_{b}\psi^{\prime}(\theta)\right)\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\right],$

for each $\theta$ such that $\theta,-\theta\in\Theta$.

For a given constant $C_{1}>0$, we consider $\delta>0$ such that for any
$\theta^{\prime}\in B_{\delta}(\theta)$,
$|\psi(\theta^{\prime})-\psi(\theta)|\leq C_{1}|\theta^{\prime}-\theta|$, and
$|\psi(\theta^{\prime})|<C_{1}|\psi(\theta)|$.

Assume $|\Delta\theta|<\delta$, and consider the difference

$\displaystyle\frac{1}{|\Delta\theta|}\left|\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-(\theta+\Delta\theta)R(b)+\tau_{b}\psi(\theta+\Delta\theta)}-\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\right|$ $\displaystyle\leq$
$\displaystyle\frac{1}{|\Delta\theta|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\left|e^{-\Delta\theta
R(b)}e^{\tau_{b}[\psi(\theta+\Delta\theta)-\psi(\theta)]}-1\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{|\Delta\theta|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\left\\{\left|\left(e^{-\Delta\theta
R(b)}-1\right)e^{\tau_{b}[\psi(\theta+\Delta\theta)-\psi(\theta)]}\right|+\left|e^{\tau_{b}[\psi(\theta+\Delta\theta)-\psi(\theta)]}-1\right|\right\\}$
$\displaystyle\leq$
$\displaystyle\frac{1}{|\Delta\theta|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\left\\{\left|e^{-\Delta\theta
R(b)}-1\right|e^{C_{1}|\Delta\theta|}+\left|e^{\tau_{b}[\psi(\theta+\Delta\theta)-\psi(\theta)]}-1\right|\right\\}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\mathbbm{1}_{\\{|\Delta\theta R(b)|\leq 1,\
\tau_{b}C_{1}|\Delta\theta|\leq
1\\}}\left\\{R(b)e^{C_{1}\delta}+CC_{1}\tau_{b}\right\\}$
$\displaystyle+\frac{1}{|\Delta\theta|}\mathbbm{1}_{\\{\tau_{b}<T\\}}\mathbbm{1}_{\\{|\Delta\theta
R(b)|>1,\text{ or
}\tau_{b}C_{1}|\Delta\theta|>1\\}}\left|e^{-(\theta+\Delta\theta)R(b)+\tau_{b}\psi(\theta+\Delta\theta)}+e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\right|$ $\displaystyle\leq$
$\displaystyle\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\left\\{R(b)e^{C_{1}\delta}+CC_{1}\tau_{b}\right\\}$
$\displaystyle+\mathbbm{1}_{\\{|\Delta\theta R(b)|>1,\text{ or
}\tau_{b}C_{1}|\Delta\theta|>1\\}}\mathbbm{1}_{\\{\tau_{b}<T\\}}\frac{\left|e^{-(\theta+\Delta\theta)R(b)+\tau_{b}\psi(\theta+\Delta\theta)}+e^{-\theta
R(b)+\tau_{b}\psi(\theta)}\right|}{|\Delta\theta|}$ $\displaystyle\leq$
$\displaystyle\tilde{C}e^{-\theta
R(b)}\left[R(b)+1\right]+\tilde{C}\mathbbm{1}_{\\{|\Delta\theta R(b)|>1,\text{
or
}\tau_{b}C_{1}|\Delta\theta|>1\\}}\frac{\left|e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right|}{|\Delta\theta|}.$

It suffices to prove $\mathbb{E}\left[e^{-\theta R(b)}[R(b)+1]\right]<\infty$,
and $\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta R(b)|>1,\text{ or
}\tau_{b}C_{1}|\Delta\theta|>1\\}}\frac{\left|e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right|}{|\Delta\theta|}\right]\to 0$ as $\Delta\theta\to 0$. For the
latter, we also need to estimate the probability

$\displaystyle\mathbb{P}\left(|\Delta\theta R(b)|>1,\text{ or
}\tau_{b}C_{1}|\Delta\theta|>1\right)$ $\displaystyle=$
$\displaystyle\mathbb{P}\left(R(b)>\frac{1}{|\Delta\theta|},\text{ or
}\tau_{b}>\frac{1}{C_{1}|\Delta\theta|}\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(R(b)>\frac{1}{|\Delta\theta|}\right)+\mathbb{P}\left(\tau_{b}>\frac{1}{C_{1}|\Delta\theta|}\right)$
$\displaystyle\leq$
$\displaystyle|\Delta\theta|^{2}\left(\mathbb{E}[R(b)^{2}+C_{1}^{2}\tau_{b}^{2}]\right).$

Next, we consider the case of a finite-state Markov random walk. For given
$\mu>0$,

$\displaystyle G(\theta,\eta)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\nu}[\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
S_{\tau_{b}}+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\nu}[\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}]e^{-\theta
b}.$

Fix a sufficiently small $\delta>0$, such that
$\\{(\theta^{\prime},\eta^{\prime}):|\theta^{\prime}-\theta|+|\eta^{\prime}-\eta|<2\delta\\}\subset\Theta\times
H$. Because $X_{i}$ only takes finite many values, we denote

$\displaystyle C_{\delta}=$
$\displaystyle\sup_{x,x^{\prime},|\theta^{\prime}-\theta|<\delta}|\frac{\partial}{\partial\theta}\psi(x,x^{\prime},\theta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\frac{\partial}{\partial\eta}k(x,x^{\prime},\eta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\frac{\partial}{\partial\eta}\phi(x,x^{\prime},\eta^{\prime})|$
$\displaystyle\vee\sup_{x,x^{\prime},|\theta^{\prime}-\theta|<\delta}|\psi(x,x^{\prime},\theta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|k(x,x^{\prime},\eta^{\prime})|\vee\sup_{x,x^{\prime},|\eta^{\prime}-\eta|<\delta}|\phi(x,x^{\prime},\eta^{\prime})|.$

On the event $\\{\tau_{b}<T\\}$, we have

$\displaystyle\bigg{|}\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)$
$\displaystyle~{}-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)\bigg{|}\leq
TC_{\delta}(2|\Delta\eta|+|\Delta\theta|).$

We consider the case where
$|\Delta\theta|\vee|\Delta\eta|<\frac{1}{4TC_{\delta}}\wedge\delta$. The
difference has an estimate:

$\displaystyle\Big{|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-(\theta+\Delta\theta)R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta^{\top}R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{\tau_{b}<c\\}}e^{-\theta
R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}$
$\displaystyle\times\bigg{\\{}\left|e^{-\Delta\theta
R(b)}-1\right|e^{\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}$
$\displaystyle+\left|e^{\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}-1\right|\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+3TC_{\delta}}\bigg{\\{}\mathbbm{1}_{\\{|\Delta\theta|R(b)\leq
1\\}}C|\Delta\theta|R(b)+\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-\Delta\theta
R(b)}+1\right]+TCC_{\delta}(2|\Delta\eta|+|\Delta\theta|)\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
R(b)}\left(R(b)+1\right)(|\Delta\theta|+|\Delta\eta|)+\tilde{C}\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right].$

Hence

$\displaystyle\frac{1}{|\Delta\theta|+|\Delta\eta|}\Big{|}\Big{|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-(\theta+\Delta\theta)R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
(32) $\displaystyle-\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
R(b)}\left(R(b)+1\right)+\frac{\tilde{C}}{|\Delta\theta|}\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right].$

To analyze (32), we first note that under Assumptions 3.1, 3.1, and 3.1, by
Lemma 2 in Fuh (2004), we have $\sup_{b\geq 0}E_{\pi}R(b)\leq
E_{\pi}(S_{1}^{+})^{2}/E_{\pi}S_{1},$ which implies that
$\mathbb{E}[e^{-\theta R(b)}\left(R(b)+1\right)]<\infty$. Next, we will
analyze the second term in (32). By Markov inequality, we have
$\frac{1}{|\Delta\theta|}\mathbb{P}\left(R(b)>\frac{1}{|\Delta\theta|}\right)\leq
E_{\pi}R(b)<\infty$, via Lemma 2 in Fuh (2004). Applying Hölder’s inequality,
we have, under Assumptions 3.1, 3.1, and 3.1, for $\theta>0$,
$\Delta\theta>0$,
$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right]\right]\to 0$ as $\Delta\theta\to 0$.

When the state space of the underlying Markov chain is unbounded, we have
Assumption 3.1 $(iii)$ on the growth condition.

Note that on the event $\\{\tau_{b}<T,\
\tilde{S}_{T}\leq\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}$, we
have

$\displaystyle\sum_{i=1}^{\tau_{b}}\left|-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)\right|$
$\displaystyle\leq$ $\displaystyle
3C_{\delta}(T+2\tilde{S}_{T})(|\Delta\theta|\vee|\Delta\eta|)\leq
3TC_{\delta}(|\Delta\theta|\vee|\Delta\eta|)+6C_{\delta}\tilde{S}_{T}(|\Delta\theta|\vee|\Delta\eta|)\leq
1.$

The difference can be bounded by

$\displaystyle\Big{|}\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-(\theta+\Delta\theta)R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta^{\top}R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{\tau_{b}<c\\}}e^{-\theta
R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}$
$\displaystyle\times\bigg{\\{}\left|e^{-\Delta\theta
R(b)}-1\right|e^{\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}$
$\displaystyle+\left|e^{\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)}-1\right|\bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+3TC_{\delta}+6C_{\delta}\tilde{S}_{T}}\bigg{\\{}\mathbbm{1}_{\\{|\Delta\theta|R(b)\leq
1\\}}|\Delta\theta|R(b)+\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-\Delta\theta
R(b)}+1\right]\bigg{\\}}$
$\displaystyle+\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)+\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\mathbbm{1}_{\\{\tilde{S}_{T}\leq\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}3CC_{\delta}(T+2\tilde{S}_{T})(|\Delta\theta|+|\Delta\eta|)$
$\displaystyle+\mathbbm{1}_{\\{\tau_{b}<T\\}}e^{-\theta
R(b)}\mathbbm{1}_{\\{\tilde{S}_{T}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}\Big{|}e^{\sum_{i=1}^{\tau_{b}}-k(X_{i-1},X_{i},\eta+\Delta\eta)+\psi(X_{i-1},X_{i},\theta+\Delta\theta)+\phi(X_{i-1},\eta+\Delta\eta)}$
$\displaystyle-e^{\sum_{i=1}^{n}-k(X_{i-1},X_{i},\eta)+\psi(X_{i-1},X_{i},\theta)+\phi(X_{i-1},\eta)}\Big{|}$
$\displaystyle\leq$ $\displaystyle\tilde{C}e^{-\theta
R(b)+6C_{\delta}\tilde{S}_{T}}\left(\tilde{S}_{T}+R(b)+1\right)(|\Delta\theta|+|\Delta\eta|)+\tilde{C}\mathbbm{1}_{\\{|\Delta\theta|R(b)>1\\}}\left[e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right]e^{6C_{\delta}\tilde{S}_{T}}$
$\displaystyle+\tilde{C}\mathbbm{1}_{\\{\tilde{S}_{T}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
R(b)+6C_{\delta}\tilde{S}_{T}}.$

It suffices to show

$\mathbb{E}\left[e^{-\theta
R(b)+6C_{\delta}\tilde{S}_{T}}\left(R(b)+\tilde{S}_{T}+1\right)\right]<\infty,$

and when $|\Delta\theta|,|\Delta\eta|\to 0$,

$\frac{1}{|\Delta\theta|}\mathbb{E}\left[\mathbbm{1}_{\\{R(b)>\frac{1}{|\Delta\theta|}\\}}\left[e^{-(\theta+\Delta\theta)R(b)}+e^{-\theta
R(b)}\right]e^{6C_{\delta}\tilde{S}_{T}}\right]\to 0,\
\frac{1}{|\Delta\theta|+|\Delta\eta|}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{T}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
R(b)}e^{6C_{\delta}\tilde{S}_{T}}\right]\to 0.$

The first two conditions hold due to the same argument as above and the
Hölder’s inequality.

The last limit holds because

$\frac{1}{|\Delta\theta|+|\Delta\eta|}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{T}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}e^{-\theta
R(b)}e^{6C_{\delta}\tilde{S}_{T}}\right]\leq
24C_{\delta}\mathbb{E}\left[\mathbbm{1}_{\\{\tilde{S}_{T}>\frac{1}{24C_{\delta}(|\Delta\theta|+|\Delta\eta|)}\\}}\tilde{S}_{T}e^{-\theta
R(b)}e^{6C_{\delta}\tilde{S}_{T}}\right]\to 0$

by the monotone convergence theorem and the fact
$\mathbb{E}\left[\tilde{S}_{T}e^{-\theta
R(b)}e^{6C_{\delta}\tilde{S}_{T}}\right]<\infty$, by Lemma 15.2.

###  15.2 Proof of Theorem 3.1

Under Assumption 3.1, $r(x;\alpha)$ is non-zero and well-defined.

Recall that $\\{(X_{n},S_{n}),n\geq 0\\}$ is a Markov chain, for any classical
exponential tilting probability $\mathbb{P}_{\theta^{*}}$, the transition
probability is given by (6). Moreover, based on the definition of the
eigenvalue and eigenfunction in (4), we have

$e^{\Lambda(\theta^{*})}r(x,\theta^{*})=\mathbb{E}_{x}[e^{{\theta^{*}}^{\top}Y_{1}}r(X_{1},\theta^{*})]=\mathbb{E}_{x}\big{[}r(X_{1},\theta^{*})\mathbb{E}_{x}[e^{{\theta^{*}}^{\top}Y_{1}}|X_{1}]\big{]}=\mathbb{E}_{x}[r(X_{1},\theta^{*})e^{\psi(x,X_{1},\theta^{*})}].$

With $k(x,x^{\prime},\eta)=\psi(x,x^{\prime},\eta)+\log r(x^{\prime},\eta)$,
let us compute

$\phi(x,\eta)=\log\mathbb{E}_{x}[e^{\psi(x,X_{1},\eta)+\log
r(X_{1},\eta)}]=\Lambda(\eta)+\log r(x,\eta).$

Therefore, the transition probability $\mathbb{P}_{\theta,\eta}$ defined in
(9), with $\theta=\eta=\theta^{*}$, is

$\displaystyle\mathbb{P}_{\theta^{*},\theta^{*}}(\mathrm{d}x^{\prime},\mathrm{d}s^{\prime}|x,s)=e^{\log
r(X_{1},\theta^{*})+\theta^{\top}(s^{\prime}-s)-\Lambda(\theta^{*})-\log
r(x,\theta^{*})}p(x,\mathrm{d}x^{\prime})\rho(s^{\prime}-s|x,x^{\prime})\mathrm{d}s^{\prime}.$

This coincides with (6). $\hfill\Box$

###  15.3 Proof of Corollary 3.4

Here, we consider the affine model and directly verify the proposed forms are
the eigenvalues and the associated eigenfunction. Hence only Assumption 3.1 is
required.

Under the affine structure, $r(x,\theta)=A(\theta)^{\top}x$ is an
eigenfunction if and only if

$\displaystyle
E_{x}[e^{\theta^{\top}Y_{1}}r(X_{1},\theta)]=\mathbb{E}_{x}\big{[}r(X_{1},\theta)\mathbb{E}_{x}[e^{\theta^{\top}Y_{1}}|X_{1}]\big{]}=\mathbb{E}[e^{A(\theta)^{\top}X_{1}+D_{0}(\theta)^{\top}X_{1}+D_{1}(\theta)^{\top}x+D_{2}(\theta)}]$
$\displaystyle=$ $\displaystyle
e^{\big{[}C_{1}\big{(}A(\theta)+D_{0}(\theta)\big{)}+D_{1}(\theta)\big{]}^{\top}x+C_{2}\big{(}A(\theta)+D_{0}(\theta)\big{)}+D_{2}(\theta)}=e^{\Lambda(\theta)}e^{A(\theta)^{\top}x}.$

This is equivalent to
$C_{1}\big{(}A(\theta)+D_{0}(\theta)\big{)}+D_{1}(\theta)=A(\theta)$ and
$C_{2}\big{(}A(\theta)+D_{0}(\theta)\big{)}+D_{2}(\theta)=\Lambda(\theta)$.
For any given $\theta$, $D_{0}(\theta),D_{1}(\theta),D_{2}(\theta)$ are three
constants, and $C_{1}(\cdot),C_{2}(\cdot)$ are two functions. Solving this
system of algebraic equations leads to the eigenfunction and eigenvalue.

Moreover, in this case, the classical exponential tilting family is

$\mathbb{P}_{\theta}(\mathrm{d}x^{\prime},\mathrm{d}s^{\prime}|x,s)=e^{A(\theta)^{\top}(x^{\prime}-x)-\Lambda(\theta)+\theta^{\top}(s^{\prime}-s)}p(x,\mathrm{d}x^{\prime})\rho(s^{\prime}-s|x,x^{\prime})\mathrm{d}s^{\prime}.$

On the other hand, the duo-exponential tilting distribution with link function
$k(x,x^{\prime},\eta)=\eta^{\top}x^{\prime}$ is

$\mathbb{P}_{\theta,\eta}(\mathrm{d}x^{\prime},\mathrm{d}s^{\prime}|x,s)=e^{\eta^{\top}x^{\prime}+\theta^{\top}(s^{\prime}-s)-C_{1}(\eta)^{\top}x-C_{2}(\eta)-D_{0}(\theta)^{\top}x^{\prime}-D_{1}(\theta)^{\top}x-D_{2}(\theta)}p(x,\mathrm{d}x^{\prime})\rho(s^{\prime}-s|x,x^{\prime})\mathrm{d}s^{\prime}.$

By direct comparison, we could see that when $\eta=A(\theta)+D_{0}(\theta)$,
probability
$\mathbb{P}_{\theta,\eta}(\mathrm{d}x^{\prime},\mathrm{d}s^{\prime}|x,s)$
coincides with
$\mathbb{P}_{\theta}(\mathrm{d}x^{\prime},\mathrm{d}s^{\prime}|x,s)$.
Therefore, the proposed duo-exponential tilting family contains the classical
exponential tilting as a proper subset. $\hfill\Box$

###  15.4 Proof of Lemma 3.3

First, under Assumption 3.1, we claim $\psi(x,x^{\prime},\theta)$ and
$\phi(x,\eta)$ are convex functions of $\theta$ and $\eta$, respectively, and
hence $\Theta$ and $H$ are both convex sets. This is a well-known result for
cumulant generating functions. For example, it can be proved by Hölder’s
inequality: for given $\iota>0$

$\displaystyle e^{\phi(x,\iota\eta_{1}+(1-\iota)\eta_{2})}=$
$\displaystyle\mathbb{E}_{x}[e^{(\iota\eta_{1}+(1-\iota)\eta_{2})^{\top}\tilde{k}(x,X_{1})}]=\mathbb{E}_{x}[(e^{\eta_{1}^{\top}\tilde{k}(x,X_{1})})^{\iota}(e^{\eta_{2}^{\top}\tilde{k}(x,X_{1})})^{1-\iota}]$
$\displaystyle\leq$
$\displaystyle\big{(}\mathbb{E}_{x}[e^{\eta_{1}^{\top}\tilde{k}(x,X_{1})}]\big{)}^{\iota}\big{(}\mathbb{E}_{x}[e^{\eta_{2}^{\top}\tilde{k}(x,X_{1})}]\big{)}^{1-\iota}=e^{\iota\phi(x,\eta_{1})+(1-\iota)\phi(x,\eta_{2})}.$

Hence
$\phi\big{(}\iota\eta_{1}+(1-\iota)\eta_{2},x\big{)}\leq\iota\phi(x,\eta_{1})+(1-\iota)\phi(x,\eta_{2})$.
That is, $\phi$ is convex in $\eta$.

Therefore, inside the expectation, for any trajectory,
$F(X_{\tau},S_{\tau})\exp\\{-\theta^{\top}S_{\tau}+\sum_{i=1}^{\tau}-\eta^{\top}\tilde{k}(X_{i-1},X_{i})+\phi(X_{i-1},\eta)+\psi(X_{i-1},X_{i},\eta)\\}$
is a composition between exponential function and a convex function and hence
remains convex in terms of $(\theta,\eta)$. After taking the expectation,
$G(\theta,\eta)$ is also convex. $\hfill\Box$

###  15.5 Proof of Theorem 4.4

We first present a lemma about the optimal log-likelihood ratio for a joint
normal distribution.

###### Lemma 15.3

Under the LAN family and asymptotic normal regime, the second moment of the
Monte-Carlo estimator (10) is asymptotically equivalent to
$\mathbb{E}[\bar{F}^{2}(N)e^{-N_{\tilde{\mathbb{P}}}}]$, where
$(N,N_{\tilde{\mathbb{P}}})$ follows a joint normal distribution. Suppose

$\begin{pmatrix}N\\\
N_{\tilde{\mathbb{P}}}\end{pmatrix}\sim\mathcal{N}\bigg{(}\begin{pmatrix}\mu_{N}\\\
\mu_{\tilde{\mathbb{P}}}\end{pmatrix},\begin{pmatrix}\Sigma_{N}&\Sigma_{LN}^{\top}\\\
\Sigma_{LN}&\sigma^{2}_{{\tilde{\mathbb{P}}}}\end{pmatrix}\bigg{)}.$

Then the minimum of $\mathbb{E}[\bar{F}^{2}(N)e^{-N_{\tilde{\mathbb{P}}}}]$ is
achieved when
$\sigma^{2}_{\tilde{\mathbb{P}}}=\Sigma_{LN}^{\top}\Sigma_{N}^{-1}\Sigma_{LN}$.

Proof. First, we note that under the LAN family assumption of the likelihood
ratio and asymptotic normality of the statistic of interest
$\bar{F}^{2}(S_{\tau})$, by using a standard joint central limit theorem, we
have that the second moment of the Monte-Carlo estimator (10) is
asymptotically equivalent to
$\mathbb{E}[\bar{F}^{2}(N)e^{-N_{\tilde{\mathbb{P}}}}]$. (3.6) and (3.7) in
Fuh and Hu (2007) presents the simple case in finite state Markov chains.
Second, since $N_{\tilde{\mathbb{P}}}$ is the limit of a log-likelihood ratio,
$\mathbb{E}[e^{N_{\tilde{\mathbb{P}}}}]=1$. It means
$\mu_{\tilde{\mathbb{P}}}=-\frac{1}{2}\sigma_{\tilde{\mathbb{P}}}^{2}$.

We calculate the objective by conditioning on $N$ first. Since

$N_{\tilde{\mathbb{P}}}|N\sim\mathcal{N}\left(\mu_{\tilde{\mathbb{P}}}+\Sigma_{LN}^{\top}\Sigma_{N}^{-1}(N-\mu_{N}),\sigma^{2}_{\tilde{\mathbb{P}}}-\Sigma_{LN}^{\top}\Sigma_{N}^{-1}\Sigma_{LN}\right),$

we have

$\mathbb{E}[\bar{F}^{2}(N)e^{-N_{\tilde{\mathbb{P}}}}]=\mathbb{E}[\bar{F}^{2}(N)\mathbb{E}[e^{-N_{\tilde{\mathbb{P}}}}|N]]=\mathbb{E}[\bar{F}^{2}(N)e^{-\Sigma_{LN}^{\top}\Sigma_{N}^{-1}(N-\mu_{N})}]e^{\sigma^{2}_{\tilde{\mathbb{P}}}-\frac{1}{2}\Sigma_{LN}^{\top}\Sigma_{N}^{-1}\Sigma_{LN}}.$

Hence it is a decreasing function in $\sigma_{\tilde{\mathbb{P}}}^{2}$, and
the joint normality implies that
$\sigma_{\tilde{\mathbb{P}}}^{2}\geq\Sigma_{LN}^{\top}\Sigma_{N}^{-1}\Sigma_{LN}$.
This proves our claim. Moreover, when
$\sigma^{2}_{\tilde{\mathbb{P}}}=\Sigma_{LN}^{\top}\Sigma_{N}^{-1}\Sigma_{LN}$,
there exist a vector $\bar{\theta}$ and a scalar $c$, such that
$N_{\tilde{\mathbb{P}}}=\bar{\theta}^{\top}N+c$. $\hfill\Box$

Now let us first prove an intermediary result. We use the following notion to
denote the log-likelihood ratio up to time $n$ induced by our proposed change
of measure (9):

$LR_{n}(\theta,\eta):=\sum_{i=1}^{n}\left[\theta^{\top}Y_{i}+k(X_{i-1},X_{i},\eta)-\psi(X_{i-1},X_{i},\theta)-\phi(X_{i-1},\eta)\right].$

###### Lemma 15.4

Under Assumptions 3.1, 3.1, and 3.1, the asymptotic optimal tilting
distribution within the LAN family for an event in the asymptotic normal
regime is achieved by choosing the link function according to
$k(x,x^{\prime},\eta)=\psi(x,x^{\prime},\eta)+\eta^{\top}g(x^{\prime})$, where
$g$ satisfies (14), and the tilting parameter satisfies
$\theta=O(\frac{1}{\sqrt{n}})$, $\eta=O(\frac{1}{\sqrt{n}})$, and
$\theta-\eta=o(\frac{1}{\sqrt{n}})$.

Proof. Assumption 3.1 guarantees the existence of $\psi$ and Assumption 3.1
assumes the existence of $g$.

Given this link function
$k(x,x^{\prime},\eta)=\psi(x,x^{\prime},\eta)+\eta^{\top}g(x^{\prime})$, based
on the definition, the cumulant function is

$e^{\phi(x,\eta)}=\mathbb{E}[e^{k(X_{0},X_{1},\eta)}|X_{0}=x]=\mathbb{E}[e^{\psi(X_{0},X_{1},\eta)+\eta^{\top}g(X_{1})}|X_{0}=x]=\mathbb{E}[e^{\eta^{\top}Y_{1}+\eta^{\top}g(X_{1})}|X_{0}=x].$

Therefore,
$\frac{\partial\phi}{\partial\eta}(x,0)=\mathbb{E}_{x}[Y_{1}+g(X_{1})]$. Since
$g$ solves (14),
$g(x)-\mathbb{E}_{x}[g(X_{1})]=\mathbb{E}_{x}[Y_{1}]-\mathbb{E}_{\pi}[Y_{1}]$,
we obtain
$\frac{\partial\phi}{\partial\eta}(x,0)=g(x)+\mathbb{E}_{\pi}[Y_{1}]$.

Now let us check the log-likelihood ratio when
$\theta=\eta=-\frac{\bar{\theta}}{\sqrt{n}}$:

$\displaystyle
LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}+g(X_{i})]-\sum_{i=1}^{n}\phi(X_{i-1},-\frac{\bar{\theta}}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}+g(X_{i})-\frac{\partial\phi}{\partial\eta}(X_{i-1},0)]-\frac{1}{2n}\sum_{i=1}^{n}\bar{\theta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\theta}+o(1)$
$\displaystyle=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}\big{[}Y_{i}+g(X_{i})-g(X_{i-1})-\mathbb{E}_{\pi}[Y_{1}]\big{]}-\frac{1}{2n}\sum_{i=1}^{n}\bar{\theta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\theta}+o(1)$
$\displaystyle=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}\big{[}Y_{i}-\mathbb{E}_{\pi}[Y_{1}]\big{]}-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[g(X_{n})-g(X_{0})]-\frac{1}{2n}\sum_{i=1}^{n}\bar{\theta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\theta}+o(1)$
$\displaystyle=$
$\displaystyle\underbrace{-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\big{(}S_{n}-n\mathbb{E}_{\pi}[Y_{1}]\big{)}}_{\text{central
limit
theorem}}\underbrace{-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[g(X_{n})-g(X_{0})]}_{\to
0}\underbrace{-\frac{1}{2n}\sum_{i=1}^{n}\bar{\theta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\theta}}_{\text{law
of large numbers}}+o(1).$

By the central limit theorem in Theorem 17.5.3 of Meyn and Tweedie (2012),
Assumption 3.1, and Slutsky’s theorem,
$LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})$
converges to a normal distribution.

Next, we check the asymptotic mean and variance of the log likelihood ratio.
For simplicity, we denote by $m\in\mathbb{R}^{d},C\in\mathbb{R}^{d\times d}$
the asymptotic mean and variance of $S_{n}$. In particular,
$m=\mathbb{E}_{\pi}[Y_{1}]$, $C=\lim_{n\to
0^{+}}\frac{1}{n}\operatorname{Var}_{\pi}(S_{n})$. The asymptotic mean of
$LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})$ is
determined by the law of large numbers term that converges to
$-\frac{1}{2}\bar{\theta}^{\top}\mathbb{E}_{\pi}[\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{0},0)]\bar{\theta}$.
The asymptotic variance of $LR_{n}(\bar{\theta},\bar{\theta})$ is determined
by the central limit theorem term, which equals to
$\bar{\theta}^{\top}C\bar{\theta}$. It remains to verify
$C=\mathbb{E}_{\pi}[\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{0},0)]$.

Denote $M_{n}=S_{n}+g(X_{n})-nm-g(X_{0})=\sum_{i=1}^{n}z_{i}$, with
$z_{n}=Y_{n}+g(X_{n})-g(X_{n-1})-m$. Notice that $M_{n}$ is a martingale under
any $\mathbb{P}_{x}$, and $\mathbb{E}_{x}[M_{n}]=0$. Hence
$\operatorname{Var}_{x}(\frac{1}{\sqrt{n}}M_{n})=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{x}[z_{i}z_{i}^{\top}]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{x}[\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)]$.
Recall that $\frac{1}{\sqrt{n}}M_{n}\to\mathcal{N}(m,C)$ in distribution under
any $\mathbb{P}_{x}$. Therefore
$\operatorname{Var}_{x}(\frac{1}{\sqrt{n}}M_{n})\to C$ as $n\to\infty$ for any
$x$. In particular, we take $x$ follows the stationary distribution and obtain
$\mathbb{E}_{\pi}[\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{0},0)]=C$. This
proves that our tilting family also belongs to LAN family.

Moreover, this normal distribution is a linear transformation of $S_{n}$.
Therefore, by Lemma 15.3, the proposed tilting probability is asymptotically
optimal within the LAN family. This is because the join normal distribution
for the log-likelihood ratio and the event considered in Lemma 15.3 are
exhaustive for the limiting distributions of all twisted probabilities in the
LAN family (see Definitions 4.1 and 4.2). Lemma 15.3 shows that the proposed
tilting probability minimizes the asymptotic variance, and hence is
asymptotically optimal within LAN family.

Lastly, we relax the condition to $\theta=-\frac{\bar{\theta}_{n}}{\sqrt{n}}$,
$\eta=-\frac{\bar{\eta}_{n}}{\sqrt{n}}$, and
$\lim_{n\to\infty}\bar{\theta}_{n}=\lim_{n\to\infty}\bar{\eta}_{n}=\bar{\theta}<\infty$.
In this case, the log-likelihood ratio becomes

$\displaystyle
LR_{n}(-\frac{\bar{\theta}_{n}}{\sqrt{n}},-\frac{\bar{\eta}_{n}}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle-\frac{\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}+g(X_{i})]-\sum_{i=1}^{n}\phi(X_{i-1},-\frac{\bar{\eta}_{n}}{\sqrt{n}})+\sum_{i=1}^{n}[-\frac{\bar{\theta}_{n}^{\top}-\bar{\eta}_{n}^{\top}}{\sqrt{n}}Y_{i}-\psi(X_{i-1},X_{i},-\frac{\bar{\theta}_{n}}{\sqrt{n}})+\psi(X_{i-1},X_{i},-\frac{\bar{\eta}_{n}}{\sqrt{n}})]$
$\displaystyle=$
$\displaystyle-\frac{\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}+g(X_{i})]-\sum_{i=1}^{n}\phi(X_{i-1},-\frac{\bar{\eta}_{n}}{\sqrt{n}})-\frac{\bar{\theta}_{n}^{\top}-\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}-\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)]$
$\displaystyle-\frac{1}{2}\sum_{i=1}^{n}[\frac{1}{n}\bar{\theta}_{n}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\theta}_{n}-\frac{1}{n}\bar{\eta}_{n}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\eta}_{n}+o(\frac{1}{n})]$
$\displaystyle=:$ $\displaystyle I_{1}+I_{2}+I_{3},$

where

$\displaystyle I_{1}=$
$\displaystyle-\frac{\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}+g(X_{i})]-\sum_{i=1}^{n}\phi(X_{i-1},-\frac{\bar{\eta}_{n}}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle-\frac{\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}\big{[}Y_{i}-\mathbb{E}_{\pi}[Y_{1}]\big{]}-\frac{\bar{\eta}_{n}^{\top}}{\sqrt{n}}[g(X_{n})-g(X_{0})]-\frac{1}{2n}\sum_{i=1}^{n}\bar{\eta}_{n}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\eta}_{n}+o(1)$
$\displaystyle=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}\big{[}Y_{i}-\mathbb{E}_{\pi}[Y_{1}]\big{]}-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[g(X_{n})-g(X_{0})]-\frac{1}{2n}\sum_{i=1}^{n}\bar{\theta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\theta}+o(1)$

by the above argument,

$I_{2}=-\frac{\bar{\theta}_{n}^{\top}-\bar{\eta}_{n}^{\top}}{\sqrt{n}}\sum_{i=1}^{n}[Y_{i}-\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)]=(\bar{\theta}_{n}^{\top}-\bar{\eta}_{n}^{\top})O(1)=o(1),$

and

$I_{3}=-\frac{1}{2}\sum_{i=1}^{n}[\frac{1}{n}\bar{\theta}_{n}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\theta}_{n}-\frac{1}{n}\bar{\eta}_{n}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\eta}_{n}+o(\frac{1}{n})]=o(1).$

Combining all the above together, we show that asymptotically
$LR_{n}(-\frac{\bar{\theta}_{n}}{\sqrt{n}},-\frac{\bar{\eta}_{n}}{\sqrt{n}})$
converges to the same distribution as
$LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})$. The
proof is completed. $\hfill\Box$

Finally, let us prove Theorem 4.4. Recall that Assumptions 3.1, 3.1, and 3.1
guarantee the existence of $\psi$ and $g$.

Given the link function (13) with $\theta=-\frac{\bar{\theta}}{\sqrt{n}}$,
$\eta=-\frac{\bar{\eta}}{\sqrt{n}}$, the log-likelihood ratio is

$\displaystyle
LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\eta}}{\sqrt{n}})=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}S_{n}+\sum_{i=1}^{n}\big{\\{}-\psi(X_{i-1},X_{i},-\frac{\bar{\theta}}{\sqrt{n}})-\frac{\bar{\eta}^{\top}}{\sqrt{n}}[\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)+\Delta(X_{i},0)]-\phi(X_{i-1},-\frac{\bar{\eta}}{\sqrt{n}})\big{\\}}$
$\displaystyle=$
$\displaystyle-\frac{\bar{\theta}^{\top}}{\sqrt{n}}S_{n}+\sum_{i=1}^{n}\big{\\{}\frac{\bar{\theta}^{\top}-\bar{\eta}^{\top}}{\sqrt{n}}\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)-\frac{\bar{\eta}^{\top}}{\sqrt{n}}\Delta(X_{i},0)+\frac{\bar{\eta}^{\top}}{\sqrt{n}}\frac{\partial\phi}{\partial\eta}(X_{i-1},0)$
$\displaystyle+\frac{1}{2n}[-\bar{\theta}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\theta}-\bar{\eta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\eta}]+o(\frac{1}{n})\big{\\}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{\\{}-\bar{\theta}^{\top}Y_{i}+(\bar{\theta}^{\top}-\bar{\eta}^{\top})\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)-\bar{\eta}^{\top}\Delta(X_{i},0)+\bar{\eta}^{\top}\frac{\partial\phi}{\partial\eta}(X_{i-1},0)\big{\\}}$
$\displaystyle-\frac{1}{2n}\sum_{i=1}^{n}[\bar{\theta}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)\bar{\theta}+\bar{\eta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)\bar{\eta}]+o(1).$

In this case,

$\mathbb{E}_{x}[e^{\eta^{\top}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)]}]=e^{\phi(x,\eta)},\
\mathbb{E}[e^{\theta^{\top}Y_{1}}|X_{0},X_{1}]=e^{\psi(X_{0},X_{1},\theta)},$

hence

$\mathbb{E}_{x}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)]=\frac{\partial\phi}{\partial\eta}(x,0),\
\mathbb{E}[Y_{1}|X_{0},X_{1}]=\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0).$
$\operatorname{Var}_{x}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)]=\frac{\partial^{2}\phi}{\partial\eta^{2}}(x,0),\
\operatorname{Var}[Y_{1}|X_{0},X_{1}]=\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{0},X_{1},0).$

Under the stationary distribution $\pi$ of the underlying Markov chain, then
jointly, $\\{(X_{i-1},X_{i},Y_{i}),i\geq 0\\}$ is also a Markov chain.
Following the similar argument in the proof of Lemma 15.4,
$LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\eta}}{\sqrt{n}})$
converges to a normal distribution. Moreover, we can find the asymptotic mean
of $LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\eta}}{\sqrt{n}})$ is
$-\frac{1}{2}\mathbb{E}_{\pi}[\bar{\theta}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{0},X_{1},0)\bar{\theta}+\bar{\eta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{0},0)\bar{\eta}]$,
and the asymptotic variance is
$\mathbb{E}_{\pi}[\bar{\theta}^{\top}\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{0},X_{1},0)\bar{\theta}+\bar{\eta}^{\top}\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{0},0)\bar{\eta}]$.
This proves that our tilting family also belongs to LAN family.

In particular, by choosing $\theta=\eta=-\frac{\bar{\theta}}{\sqrt{n}}$, we
will claim that
$LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})=\widebar{LR}_{n}(-\frac{\bar{\theta}}{\sqrt{n}})+o(1)$,
where

$\widebar{LR}_{n}(\theta)=\theta^{\top}[S_{n}-n\Lambda^{\prime}(0)+\sum_{i=1}^{n}\big{(}\Delta(X_{i},0)-\Delta(X_{i-1},0)\big{)}]-\frac{n}{2}\theta^{\top}\Lambda^{\prime\prime}(0)\theta.$

To see this, consider

$\displaystyle
LR_{n}(-\frac{\bar{\theta}}{\sqrt{n}},-\frac{\bar{\theta}}{\sqrt{n}})-\widebar{LR}_{n}(-\frac{\bar{\theta}}{\sqrt{n}})-\frac{1}{2}\bar{\theta}^{\top}\Lambda^{\prime\prime}(0)\bar{\theta}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\bigg{[}-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\Delta(X_{i-1},0)-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\Lambda^{\prime}(0)-\psi(X_{i-1},X_{i},-\frac{\bar{\theta}}{\sqrt{n}})-\frac{\bar{\theta}^{\top}}{\sqrt{n}}\frac{\partial\psi}{\partial\theta}(X_{i-1},X_{i},0)-\phi(X_{i-1},-\frac{\bar{\theta}}{\sqrt{n}})\bigg{]}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\bigg{[}-\frac{1}{2n}\bar{\theta}^{\top}[\frac{\partial^{2}\psi}{\partial\theta^{2}}(X_{i-1},X_{i},0)+\frac{\partial^{2}\phi}{\partial\eta^{2}}(X_{i-1},0)]\bar{\theta}+\frac{\bar{\theta}^{\top}}{\sqrt{n}}[\frac{\partial\phi}{\partial\eta}(X_{i-1},0)-\Delta(X_{i-1},0)-\Lambda^{\prime}(0)]\bigg{]}.$

By definition of $\phi$, we have

$e^{\phi(x,\eta)}=\mathbb{E}\big{[}e^{\eta^{\top}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)]}|X_{0}=x\big{]},$

hence
$\frac{\partial\phi}{\partial\eta}(x,0)=\mathbb{E}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)|X_{0}=x]$.
On the other hand, from (i) we get

$\Lambda^{\prime}(0)+\Delta(x,0)=\mathbb{E}[Y_{1}+\Delta(X_{1},0)|X_{0}=x]=\mathbb{E}[\frac{\partial\psi}{\partial\theta}(X_{0},X_{1},0)+\Delta(X_{1},0)|X_{0}=x].$

Therefore,
$\Lambda^{\prime}(0)+\Delta(x,0)=\frac{\partial\phi}{\partial\eta}(x,0)$.

Note that
$\widebar{LR}_{n}(-\frac{\bar{\theta}}{\sqrt{n}})=-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[S_{n}-n\Lambda^{\prime}(0)]-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[\Delta(X_{n},0)-\Delta(X_{0},0)]+c=-\frac{\bar{\theta}^{\top}}{\sqrt{n}}[S_{n}-n\Lambda^{\prime}(0)]+c+o(1)$.
Therefore, by Lemma 15.3, the proposed tilting probability is asymptotically
optimal.

Lastly, we relax the condition to $\theta=-\frac{\bar{\theta}_{n}}{\sqrt{n}}$,
$\eta=-\frac{\bar{\eta}_{n}}{\sqrt{n}}$, and
$\lim_{n\to\infty}\bar{\theta}_{n}=\lim_{n\to\infty}\bar{\eta}_{n}=\bar{\theta}<\infty$.
The rest of the proof follows the same argument as in the proof of Lemma 15.4.
$\hfill\Box$

###  15.6 Proof of Lemma 4.5

Under Assumption 3.1 $r(x;\alpha)$ is analytic.

We start from the definition of eigenvalue and eigenfunction in (4). Notice
that $\Lambda(0)=0$ and $r(x,0)$ is normalized to be 1. We consider the Taylor
expansion of both $r(x,\theta)$ and $\Lambda(\theta)$ at any point
$\theta_{0}$:

$e^{\Lambda(\theta)}\approx
e^{\Lambda(\theta_{0})}+e^{\Lambda(\theta_{0})}\Lambda^{\prime}(\theta_{0})^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0}),$
$r(x,\theta)\approx r(x,\theta_{0})+\frac{\partial
r}{\partial\theta}(x,\theta_{0})^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0}).$

Therefore, under Assumption 3.1, (4) becomes

$\displaystyle\big{[}e^{\Lambda(\theta_{0})}+e^{\Lambda(\theta_{0})}\Lambda^{\prime}(\theta_{0})^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0})\big{]}\big{[}r(x,\theta_{0})+\frac{\partial
r}{\partial\theta}(x,\theta_{0})^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0})\big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{x}\bigg{[}\big{(}e^{\theta_{0}^{\top}Y_{1}}+e^{\theta_{0}^{\top}Y_{1}}Y_{1}^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0})\big{)}\big{[}r(X_{1},\theta_{0})+\frac{\partial
r}{\partial\theta}(X_{1},\theta_{0})^{\top}(\theta-\theta_{0})+o(\theta-\theta_{0})\big{]}\bigg{]}.$

The leading order terms are canceled. Then comparing $O(\theta-\theta_{0})$
term leads to

$e^{\Lambda(\theta_{0})}\frac{\partial
r}{\partial\theta}(x,\theta_{0})+e^{\Lambda(\theta_{0})}\Lambda^{\prime}(\theta_{0})r(x,\theta_{0})=\mathbb{E}_{x}\big{[}e^{\theta_{0}^{\top}Y_{1}}\frac{\partial
r}{\partial\theta}(X_{1},\theta_{0})+e^{\theta_{0}Y_{1}}Y_{1}r(X_{1},\theta_{0})\big{]}.$

Denote $\Delta(x,\theta)=\frac{\partial r}{\partial\theta}(x,\theta)$, then
the above equality becomes

$\Delta(x,\theta_{0})+\Lambda^{\prime}(\theta_{0})=\mathbb{E}_{x}\big{[}e^{\theta_{0}^{\top}Y_{1}-\Lambda(\theta_{0})}\frac{r(X_{1},\theta_{0})}{r(x,\theta_{0})}\big{(}\Delta(X_{1},\theta_{0})+Y_{1}\big{)}\big{]}.$

Recall the definition of the probability $\mathbb{P}_{\theta}$ in (4), we
obtain

$\mathbb{E}^{\mathbb{P}_{\theta_{0}}}_{x}[\Delta(X_{1},\theta_{0})-\Delta(x,\theta_{0})+Y_{1}]=\Lambda^{\prime}(\theta_{0}).$

Moreover, since the right hand side does not depend on the initial state $x$,
we have taken the initial state as any arbitrary distribution $\nu$. Then

$\mathbb{E}^{\mathbb{P}_{\theta_{0}}}_{\nu}[\Delta(X_{1},\theta_{0})-\Delta(x,\theta_{0})+Y_{1}]=\Lambda^{\prime}(\theta_{0}).$

In particular, if we take the initial distribution to be the stationary
distribution under $\mathbb{P}_{\theta}$, denoted by $\pi_{\theta}$, then
$\mathbb{E}^{\mathbb{P}_{\theta_{0}}}_{\pi_{\theta}}[\Delta(X_{1},\theta_{0})-\Delta(x,\theta_{0})]=0$,
hence
$\mathbb{E}_{\pi_{\theta}}^{\mathbb{P}_{\theta}}[Y_{1}]=\Lambda^{\prime}(\theta)$.

In particular, take $\theta_{0}=0$ to obtain

$\mathbb{E}_{x}[\Delta(X_{1},0)-\Delta(x,0)]=\Lambda^{\prime}(0)-\mathbb{E}_{x}[Y_{1}]=\mathbb{E}_{\pi}[Y_{1}]-\mathbb{E}_{x}[Y_{1}],$

where $\pi$ is the stationary distribution of the underlying Markov chain
$\\{X_{n},n\geq 0\\}$. The left hand side can be represented as
$(\mathcal{P}_{0}-I)\Delta(x,0)$, where $I$ is the identity operator and
$\mathcal{P}_{0}$ is the operator defined in (3). $\hfill\Box$

###  15.7 Proof of Theorem 5.2

  1. (i)

We first consider the fixed-time event.

Under the asymptotic normal regime, by the Borjesson-Sundberg bound on the
Mills ratio, we have

$\lim_{n\to\infty}z(n,\ell)=\Phi(-\ell)\geq\frac{\ell}{1+\ell^{2}}\varphi(\ell)=\frac{\ell}{(1+\ell^{2})\sqrt{2\pi\sigma^{2}}}e^{-\frac{\ell^{2}}{2}}.$

To prove the bounded relative or logarithmic efficiency, it suffices to find
suitable upper bound for the variance of the estimator.

When $S_{n}=\sum_{k=1}^{n}Y_{k}$, and $\\{(X_{n},S_{n}),n\geq 0\\}$ forms a
Markov random walk as described in Section 2. The classical exponential
tilting family is given by (5), with $r(\cdot,\theta)$ and $\Lambda(\theta)$
eigenfunction and eigenvalue respectively. Note that under Assumptions 3.1 and
3.1, $\Lambda(\theta)$ is analytic for $\theta\in\Theta$.

Without loss of generality, we assume $\ell>0$, and
$\sqrt{n}\frac{S_{n}}{n}\to\mathcal{N}(0,1)$ in the later development, and
restrict to the one-dimensional case $S_{n}\in\mathbb{R}$. Here we assume the
stationary mean of $S_{1}$ is $0$ and the stationary variance of $S_{1}$ is
$1$. Under Assumptions 3.1 to 3.1, by Theorem 17.0.1 of Meyn and Tweedie
(2012), we have $\frac{S_{n}}{\sqrt{n}}\to\mathcal{N}(0,1)$.

By Theorem 4.1 of Ney and Nummelin (1987a), we have the relation between the
eigenvalue and the mean and variance of the limiting distribution as

$0=\mathbb{E}_{\pi}[Y_{1}]=\Lambda^{\prime}(0),\ 1=\Lambda^{\prime\prime}(0).$

And we still can define the Legendre transformation of $\Lambda$ by

$\hat{\Lambda}(c)=\sup_{\theta\geq
0}\\{c\theta-\Lambda(\theta)\\}=c{\Lambda^{\prime}}^{-1}(c)-\Lambda\left({\Lambda^{\prime}}^{-1}(c)\right).$

Recall that the importance sampling estimator in the classical exponential
tilting, $\hat{Z}(n,\ell;\theta)$, is to sample under $\mathbb{P}_{\theta}$,
with $\theta>0$ and is given by
$\mathbbm{1}_{\\{\sqrt{n}\frac{S_{n}}{n}>\ell\\}}\frac{r(X_{0},\theta)}{r(X_{n},\theta)}e^{-\theta
S_{n}+n\Lambda(\theta)}$. It has variance

$\displaystyle\operatorname{Var}\left(\hat{Z}(n,\ell;\theta)\right)=$
$\displaystyle\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}[\mathbbm{1}_{\\{\sqrt{n}\frac{S_{n}}{n}>\ell\\}}e^{-2\theta
S_{n}+2n\Lambda(\theta)+2\log r(X_{0},\theta)-2\log
r(X_{n},\theta)}]-\left(z(n,x)\right)^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}[\mathbbm{1}_{\\{\sqrt{n}\frac{S_{n}}{n}>\ell\\}}e^{-2\theta
S_{n}+2n\Lambda(\theta)+2\log r(X_{0},\theta)-2\log r(X_{n},\theta)}]$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-2n\left[\frac{\ell}{\sqrt{n}}\theta-\Lambda(\theta)\right]\right\\}\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}\left[\left(\frac{r(X_{0},\theta)}{r(X_{n},\theta)}\right)^{2}\right].$

By picking
$\theta_{n,\ell}^{*}={\Lambda^{\prime}}^{-1}(\frac{\ell}{\sqrt{n}})$, we have

$\operatorname{Var}\left(\hat{Z}(n,\ell;\theta_{n,\ell}^{*})\right)\leq\exp\left\\{-2n\hat{\Lambda}(\frac{\ell}{\sqrt{n}})\right\\}\mathbb{E}_{\nu}^{\mathbb{P}_{\theta_{n,\ell}^{*}}}\left[\left(\frac{r(X_{0},\theta_{n,\ell}^{*})}{r(X_{n},\theta_{n,\ell}^{*})}\right)^{2}\right].$

Moreover, by Taylor’s expansion, we have

$\theta_{n,\ell}^{*}=\left[\frac{1}{\Lambda^{\prime\prime}\left({\Lambda^{\prime}}^{-1}(0)\right)}\frac{\ell}{\sqrt{n}}+o(\frac{1}{\sqrt{n}})\right]=\frac{\ell}{\sqrt{n}}+o(\frac{1}{\sqrt{n}}).$

Hence

$-2n\hat{\Lambda}(\frac{\ell}{\sqrt{n}})=-2n\left[\hat{\Lambda}(0)+\hat{\Lambda}^{\prime}(0)\frac{\ell}{\sqrt{n}}+\frac{1}{2}\hat{\Lambda}^{\prime\prime}(0)\frac{\ell^{2}}{n}+o(\frac{1}{n})\right]\to-\ell^{2}\hat{\Lambda}^{\prime\prime}(0)=-\ell^{2}.$

In addition, Assumption 3.1 implies
$\mathbb{E}_{\nu}^{\mathbb{P}_{\theta_{n,\ell}^{*}}}\left[\left(\frac{r(X_{0},\theta_{n,\ell}^{*})}{r(X_{n},\theta_{n,\ell}^{*})}\right)^{2}\right]\leq
C$ for some constant $C$ as $\theta^{*}_{n,\ell}\to 0$.

Note that as $n\to\infty$, $\theta^{*}_{n,\ell}\to 0$. Therefore,

$\limsup_{n\to\infty}\frac{\operatorname{Var}\left(\hat{Z}(n,\ell;\theta_{n,\ell}^{*})\right)}{z(n,\ell)^{2-\varepsilon}}\leq\frac{Ce^{-\ell^{2}}}{\left(\Phi(-\ell)\right)^{2-\epsilon}}\leq
C\left(\frac{(1+\ell^{2})\sqrt{2\pi}}{\ell}\right)^{2-\epsilon}e^{-\frac{\epsilon\ell^{2}}{2}},$

where the right-hand side tends to 0 as $\ell\to+\infty$. Hence the sequence
of estimator $\\{\hat{Z}(n,\ell;\theta_{n,\ell}^{*})\\}$ has logarithmic
efficiency.

Next, we show the sequence of estimator
$\\{\hat{Z}(n,\ell;\theta_{n,\ell}^{*})\\}$ belongs to the LAN family (based
on Definition 4.1). The log-likelihood ratio is

$\displaystyle\theta^{*}_{n,\ell}S_{n}-n\Lambda(\theta^{*}_{n,\ell})+\log
r(X_{n},\theta^{*}_{n,\ell})-\log r(X_{0},\theta^{*}_{n,\ell})$ (33)
$\displaystyle=$
$\displaystyle{\Lambda^{\prime}}^{-1}(\frac{\ell}{\sqrt{n}})S_{n}-n\Lambda\left({\Lambda^{\prime}}^{-1}(\frac{\ell}{\sqrt{n}})\right)+\log
r\left(X_{n},{\Lambda^{\prime}}^{-1}(\frac{\ell}{\sqrt{n}})\right)-\log
r\left(X_{0},{\Lambda^{\prime}}^{-1}(\frac{\ell}{\sqrt{n}})\right)$
$\displaystyle=$
$\displaystyle\left[\frac{1}{\Lambda^{\prime\prime}\left({\Lambda^{\prime}}^{-1}(0)\right)}\frac{\ell}{\sqrt{n}}+o(\frac{1}{\sqrt{n}})\right]S_{n}-n\left[\frac{1}{2}\Lambda^{\prime\prime}(0)\left[\frac{1}{\Lambda^{\prime\prime}\left({\Lambda^{\prime}}^{-1}(0)\right)}\frac{\ell}{\sqrt{n}}+o(\frac{1}{\sqrt{n}})\right]^{2}+o(\frac{1}{n})\right]$
$\displaystyle+\left[\frac{\partial r}{\partial\theta}(X_{n},0)-\frac{\partial
r}{\partial\theta}(X_{0},0)\right]\left[\frac{1}{\Lambda^{\prime\prime}\left({\Lambda^{\prime}}^{-1}(0)\right)}\frac{\ell}{\sqrt{n}}+o(\frac{1}{\sqrt{n}})\right]$
$\displaystyle=$
$\displaystyle\ell\frac{1}{\sqrt{n}}S_{n}+O(\frac{1}{\sqrt{n}})-\frac{\ell^{2}}{2}+o(1)\to\mathcal{N}(-\frac{\ell^{2}}{2},\ell^{2})~{}{\rm
as}~{}n\to\infty.$

Note that under Assumptions 3.1 to 3.1, the asymptotic normality in (33) comes
from Theorem 17.0.1 of Meyn and Tweedie (2012).

Now suppose there is another sequence of estimator
$\\{\hat{Z}_{opt}(n,\ell)\\}$ belonging to the LAN family and achieving the
smallest asymptotic variance. Then it means

$\limsup_{n\to\infty}\operatorname{Var}\left(\hat{Z}_{opt}(n,\ell)\right)\leq\limsup_{n\to\infty}\operatorname{Var}\left(\hat{Z}(n,\ell;\theta_{n,\ell}^{*})\right).$

Hence $\\{\hat{Z}_{opt}(n,\ell)\\}$ also has logarithmic efficiency.

  2. (ii)

Next we consider the first-passage time event.

When $S_{n}=\sum_{k=1}^{n}Y_{k}$, and $\\{(X_{n},S_{n}),n\geq 0\\}$ forms a
Markov random walk as described in Section 2. Recall that the importance
sampling estimator in the classical exponential tilting,
$\hat{Z}(b,\ell;\theta)$, is to sample under $\mathbb{P}_{\theta}$, with
$\theta>0$ and is given by
$\mathbbm{1}_{\\{\tau_{b}<\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\\}}\frac{r(X_{0},\theta)}{r(X_{\tau_{b}},\theta)}e^{-\theta
S_{\tau_{b}}+\tau_{b}\Lambda(\theta)}$, where $\theta\geq 0$. Since
$\Lambda^{\prime}(0)=\mu>0$, $\Lambda^{\prime\prime}(0)=\sigma^{2}<\infty$, we
know when $\theta>0$ is sufficiently close to 0, $\Lambda(\theta)>0$.

In this case, the importance sampling estimator in the classical exponential
tilting has variance

$\displaystyle\operatorname{Var}\left(\hat{Z}(b,\ell;\theta)\right)=$
$\displaystyle\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}[\mathbbm{1}_{\\{\tau_{b}<\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\\}}e^{-2\theta
S_{\tau_{b}}+2\tau_{b}\Lambda(\theta)+2\log r(X_{0},\theta)-2\log
r(X_{\tau_{b}},\theta)}]-\left(z(n,b)\right)^{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}[\mathbbm{1}_{\\{\tau_{b}<\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\\}}e^{-2\theta
b+2[\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}]\Lambda(\theta)+2\log
r(X_{0},\theta)-2\log r(X_{\tau_{b}},\theta)}]$ $\displaystyle\leq$
$\displaystyle\exp\left\\{-2\left(\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\right)\left[\frac{b}{\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}}\theta-\Lambda(\theta)\right]\right\\}\mathbb{E}_{\nu}^{\mathbb{P}_{\theta}}\left[\left(\frac{r(X_{0},\theta)}{r(X_{\tau_{b}},\theta)}\right)^{2}\right].$

By picking
$\theta_{b,\ell}^{*}={\Lambda^{\prime}}^{-1}(\frac{b}{\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}})={\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})=\frac{1}{\sigma^{2}}\left(-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right)+O(\frac{1}{b})$,
we have

$\operatorname{Var}\left(\hat{Z}(b,\ell;\theta_{b,\ell}^{*})\right)\leq\exp\left\\{-2\left(\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\right)\hat{\Lambda}\left(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1}\right)\right\\}\mathbb{E}_{\nu}^{\mathbb{P}_{\theta_{b,\ell}^{*}}}\left[\left(\frac{r(X_{0},\theta_{b,\ell}^{*})}{r(X_{\tau_{b}},\theta_{b,\ell}^{*})}\right)^{2}\right].$

Moreover, by Taylor’s expansion,

$\displaystyle\hat{\Lambda}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})=$
$\displaystyle{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1}-\Lambda\left({\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\right)$
$\displaystyle=$
$\displaystyle{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\left[\mu-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right]$
$\displaystyle-\mu{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})-\frac{\sigma^{2}}{2}\left({\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\right)^{2}$
$\displaystyle=$
$\displaystyle\left[\frac{1}{\sigma^{2}}\left(-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right)+O(\frac{1}{b})\right]\left[-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right]$
$\displaystyle-\frac{\sigma^{2}}{2}\left[\frac{1}{\sigma^{2}}\left(-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right)+O(\frac{1}{b})\right]^{2}$
$\displaystyle=$ $\displaystyle\frac{\mu}{2b}\ell^{2}+o(\frac{1}{b}).$

Hence

$-2\left(\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\right)\hat{\Lambda}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})=-2\left(\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\ell+\frac{b}{\mu}\right)\left(\frac{\mu}{2b}\ell^{2}+o(\frac{1}{b})\right)=-\ell^{2}+O(\frac{1}{\sqrt{b}}).$

In addition, Assumption 3.1 implies
$\mathbb{E}_{\nu}^{\mathbb{P}_{\theta_{b,\ell}^{*}}}\left[\left(\frac{r(X_{0},\theta_{b,\ell}^{*})}{r(X_{\tau_{b}},\theta_{b,\ell}^{*})}\right)^{2}\right]\leq
C$ for some constant $C$ as $\theta^{*}_{b,\ell}\to 0$.

Note that as $b\to\infty$, $\theta^{*}_{b,\ell}\to 0$. Therefore,

$\limsup_{b\to\infty}\frac{\operatorname{Var}\left(\hat{Z}(b,\ell;\theta_{b,\ell}^{*})\right)}{z(b,\ell)^{2-\varepsilon}}\leq\frac{Ce^{-\ell^{2}}}{\left(\Phi(\ell)\right)^{2-\epsilon}}\leq
C\left(\sqrt{2\pi}\ell\right)^{2-\epsilon}e^{-\frac{\epsilon\ell^{2}}{2}},$

where the right-hand side tends to 0 as $\ell\to-\infty$. Hence the sequence
of estimator $\\{\hat{Z}(b,\ell;\theta_{b,\ell}^{*})\\}$ has logarithmic
efficiency.

Next, we show the sequence of estimator
$\\{\hat{Z}(b,\ell;\theta_{b,\ell}^{*})\\}$ belongs to the LAN family (based
on Definition 4.1 (ii)). Denote $R(b)=S_{\tau_{b}}-b$ as the overshoot. The
log-likelihood ratio is

$\displaystyle\theta_{b,\ell}^{*}S_{\tau_{b}}-\tau_{b}\Lambda(\theta_{b,\ell}^{*})+\log
r(X_{\tau_{b}},\theta^{*}_{b,\ell})-\log r(X_{0},\theta^{*}_{b,\ell})$ (34)
$\displaystyle=$
$\displaystyle{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})[b+R(b)]-\tau_{b}\Lambda\left({\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\right)$
$\displaystyle+\left[\frac{\partial
r}{\partial\theta}(X_{\tau_{b}},0)-\frac{\partial
r}{\partial\theta}(X_{0},0)\right]\left[\frac{1}{\sigma^{2}}\left(-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell+\frac{\sigma^{2}}{2b}\ell+o(\frac{1}{b})\right)+O(\frac{1}{b})\right]$
$\displaystyle=$
$\displaystyle{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})[b+R(b)]-\left[\frac{\tau_{b}-b/\mu}{\sqrt{b\sigma^{2}/\mu^{3}}}\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}+\frac{b}{\mu}\right]\bigg{[}\mu{\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})$
$\displaystyle+\frac{\sigma^{2}}{2}\left({\Lambda^{\prime}}^{-1}(\frac{\mu}{\sigma\ell/\sqrt{b\mu}+1})\right)^{2}+o(\frac{1}{b})\bigg{]}+\left[\frac{\partial
r}{\partial\theta}(X_{\tau_{b}},0)-\frac{\partial
r}{\partial\theta}(X_{0},0)\right]\left[-\frac{\sqrt{\mu}}{\sigma\sqrt{b}}\ell+O(\frac{1}{b})\right]$
$\displaystyle=$
$\displaystyle\left[-\frac{\sqrt{\mu}}{\sigma\sqrt{b}}\ell+O(\frac{1}{b})\right]R(b)-\frac{b\sigma^{2}}{2\mu}\left(\frac{\mu}{b\sigma^{2}}\ell^{2}+o(\frac{1}{b})\right)-\frac{\tau_{b}-b/\mu}{\sqrt{b\sigma^{2}/\mu^{3}}}\sqrt{\frac{b\sigma^{2}}{\mu^{3}}}\left(\frac{\mu}{\sigma^{2}}(-\frac{\sqrt{\mu}\sigma}{\sqrt{b}}\ell)+O(\frac{1}{b})\right)$
$\displaystyle+\left[\frac{\partial
r}{\partial\theta}(X_{\tau_{b}},0)-\frac{\partial
r}{\partial\theta}(X_{0},0)\right]\left[-\frac{\sqrt{\mu}}{\sigma\sqrt{b}}\ell+O(\frac{1}{b})\right]$
$\displaystyle=$ $\displaystyle
R(b)O(\frac{1}{b})-\frac{1}{2}\ell^{2}+\frac{\tau_{b}-b/\mu}{\sqrt{b\sigma^{2}/\mu^{3}}}\ell+O(\frac{1}{b}).$

To handle the asymptotic behavior in (34), we first have that under
Assumptions 3.1 to 3.1, Theorems 2 and 3 of Fuh (2004) show that
$\\{\tau<n,S_{n}<\gamma n^{1/2}\\}$, for a suitable chosen $\gamma$, satisfies
the asymptotic normality. Note that
$\mathbb{P}_{\pi}(\tau<n)=\mathbb{P}_{\pi}(S_{n}\geq
b)+\mathbb{P}_{\pi}(\tau<n,S_{n}<b)$. By using the central limit theorem of
$\mathbb{P}_{\pi}(S_{n}\geq b)$ for a suitable chosen $b$, we have
$\frac{\tau_{b}-b/\mu}{\sqrt{b\sigma^{2}/\mu^{3}}}\to\mathcal{N}(0,1)$ as
$b\to\infty$. Next, we consider the overshoot $R(b)$. Under Assumptions 3.1 to
3.1, by Lemma 2 of Fuh (2004), we have $\sup_{b\geq 0}E_{\pi}R(b)\leq
E_{\pi}(S_{1}^{+})^{2}/E_{\pi}S_{1},$ thus $R(b)O(\frac{1}{b})\to 0$ in
probability as $b\to\infty$. Therefore,
$\theta_{b,\ell}^{*}S_{\tau_{b}}-\tau_{b}\psi(\theta_{b,\ell}^{*})\to\mathcal{N}(-\frac{1}{2}\ell^{2},\ell^{2})$.

Now suppose there is another sequence of estimator
$\\{\hat{Z}_{opt}(b,\ell)\\}$ belonging to the LAN family and achieving the
smallest asymptotic variance. Then it means

$\limsup_{b\to\infty}\operatorname{Var}\left(\hat{Z}_{opt}(b,\ell)\right)\leq\limsup_{b\to\infty}\operatorname{Var}\left(\hat{Z}(b,\ell;\theta_{b,\ell}^{*})\right).$

Hence $\\{\hat{Z}_{opt}(b,\ell)\\}$ also has logarithmic efficiency.
$\hfill\Box$