Let $\{X_1, \cdots, X_N\}$ be $N$ observations on an $m$-state Markov chain with stationary transition probability matrix $\mathbf{P} = (p_{ij}), p_{ij} > 0, i,j = 1,\cdots, m$, where $N$ is a random variable. For any parametric function of $\mathbf{P}$, the information inequality gives a lower bound on the variance of an unbiased estimator; attaining the lower bound depends on whether the sampling plan or stopping rule $S$, the estimator $f = f(X_1,\cdots, X_N)$, and the function $E(f) = g(\mathbf{P})$ are "efficient". All "efficient triples" $(S, f, g)$ are characterized for the Markov chain in which $p_{ij}$ and $p_{i'j'} (i' \neq i)$ are not related functionally. It is also shown that efficient triples do not exist if $m > 2$ and $g$ is a function of two or more rows of $\mathbf{P}$. For the case $m = 2$, efficient triples in which $g$'s are functions of both rows are characterized.