\documentclass[11pt,leqno]{article}
\usepackage{amsmath,amssymb,mathrsfs,amsthm}
\def\sst#1{\vtop{\offinterlineskip\def\\{\crcr}\tabskip0pt\halign{\strut
##\hfil\cr #1\cr}}}%
\def\Line#1{\hbox to\textwidth{#1}}
\def\HD#1#2{\vrule width 0pt height #1 pt depth #2 pt\relax}%
\long\def\AOSaddress#1{\leavevmode{\footnotesize\sc
\sst{\HD40\\ \noalign{\vskip-6pt} #1}}}

\setlength{\textheight}{8.5truein}
\setlength{\topmargin}{-0.25truein}
\setlength{\oddsidemargin}{0.25truein}
\setlength{\evensidemargin}{0.25truein}
\setlength{\textwidth}{6truein}
\linespread{1.1}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{assumption}{Assumption}
\newtheorem{remark}{Remark}
\newcommand{\Thm}[1]{\begin{theorem}\label{thm.#1}}
\newcommand{\Prop}[1]{\begin{proposition}\label{prop.#1}}
\newcommand{\Lm}[1]{\begin{lemma}\label{lm.#1}}
\newcommand{\Cor}[1]{\begin{corollary}\label{cor.#1}}
\newcommand{\Ass}[1]{\begin{assumption}\label{ass.#1}\rm}
\newcommand{\Rem}[1]{\begin{remark}\label{rem.#1}\rm}
\newcommand{\Def}[1]{\begin{definition}\label{def.#1}\rm}
\newcommand{\thmref}[1]{Theorem~\ref{thm.#1}}
\newcommand{\propref}[1]{Proposition~\ref{prop.#1}}
\newcommand{\lmref}[1]{Lemma~\ref{lm.#1}}
%\newcommand{\defnref}[1]{Definition~\ref{defn.#1}}
\newcommand{\corref}[1]{Corollary~\ref{cor.#1}}
\newcommand{\assref}[1]{Assumption~\ref{ass.#1}}
\newcommand{\remref}[1]{Remark~\ref{rem.#1}}
%\newcommand{\exref}[1]{Example~#1}

\numberwithin{equation}{section}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}

\newcommand{\new}{\setlength{\parindent}{0pt}%\vspace{3.0pt}
  \setlength{\hangindent}{1.6pc}\setlength{\hangafter}{1}}
\newcommand{\Ref}[1]{(\ref{#1})}

\newcommand{\bel}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\norm}[1]{\|#1\|}
\def\ben{\begin{eqnarray}}
\def\non{\end{eqnarray}}
\def\bea{\[ \begin{aligned}}
\def\ea{\end{aligned} \]}

\def\opn{o_{P_n}(n^{-1/2})}
\def\op{o_{P_n}(1)}
\def\und{\quad\mbox{and}\quad}
\def\sm{\smallskip}
\def\m{\medskip}
\def\b{\bigskip}
\def\n{\noindent}
\def\cov{\mathrm{Cov\,}}
\def\var{\mathrm{Var\,}}

\def\sj{\sum_{j=1}^n}
\def\sk{\sum_{k=1}^m}
\def\sjk{\sum_{j=1}^k}
\def\si{\sum_{i=1}^n}
\def\ssj{n^{-1/2}\sum_{j=1}^n}
\def\s1{\sum_{j=1}^{n-1}}
\def\av1{\frac{1}{n-1}\sum_{j=1}^{n-1}}
\def\avj{\frac{1}{n}\sum_{j=1}^n}
\def\avk{\frac{1}{m}\sum_{k=1}^m}
\def\vt{\vartheta}
\def\ve{\varepsilon}
\def\vf{\varphi}
\def\vr{\varrho}
\def\hve{\hat\varepsilon}
\def\hvf{\hat\varphi}
\def\tvf{\tilde\varphi}
\def\hw{\hat w}
\def\tw{\tilde w}
\def\hF{\hat F}
\def\hW{\hat W}
\def\hQ{\hat Q}
\def\bve{\boldsymbol{\varepsilon}}
\def\tvt{\tilde\vartheta}
\def\tve{\tilde\varepsilon}
\def\tm{\tilde\mu}
\def\tR{\tilde R}
\def\tA{\tilde A}
\def\tsg{\tilde\sigma}
\def\ts{\tilde s}
\def\tf{\tilde f}
\def\tt{\tilde t}
%\def\tl{\tilde\ell}
\def\tJ{\tilde J}
\def\tT{\tilde T}
\def\tL{\tilde\Lambda}
\def\tS{\tilde\Sigma}
\def\hvt{\hat\vartheta}
%\def\hs{\hat\sigma}
\def\dr{\dot r}
\def\ds{\dot s}
\def\dvr{\dot \varrho}
%\def\RR{\mathbb{R}}
\def\R{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
%\def\NN{\mathbb{N}}
\def\EE{\mathbb{E}}
\def\1{\mathbf{1}}
\def\X{\mathbf{X}}
\def\Y{\mathbf{Y}}
\def\Z{\mathbf{Z}}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\t{\mathbf{t}}
\def\v{\mathbf{v}}
\def\w{\mathbf{w}}
\def\T{\mathbf{T}}
\def\V{\mathbf{V}}
\def\W{\mathbf{W}}
\def\TT{\mathcal{T}}
\def\E{\mathcal{E}}
%\def\bV{\bar V}
\def\bV{\bar{\mathbf{V}}}
\def\bW{\bar{\mathbf{W}}}
\def\da{\dot a}
\def\hR{\hat R}
\def\hQ{\hat Q}
\def\hp{\hat\pi}
\def\hc{\hat c}

\begin{document}
\title{Estimators for discrete Markov chains with observations
``missing at random''}

\author{Ursula U. M\"uller \\
Texas A\&M University
\and Anton Schick \\
Binghamton University
\and Wolfgang Wefelmeyer \\
Universit\"at zu K\"oln
}

\date{}
\maketitle


\begin{abstract}
Suppose we observe a stationary and homogeneous discrete-state
Markov chain, except for gaps whose length is random 
and may depend on the observation preceding the gap. 
A naive estimator for the probability of the values 
of two successive observations is the empirical estimator
based on the observed pairs of successive observations.
We show how to improve this estimator using also the pairs of observations
separated by gaps. The method is related to imputation of missing
responses in regression models.

%\b\n\textbf{Keywords.}
%Variance bound, efficient influence function,
%local asymptotic normality, missing at random, Markov renewal process,
%Martingale appproximation, weighted least squares estimator.
\end{abstract}


\section{Introduction}


Consider a stationary and homogeneous (first-order) Markov chain 
$X_i$, $i\in\Z$, on a discrete state space, which we will later take finite.
In order to estimate its transition matrix $Q$, the stationary vector $\pi$,
and general (smooth) functionals of the joint law of the chain,
it suffices to estimate the probabilities $R_{xy}=\pi_x Q_{xy}$
of successive states $(X_i,X_{i+1})=(x,y)$.
If we have observations $X_1,\dots,X_n$, the obvious estimator of $R_{xy}$
is the empirical estimator, i.e.\ the proportion of observed pairs 
for which $(X_i,X_{i+1})=(x,y)$. It will be convenient to write 
this estimator in the form
\[
\hR_{xy} = \frac{1}{n-1}\sum_{i=1}^{n-1} c_{xyi} \quad\mbox{with}\quad 
c_{xyi} = \1((X_i,X_{i+1})=(x,y)).
\]
Similarly, $\pi_x$ is estimated by 
\[
\hp_x = \frac{1}{n}\si c_{xi} \quad\mbox{with}\quad c_{xi} = \1(X_i=x).
\]
We may assume w.l.g.\ that $\pi_x$ is positive.
Then the transition probability $Q_{xy}=R_{xy}/\pi_x$ can be estimated by
$\hQ_{xy}=\hR_{xy}/\hp_x$. These estimators are easily shown to be efficient
if no structural assumptions on $Q$ are made; see Penev (1991)
or Greenwood and Wefelmeyer (1995). General differentiable functionals
of higher-order stationary laws $\pi_{x_1}Q_{x_1 x_2}\dots Q_{x_r x_{r+1}}$
are estimated efficiently by plugging in $\hp$ and $\hQ$ for $\pi$ and $Q$.

Suppose now that we do not observe the realizations of the chain successively,
but only with gaps of random length. Let us allow the probabilities 
of the different lengths to depend on the value of the last observation
before the gap. We will however assume that pairs of \emph{successive}
realizations are observed with positive probability. 
Then a simple estimator for $R_{xy}$ is the proportion of the pairs
$(X_i,X_{i+1})$ with values $(x,y)$ among all observed pairs.
We call this estimator again $\hR_{xy}$. Similarly, $\hp_x$
now denotes the proportion of observed visits to $x$. 
We will show that this simple estimator does not make efficient use
of the observations. We can exploit non-adjacent pairs $(X_i,X_{i+j})$
with gap $j>1$ in the following three ways. 

(1) If $X_i=x$, then the conditional expectation of $c_{xyi}$ given $X_i=x$ 
is the forward transition probability $Q_{xy}$.
We replace the unobserved indicator $c_{xyi}$ by the nonparametric estimator 
of $Q_{xy}$, i.e.\ by $\hc_{xyi}\hQ_{xy}=\hR_{xy}/\hp_x$. 

(2) If $X_{i+j}=y$, then the conditional expectation 
of $c_{xy,i+j-1}$ given $X_{i+j}=x$
is the backward transition probability $Q_{yx}^-=R_{xy}/\pi_y$.
We replace the unobserved indicator $c_{xy,i+j-1}$ 
by the nonparametric estimator of $Q_{xy}^-$, i.e.\
by $\hc_{xy,i+j-1}=\hQ_{yx}^-=\hR_{xy}/\hp_y$.

(3) If $j>2$ and $r\in\{2,\dots,j-1\}$, then the 
(backward and forward) conditional expectation
of $c_{xy,i+r-1}$ given $(X_i,X_{i+j})$ is
$Q_{X_i x}^{r-1}Q_{xy}Q_{X_{i+j}y}^{-(j-r)}$.
We replace the unobserved indicator $c_{xy,i+r-1}$ 
by the nonparametric estimator for this conditional expectation, i.e.\ by 
\bea
\hc_{xy,i+r-1} &= \hQ_{X_i x}^{r-1}\hQ_{xy}\hQ_{X_{i+j}y}^{-(j-r)} \\
&= \sum_{x_1,\dots,x_{r-2},x_{r+1},\dots,x_{j-1}}
\frac{\hR_{X_i x_1}\hR_{x_1 x_2}\cdots\hR_{x_{r-2}x}
\hR_{yx_{r+1}}\hR_{x_{r+1}x_{r+2}}\cdots\hR_{x_{j-1}X_{i+j}}}{
\hp_{X_i}\hp_{x_1}\cdots\hp_{x_{r-2}}\hp_{r+1}\cdots\hp_{X_{i+j}}}.
\ea

(4) At all other time points $i$ we see the pairs $(X_i,X_{i+1})$
and know the value of the indicator $c_{xyi}$. 
It is notationally convenient to set $\hc_{xyi}=c_{xyi}$ at these time points.
As estimator of $R_{xy}$ we now suggest the average
\[
\bar R_{xy} = \frac{1}{N}\sum_{i=1}^N\hc_{xyi},
\]
where $N$ is the last time at which we have observed a realization of the chain.
This estimator can also be thought of as a convex combination 
of the four averages over each of these four different types of
left observed, right observed, unobserved, and fully observed pairs
of successive observations. The unobserved pairs can further be sorted
according to the size of the gap and the position within the gap.
All these averages have, in general, different asymptotic variances
(and different sample sizes).

The estimator $\bar R_{xy}$ has smaller asymptotic variance than $\hR_{xy}$.
The improvement will be considerable if the probability
of observing pairs of successive observations is small.
We will show elsewhere that $\bar R_{xy}$ cannot be improved, asymptotically,
unless structural assumptions about the transition matrix $Q$ are made.

We can also show that the naive estimator $\bar R_{xy}$ is efficient
in the less informative model in which the observed blocks 
are \emph{independent} of each other. Then there is no information about $Q$
in in the pair $(X_i,X_{i+j})$ separated by an unobserved gap
(of length $j>1$). This is a different way of explaining the improvement
of $\bar R_{xy}$ over $\hR_{xy}$.

Our result can be generalized to Markov chains of order $p>2$.
This is straightforward if we never observe blocks of length
shorter than $p$. A new problem arises however if we want to use
the information across a gap after a shorter block,
because then we do not completely observe the realizations
of the chain on which the distribution of the observation after the gap
depends. 
--- We conclude the Introduction with three remarks on the literature
about time series with missing observations.

1. We call our observations ``missing at random'' in analogy 
with the usual concept of responses missing at random in regression models;
see e.g.\ Tsiatis (2006). There we have i.i.d.\ $(X_i,Y_i)$,
but do not observe the response $Y_i$ with a probability
that may depend on the covariate $X_i$ but not on the response itself.
In order to estimate an expectation $E[h(X,Y)]$,
we can then use an empirical estimator in which we impute
for $(X_i,Y_i)$ an estimator of the conditional expectation
$E(h(X_i,Y_i)|X_i)$. In our Markov chain setting,
we estimate $E[h(X_i,X_{i+1})]$ by an empirical estimator
that bridges a gap between times the $i$ and $i+j$ by estimators
of the conditional expectations $E(h(X_{i+r-1},X_{i+r})|X_i,X_{i+j})$
for $r=1,\dots,j$.

2. It is essential that pairs of successive observations occur
with positive probability. Suppose, for example, that we see the Markov chain
only at odd times $1,3,\dots$. Then the observations form a Markov chain
with transition distribution $Q^2$. We can estimate $Q^2$ 
from the odd observations, but the underlying transition matrix 
cannot be identified. M\"uller et al.\ (2008) discuss structural assumptions
on $Q$ that allow (partial) identification of $Q$ in such cases.

3. Most of the literature on missing data in time series is concerned
with interpolating plausible values for missing observations.
See e.g.\ Parzen (1963, 1984) and Pourahmadi (1989, 2001).
Our aim is not to interpolate the chain but to use the information
in the [\dots]

\section{Result}


Let $X_i$, $i\in\Z$, be a stationary and homogeneous first-order
Markov chain with finite state space $E=\{1,\dots,m\}$, transition matrix $Q$
and stationary vector $\pi$. Suppose that, after observing state $X_i=x$
at time $i$, our next observation is $X_{i+j}=y$, and 
conditional on $x$ the lag $j$ has multinomial probability $\mu(x,j)$ 
for $j=1,\dots,k$. We assume that we know the maximal length $k$ 
of the gaps but do not know the multinomial distribution $\mu(x,\cdot)$
for the gap lengths following state $x$. 
 

\section*{Acknowledgments}

Ursula U. M\"uller was supported by NSF Grant DMS 0907014.
%Anton Schick was supported by NSF Grant DMS 0906551.


\begin{thebibliography}{99}


\bibitem{gw95}
Greenwood, P. E. and Wefelmeyer, W. (1995).
Efficiency of empirical estimators for Markov chains,
\emph{Annals of Statistics} \textbf{23}, 132--143.

\bibitem{msw08}
M\"uller, U. U., Schick, A. and Wefelmeyer, W. (2008).
Estimators for partially observed Markov chains.
In: {\em Statistical Models and Methods for Biomedical and Technical Systems} 
(F. Vonta, M. Nikulin, N. Limnios and C. Huber-Carol, eds.), 419--433, 
Birkh\"auser, Boston.

\bibitem{pa1963}
Parzen, E. (1963). 
On spectral analysis with missing observations and amplitude modulation. 
\emph{Sankhy\={a} Ser.\ A} \textbf{25}, 383--392. 

\bibitem{pa84}
Parzen, E., ed.\ (1984).
\emph{Time Series Analysis of Irregularly Observed Data}, 
Lecture Notes in Statist. \textbf{25}, Springer, New York.

\bibitem{pe91}
Penev, S. (1991).
Efficient estimation of the stationary distribution for exponentially 
ergodic Markov chains.
\emph{J. Statist.\ Plann.\ Inference} \textbf{27}, 105--123. 

\bibitem{po89}
Pourahmadi, M. (1989).
Estimation and interpolation of missing values of a stationary time series. 
\emph{J. Time Ser.\ Anal.} \textbf{10}, 149--169.

\bibitem{po01}
Pourahmadi, M. (2001).
\emph{Foundations of Time Series Analysis and Prediction Theory}, 
Wiley Series in Probability and Statistics: Applied Probability and Statistics, Wiley-Interscience, New York.

\bibitem{ts06}
Tsiatis, A. A. (2006).
\emph{Semiparametric Theory and Missing Data},
Springer Series in Statistics,
Springer-Verlag, New York.

\end{thebibliography}

\end{document}


A simple estimator for the probability
$R_{xy}=\pi_x Q_{xy}$ of visiting successively states $x$ and $y$
is the empirical estimator
$\hR_{xy}$

\b\n ----------------------------------------------------------------------
 
The distribution of a stationary (first-order) Markov chain is described 
by its transition distribution $Q(x,dy)$, 
its two-dimensional joint distribution 
$\pi \otimes Q(dx,dy) = \pi(dx) \otimes Q(x, dy)$, where $\pi(dx)$ is the
(marginal) stationary distribution. 
Hence the distribution of the chain, and therefore its parameters, is 
determined by sufficiently many expectations $Eh(X_{0}, X_1)$, say for a basis 
of functions $h$ in $L_2(\pi \otimes Q)$.
These can be estimated from observations $X_0,\dots,X_n$ by empirical 
estimators 
$$
\EE h = \frac1n \sum_{i=0}^{n-1} h(X_{i}, X_{i+1}).
$$
In many applications, the chain can only be observed at certain random time
points. Suppose we have observed $X_i$. Then we assume
that our next observation will be $X_{i+j}$,
where $j$ is chosen according to a multinomial probability 
$\mu(X_i, j)$, possibly depending on the previous observation $X_i$,
with $j = 1,\dots, k$. For simplicity
we assume that the maximum size $k$ of the gaps between our observations
is known. Note that here we count the gap between two adjacent time points
$i$ and $i+1$ as one. If $E\mu(X_i, 1) >0$, we can still 
consistently estimate expectations $Eh(X_0,X_1)$.
For example, if $S_1 \subset \{1,\dots,n-1\}$ is the set of time points $i$
such that the pair $X_i, X_{i+1}$ is observed, then an estimator for 
$Eh(X_0,X_1)$ is the empirical estimator
$$
\EE_1 h = \frac1{|S_1|} \sum_{i \in S_1} h(X_{i}, X_{i+1}),
$$
where $\|S \|$ denotes the cardinality of a set $S$.
We expect, however, that this does not fully use the information contained
in our observations. It should be possible to exploit the information
in isolated observations as well. 
For a brief introduction into various random and deterministic patterns
of missingness and corresponding estimation problems we refer to
M\"uller et al.\ (2008). In this paper we describe a method that 
is related to the one used in regression models with responses missing 
at random. Then we have independent copies of $(X,Y)$ and always observe $X$,
but observe $Y$ only with some probability possibly depending on $X$.
The naive estimator for an expectation $Eh(X,Y)$ is the empirical 
estimator based on the observed pairs $(X_i,Y_i)$. A better estimator 
is the partially imputed empirical estimator that replaces 
$h(X_i, Y_i)$ by an estimator for the conditional expectation 
$E(h(X,Y)|X)$ if $Y_i$ is missing. For a comparison of partial and 
full imputation see M\"uller et al.\ (2006).

In our Markov chain setting we use the observations $(X_i,X_{i+j})$ 
separated by a fixed gap $j>1$ as follows. 
For our estimator we must assume that there is positive probability of
seeing the next observation, $E\mu(X,1)>0$. We suppose that the
state space is the real line and that the transition distribution
$Q(x,dy)$ has a Lebesgue density $q(x,y)$. Then the stationary
distribution $\pi(dx)$ also has a density, say $m(x)$. 
Write $p(x,y) = m(x)q(x,y)$ for the joint density of two successive
realizations of the underlying Markov chain. 
For $r \in \{1,\dots,j\}$ we can write
$$
Eh(X_0, X_j) = EQ_h^{jr}(X_0,X_j)
$$
with
\bea
Q_h^{jr}(X_0,X_j)
&= E(h(X_{r-1}, X_r)|X_0, X_j)
\\& =
\frac1{q^j(X_0, X_j)} \int \cdots \int 
q(X_0,y_1) \cdots h(y_{r-1}, y_r) \cdots q(y_{j-1}, X_j) dy_1 
\cdots dy_{j-1}
\\& =
\frac1{q^j(X_0, X_j)} \int \cdots \int 
\frac{p(X_0,y_1) \cdots h(y_{r-1}, y_r) \cdots p(y_{j-1}, X_j)}
{m(y_1) \cdots m(y_{j-1})}
dy_1 \cdots dy_{j-1}.
\ea
Similarly we write 
$$
q^j(X_0,X_j)
= 
\int \cdots \int 
\frac{p(X_0,y_1) \cdots p(y_{j-1}, X_j)}
{m(y_1) \cdots m(y_{j-1})}
dy_1 \cdots dy_{j-1}.
$$
Let $\hat Q_h^{jr}(X_0,X_j)$ be an estimator for $Q_h^{jr}(X_0,X_j)$.
It can be obtained by replacing the one-dimensional 
stationary density $m$ appearing in $Q_h^{jr}$ by a kernel estimator
$\hat m$ based on all observations, and the  two-dimensional
stationary density $p$ by a kernel estimator $\hat p$ based on
the observed pairs of successive realizations $X_i$ and 
$X_{i+1}$ of the underlying Markov chain. 
Let $S_j \subset \{1,\dots, n-j\}$ be the set of time points $i$
such that $(X_i, X_{i+j})$ is observed. For $j=1,\dots,k$
and $r=1,\dots,j$ we now have new ``empirical'' estimators for
$Eh(X_0,X_1)$, namely 
$$
\EE_{jr}h = \frac1{|S_j|} \sum_{i \in S_j}
\hat Q_h^{jr}(X_i,X_{i+j}).
$$
We can use any convex combination of the estimators 
$\EE_1h$ and $\EE_{jr}h$ to estimate $Eh(X_0, X_1)$.
The optimal weights depend on the distribution of the chain and must 
be estimated. We show in Section 3 that the resulting estimator 
for $Eh(X_0, X_1)$ is asymptotically efficient in the sense of
H\'ajek and Le Cam. This requires proving local asymptotic normality
for Markov chain models with missing observations, which we prove
in Section 2. In Section 4 we apply the results of Section 2
to first-order linear autoregressive models
$
X_i = \vt X_{i-1} + \ve_i,
$
where the innovations $\ve_i$ are independent and identically distributed
with mean zero and finite variance.
[Degenerate because $Q^j$ is again AR; the construction is then different.]


\section{Characterization of efficient estimators}

Let $X_i$, $i \in \ZZ$, be a stationary and homogeneous (first-order) Markov
chain with arbitrary state space $(E, \E)$, transition distribution 
$Q(x,dy)$ and (marginal) stationary distribution $\pi(dx)$. 
First we introduce some notation. 
For each $x$ let $\mu(x, \cdot)$ be a multinomial distribution
on $\{1, \dots, k\}$. For a function $v(x,j)$ we write 
$\mu(x,u) = \sjk u(j)$ and $\mu u = \mu(\cdot, u)$, and set
$$
U = \{ u \in L_2(\pi \otimes \mu): \mu u =0\}.
$$
For a function $u(x,y)$ we write 
$$
Q(x,v) = \int Q(x, dy) u(x,y),  \quad
Q^j(x,v) = \int Q^{j-1}(x,dy) \int Q(y, dz) u(y,z)
$$
and $Qv = Q(\cdot, v)$, and set
$$
V = \{ v \in L_2(\pi \otimes Q): Qv =0\}.
$$
For $r = 1,\dots, j$ we will also need
$
D^{jr}_v(X_i, X_{i+j}) 
= E[v(X_{r-1}, X_r)|X_i, X_{i+j}],
$
which can be written
$$
D^{jr}_v(x, z) = \frac{d Q^{jr}_v(x,\cdot)}{d Q^{j}(x,\cdot)}(z).
$$
Here, for $r=2,\dots,j-1$, we define $Q^{jr}_v$ as the signed conditional 
measure
\bea
Q^{jr}_v(x,B) =
&\int \cdots \int Q(x,dy_1) \cdots Q(y_{j-2}, d y_{j-1}) Q(y_{j-1},B) 
v(y_{r-1},y_r)
\\ &=
\iiint Q^{r-1}(x, d y_{r-1})  Q(y_{r-1}, d y_{r}) 
v(y_{r-1},y_r) Q^{j-r}(y_r, B),
\ea
and for $r=1$ and $r=j$ we set
\bea
Q^{j1}_v(x,B) &=
\iint Q(x, d y) v(x,y) Q^{j-1}(y, B),
\\
Q^{jj}_v(x,B) &=
\iint Q^{j-1}(x, d y)  Q(y, d z) 
v(y,z) \1_B(z).
\ea
It is easy to check that $Q^j D^{jr}_v =0$.

Now we describe the mechanism that generates our observations.
Our initial observation is $X_0$.
Choose $J_1$ from the multinomial distribution $\mu(X, \cdot)$.
Then our next observation of the Markov chain is $X_{J_1}$. 
The transition distribution from $X_0$ to $X_{J_1}$ is $Q^{J_1}(X_0, \cdot)$.
Continuing in this way for $i=1,2, \dots$, we obtain observations 
$(J_i,X_{S_i})$ with $S_i = J_1 + \cdots + J_i$.
We assume that the sample size is $N = N_n$, where $N/n \to c >0$ in 
probability as $n \to \infty$.
(For example we stop observing the original chain after time $n$.
Then $N$ is the maximum number $i$ such that $S_i \le n$.)
Let $N_j = |\{t : J_t = j\}|$. Then
$$
\frac{N_j}N \to \int \pi(dx) \mu(x,j) = \mu_j.
$$
Hence
$$
\frac{N_j}n = \frac{N_j}N \frac Nn \to c \mu_j.
$$

The transition distribution from $(J_{i-1}, X_{S_{i-1}})$
to $(J_{i}, X_{S_{i}}) = (j,y)$ is 
$$
\mu(X_{S_{i-1}},j) Q^j(X_{S_{i-1}},dy).
$$
This transition distribution is similar to the transition distribution
$Q(X_i,dy)R(X_i,X_{i+1},ds)$ of a Markov renewal process $(X_i, T_i)$, where
$Q$ is the transition distribution of the embedded Markov chain $X_i$,
and $R(X_i,X_{i+1}, ds)$ is the conditional distribution of the waiting 
time $T_{i+1}-T_i$ given $X_i$ and $X_{i+1}$. For local asymptotic normality
of Markov renewal processes see Greenwood et al.\ (2004). The essential
difference to our Markov chains with missing observations is that now
the transition distribution $Q^j$ \emph{depends} on the waiting time $j$,
and the underlying transition distribution $Q$ cannot be estimated
directly from pairs of observations generated by $Q^j$, but only
indirectly via imputation as described in Section 1.

To prove local asymptotic normality we introduce local parameters
for $\mu$ and $Q$. 
For a function $u$ in $U$ choose a sequence of conditional 
multinomial distributions $\mu_{nu}$ that is Hellinger differentiable 
at $\mu$ with derivative $u$ in the sense that
\[
\int \sjk \Big( \Big( \frac{\mu_{nu}(x,j)}{\mu(x,j)}\Big)^{1/2}
-1 - \frac12 n^{-1/2}u(x,j)\Big)^2 \, \mu(x,j) \pi(dx) 
= o(n^{-1}).
\]
For a function $v$ in $V$ 
choose a sequence of transition distributions $Q_{nv}$ that is
Hellinger differentiable at $Q$ with derivative $v$ in the sense that
\[
\iint \Big( \Big( \frac{d Q_{nv}(x,\cdot)}{d Q(x,\cdot)}(y)\Big)^{1/2}
-1 - \frac12 n^{-1/2}v(x,y)\Big)^2 \, Q(x,dy) \pi(dx)
= o(n^{-1}).
\]
Note that $u(X_{S_{t-1}}, J_t)$ and $v(X_{S_{t-1}}, X_{S_t})$
are uncorrelated, 
$$
E[u(X_{S_{t-1}}, J_t) v(X_{S_{t-1}}, X_{S_t})]
=
\int \pi(dx) \sjk \mu(x,j) v(x,j) \int Q^j(x,dy) v(x,y) =0.
$$
Let $P_n$ and $P_{nuv}$ denote the distributions of the observations 
$X_0, (J_1, X_{S_1}), \dots, (J_N, X_{S_N})$ under $(\mu, Q)$ and
$(\mu_{nu}, Q_{nv})$, respectively. 
Set $J_0=0$ and $S_0=0$. Then the likelihood ratio is 
$$
\frac{d P_{nuv}}{d P_n} 
= \frac{d \pi_{nv}}{d \pi} (X_0) \prod_{t=1}^N 
\frac{\mu_{nu}(X_{S_{t-1}}, J_t)} {\mu(X_{S_{t-1}}, J_t)} 
\frac{d Q^{J_t}_{nv}(X_{S_{t-1}}, \cdot)}{d Q^{J_t}(X_{S_{t-1}}, \cdot)} 
(X_{S_t}).
$$
\thmref{lan} below gives a stochastic expansion for the logarithm 
of the likelihood ratio, which is called \emph{local asymptotic normality}.
We must assume that the stationary distribution depends
continuously on the local parameter in the following sense,
\bel{cont}
\int \Big| \frac{d \pi_{nv}}{d \pi}(x) -1 \Big| \pi(dx) \to 0.
\ee
This is usually satisfied. We also use the following abbreviations,
\bea
S_n(u,v) 
&=
n^{-1/2}
\sum_{t =1}^N u(X_{S_{t-1}}, J_t) 
+
n^{-1/2}
\sjk \mu_j \sum_{t:J_t =j} \sum_{r=1}^{j} D^{jr}_v(X_{S_{t-1}},X_{S_{t}}),
\\  
\| u \|^2
&=
c \, \pi \otimes \mu(u^2), \qquad
\| v \|^2_j 
=
c \mu_j \sum_{r,s=1}^j \pi \otimes Q^j(D_v^{jr}D^{js}_v).
\ea


%Let $Y^j_1, Y^j_2, \dots$ denote the consecutive $X_{S_t}$ 
%for which $J_t = j$, i.e.\ those observations which are preceeded
%by a gap of length $j$.


\Thm{lan} 
Let $\mu_{nu}$ and $Q_{nv}$ be Hellinger differentiable at $\mu$ and $Q$
with derivatives $u$ and $v$, respectively. Assume that \Ref{cont} holds.
Then
\bea
\log \frac{d P_{nuv}}{d P_n} 
 =
S_n(u,v) 
- \frac12 ( \|u\|^2 + \|v\|_1^2 + \cdots + \|v\|_k^2)
+ \op
\ea
and $S_n(u,v) \Rightarrow ( \|u\|^2 + \|v\|_1^2 + \cdots + \|v\|_k^2) N,$ 
where $N$ is a standard normal random variable.
\end{theorem}

\n
{\bf Proof.}
Rearranging the product according to the values of $J_t$, we obtain
the following representation for the logarithm of the likelihood ratio,
$$
\log \frac{d P_{nuv}}{d P_n} 
=
\log \frac{d \pi_{nv}}{d \pi} (X_0)
+ \sum_{t=1}^N \log
\frac{\mu_{nu}(X_{S_{t-1}}, J_t)} {\mu(X_{S_{t-1}}, J_t)} 
+ \sjk \sum_{t:J_t =j} 
\log
\frac{d Q^{j}_{nv}(X_{S_{t-1}}, \cdot)}{d Q^{j}(X_{S_{t-1}}, \cdot)} 
(X_{S_t}).
$$
By \Ref{cont}, the first term converges to zero in probability.
By assumption, $N/n \to c$ and $N_j/n \to c \mu_j$ in probability.
By Hellinger differentiability and standard arguments for proving local 
asymptotic normality, we obtain the second-order stochastic expansion 
\bel{m}
 \sum_{t=1}^N \log
\frac{\mu_{nu}(X_{S_{t-1}}, J_t)} {\mu(X_{S_{t-1}}, J_t)} 
=
n^{-1/2}
\sum_{t =1}^N u(X_{S_{t-1}}, J_t) 
- \frac12 \|u\|^2 + \op.
\ee
For $j=1,\dots, k$ we can write
\bea
& Q_{nv}^j(x,dz) 
= \int \cdots \int Q_{nv}(x,dy_1)  \cdots Q_{nv}(y_{j-1}, dz)
\\ &=
\int \cdots \int Q(x,dy_1)  \cdots Q(y_{j-1}, dz)
\big(1+n^{-1/2}v(x,y_1)\big) \cdots \big(1+n^{-1/2}v(y_{j-1},z)\big).
\ea
Neglecting higher-order powers of $n^{-1/2}$ we see that $Q_{nv}^j$
is Hellinger differentiable at $Q^j$ with derivative 
$\sum_{r=1}^j D_v^{jr}$, i.e.
\[
\iint \Big( \Big( \frac{d Q_{nv}^j(x,\cdot)}{d Q^j(x,\cdot)}(z)\Big)^{1/2}
-1 - \frac12 n^{-1/2}
\sum_{r=1}^j D_v^{jr}(x,z)\Big)^2 \, Q^j(x,dz) \pi(dx)
= o(n^{-1}).
\]
Again by standard arguments,
\bel{q}
 \sum_{t:J_t =j} \log
\frac{d Q^{j}_{nv}(X_{S_{t-1}}, \cdot)}{d Q^{j}(X_{S_{t-1}}, \cdot)} 
(X_{S_t}) 
= n^{-1/2} \sum_{t:J_t =j} \sum_{r=1}^{j} D^{jr}_v(X_{S_{t-1}},X_{S_{t}}) 
- \frac12 \|v\|_j^2 + \op.
\ee
By a martingale central limit theorem, the random variables in \Ref{m}
and \Ref{q} are asymptotically normal. 
Since $u(X_{S_{t-1}}, J_t)$ and $v(X_{S_{t-1}}, X_{S_t})$
are uncorrelated, the random variables in \Ref{m} and \Ref{q} are also 
asymptotically independent. Furthermore, for different $j$, we have
taken $D_v^{j1}, \dots, D_v^{jj}$ at different pairs of observations,
namely those with gap $j$. Hence the $k$ random variables in \Ref{q}
are asymptotically independent. It follows that the asymptotic variance of 
$\log dP_{nuv}/dP_n$ is the sum of the $1+k$ asymptotic variances of
the random variables in \Ref{m} and \Ref{q}, and the assertion follows.



\bibitem{am08}
A\"\i t-Sahalia, Y. and Mykland, P. A. (2008).
An analysis of Hansen-Scheinkman moment estimators for discretely 
and randomly sampled diffusions. 
\emph{J. Econometrics} \textbf{144}, 1--26.

\bibitem{bkrw98}
Bickel, P. J., Klaassen, C. A. J., Ritov, Y. and Wellner, J. A. (1998).
\emph{Efficient and Adaptive Estimation for Semiparametric Models.} 
Springer, New York. 

\bibitem{gw95}
Greenwood, P. E. and Wefelmeyer, W. (1995).
Efficiency of empirical estimators for Markov chains,
\emph{Annals of Statistics} \textbf{23}, 132--143.

\bibitem{gmw04}
Greenwood, P. E., M\"uller, U. U. and Wefelmeyer, W. (2004).
Efficient estimation for semiparametric semi-Markov processes,
\emph{Communications in Statistics Theory and Methods} \textbf{33}, 419--435.

\bibitem{h93}
H\"opfner, R. (1993). 
On statistics of Markov step processes: 
representation of log-likelihood ratio processes in filtered local models. 
\emph{Probab. Theory Related Fields} \textbf{94}, 375--398.

\bibitem{hjl90}
H\"opfner, R., Jacod, J. and Ladelli, L. (1990).
Local asymptotic normality and mixed normality for Markov statistical models. 
\emph{Probab.\ Theory Related Fields} \textbf{86}, 105--129.

\bibitem{lr02}
Little, R. J. A. and Rubin, D. B. (2002).
\emph{Statistical Analysis With Missing Data}, Second Edition,
Wiley Series in Probability and Statistics,
Wiley-Interscience, Hoboken, NJ.

\bibitem{mt93}
Meyn, S. P. and Tweedie, R. L. (1993).
\emph{Markov Chains and Stochastic Stability},
Communications and Control Engineering Series,
Springer-Verlag, London.

%\bibitem{Ka85a}
%Kartashov, N. V. (1985a).
%Criteria for uniform ergodicity and strong stability of Markov chains
%with a common phase space.
%\emph{Theory Probab.\ Math.\ Statist.} \textbf{30}, 71--89.

%\bibitem{Ka85b}
%Kartashov, N. V. (1985b).
%Inequalities in theorems of ergodicity and stability for Markov chains
%with common phase space. I.
%\emph{Theory Probab.\ Appl.} \textbf{30}, 247--259.

%\bibitem{Ka96}
%Kartashov, N. V. (1996). 
%\emph{Strong Stable Markov Chains.}
%VSP, Utrecht.

%\bibitem{ks97}
%Kitamura, Y. and Stutzer, M. (1997).
%An information-theoretic alternative to generalized method of moments 
%estimation. 
%\emph{Econometrica} \textbf{65}, 861-874.

%Kitamura, Y. (2001). [independent]
%Asymptotic optimality of empirical likelihood for testing moment restrictions. %\emph{Econometrica} \textbf{69}, 1661--1672.

%\bibitem{msw01}
%M\"uller, U. U., Schick, A. and Wefelmeyer, W. (2001).
%Improved estimators for constrained Markov chain models.  
%\emph{Statist.\ Probab.\ Lett.} \textbf{54}, 427--435.


\bibitem{msw06}
M\"uller, U.\ U., Schick, A.\ and Wefelmeyer, W.\ (2006).
Imputing responses that are not missing. 
In: {\em Probability, Statistics and Modelling in Public Health}
 (M.\ Nikulin, D.\ Commenges and C.\ Huber, eds.), 350--363, Springer,
New York.

\bibitem{msw08}
M\"uller, U. U., Schick, A. and Wefelmeyer, W. (2008).
Estimators for partially observed Markov chains.
In: {\em Statistical Models and Methods for Biomedical and Technical Systems} 
(F. Vonta, M. Nikulin, N. Limnios and C. Huber-Carol, eds.), 419--433, 
Birkh\"auser, Boston.

%\bibitem{msw11}
%M\"uller, U. U., Schick, A. and Wefelmeyer, W. (2011).
%Variance bounds for estimators in autoregressive models with constraints.
%To appear in: \emph{Statistics}.

%\bibitem{mw02}
%M\"uller, U. U. and Wefelmeyer, W. (2002).
%Estimators for models with constraints involving unknown parameters.  
%\emph{Math.\ Methods Statist.} \textbf{11}, 221--235.

\bibitem{pa1963}
Parzen, E. (1963). 
On spectral analysis with missing observations and amplitude modulation. 
\emph{Sankhy\={a} Ser.\ A} \textbf{25}, 383--392. 

\bibitem{pa84}
Parzen, E., ed.\ (1984).
\emph{Time Series Analysis of Irregularly Observed Data}, 
Lecture Notes in Statist. \textbf{25}, Springer, New York.

\bibitem{pe91}
Penev, S. (1991).
Efficient estimation of the stationary distribution for exponentially 
ergodic Markov chains.
\emph{J. Statist.\ Plann.\ Inference} \textbf{27}, 105--123. 

\bibitem{ts06}
Tsiatis, A. A. (2006).
\emph{Semiparametric Theory and Missing Data},
Springer Series in Statistics,
Springer-Verlag, New York.

\bibitem{VLR}
Van der Laan, M. J. and Robins, J. M. (2003).
\emph{Unified Methods for Censored Longitudinal Data and Causality},
Springer Series in Statistics, Springer-Verlag, New York.


\end{thebibliography}

\end{document}



