Let $\{X_k: k = 0, 1, 2, \cdots\}$ be a Markov process with state space $(\mathscr{S}, \mathscr{B})$ and denote by $f$ a real-valued $\mathscr{B}$-measurable function on $\mathscr{S}$. In [1] and [6] it was shown that for a Markov process with a single ergodic class, if the transition probabilities $P(x, A) = P\lbrack X_1 \varepsilon A \mid X_0 = x\rbrack$ are stationary and satisfy Doeblin's condition ([2]), if the conditional moment generating function of $f, \int_{\mathscr{S}} e^{tf(y)} P(x, dy)$, satisfies a certain boundedness condition in $t$ uniformly in $x$ and if $\int_{\mathscr{S}}f(y)\pi(dy) = 0$ where $\pi$ is the unique stationary probability measure for the process, then an exponential bound exists for the convergence of $S_n = n^{-1}\lbrack f(X_1) + \cdots + f(X_n)\rbrack$ to zero which is independent of the initial probability measure. That is, for every $\epsilon > 0$ there exist positive constants $A$ and $\rho < 1$ such that for all initial measures $\nu$, $P_\nu\lbrack|S_n| \geqq \epsilon\rbrack \leqq A\rho^n\quad\text{for} n = 1, 2, \cdots.$ The purpose of this paper is to study the extent to which such a result holds when the Cesaro averages $n^{-1}\lbrack f(X_1) + \cdots + f(X_n)\rbrack$ are replaced by a more general class of averages $\sum^\infty_{k = 1} a_{n,k}f(X_k), n = 1, 2, \cdots$, where the infinite matrices $\{a_{n,k}\}$ satisfy the conditions (a) $\sum^\infty_{k = 1} |a_{n,k}| \leqq 1$ uniformly for $n = 1, 2, \cdots$; (b) $\lambda(n) = \max_k |a_{n,k}| \rightarrow 0$ as $n \rightarrow \infty$; (c) $\lim_{n \rightarrow \infty} \sum^\infty_{k = 1} a_{n,k} = 1$. Such matrices are called Toeplitz matrices (except that our Condition (b) is somewhat stronger than the one usually imposed, see e.g. [8]), and our concern will be with the rate at which the sequence of random variables $S_n = \sum^\infty_{k = 1} a_{n,k}f(X_k)$ tends to zero in probability as $n \rightarrow \infty$. We will obtain theorems analogous to those of [1] and [6] through a series of specializations of two basic theorems to be proved in Section 2. There, without the assumption of stationary transition functions, conditions are given under which for every $\epsilon > 0$, there exist positive constants $A$ and $\rho < 1$ such that for all initial measures $\nu$, \begin{equation*}\tag{0}P_\nu\lbrack|S_n| \geqq \epsilon\rbrack \leqq A\rho^{1/\lambda(n)},\quad n = 1, 2, \cdots.\end{equation*} Here $S_n$ is the Toeplitz average and $\lambda(n)$ is defined above in Condition (b). In Section 3, processes with stationary transition probabilities are studied and a condition on the conditional moment generating function of $f$ is introduced which is comparable to a condition introduced in [1] and which implies the first theorem of Section 2. In Section 4, Doeblin's condition is introduced and additional restrictions on the process and the Toeplitz matrices sufficient to yield (0) are considered. This study is a sequel to work begun in [3] and continued in [4] and [5]. For applications in which Toeplitz averages of stochastic processes are of interest and for further orientation on the subject of convergence rates for Toeplitz averages of random variables, the reader is referred to these papers.