2

I wonder if there is any irreducible, aperiodic, recurrent positive Markov chain $M_n$ taking values in $\mathbb{N}$ such that for some initial state $k_0$, $E_{k_0} M_n$ does not converge to $E_{X\sim \mu} X=\sum_{k\in\mathbb{N}}k\mu_k$, where $\mu$ is the (unique) invariant distribution. We assume $E_{X\sim \mu} X$ is finite.

All I have so far is that $M$ cannot be bounded, otherwise the total variation convergence implies the convergence of the expectations.

Papagon
  • 315
  • 2
    Here is a quick lower bound: For all positive integers $k$ we have $E[M_n]\geq \sum_{i=0}^k i P[M_n=i]$ so taking $n\rightarrow\infty$ gives $$\liminf_{n\rightarrow\infty}E[M_n]\geq \sum_{i=0}^k i \mu_i$$ and since this works for all positive integers $k$ we get $$\liminf_{n\rightarrow\infty}E[M_n]\geq \sum_{i=0}^{\infty} i \mu_i$$ – Michael Jul 04 '23 at 13:43
  • Define $c = \sum_{i=0}^{\infty} i \mu_i$ and assume $c<\infty$. I believe the elementary renewal theorem can be used to prove $\lim_{t\rightarrow\infty} \frac{1}{t}\sum_{n=0}^{t-1}E[M_n] = c$ and that, together with my first comment, would imply $\lim\inf_{n\rightarrow\infty} E[M_n]=c$. It may also be useful to note that if $\mu_j>0$ then we have the following finite upper bound that holds uniformly for all $n$: $$E[M_n|M_0=j]\leq \frac{c}{\mu_j}\quad \forall n \in {0, 1, 2, ...}$$ – Michael Jul 04 '23 at 16:44
  • Thanks, I don't understand though: you already proved above that the lim inf was $c$. The Cesaro-convergence does not grant that the limit is $c$. – Papagon Jul 04 '23 at 16:55
  • My first comment proves $\liminf_{n\rightarrow\infty} E[M_n]\geq c$. To prove the $\liminf$ is exactly $c$, suppose there is an $\epsilon>0$ such that $\liminf_{n\rightarrow\infty} E[M_n]\geq c + \epsilon$ (we want a contradiction). Then $E[M_n]\geq c + \epsilon/2$ for all sufficiently large $n$ so $$\liminf_{t\rightarrow\infty}\frac{1}{t}\sum_{n=0}^{t-1}E[M_n]\geq c+\epsilon/2$$ This contradicts what we know about $\frac{1}{t}\sum_{n=0}^{t-1}E[M_n]$. – Michael Jul 04 '23 at 20:23
  • Generally speaking, for any real-valued sequence ${a_k}{k=1}^{\infty}$ we have $$\left(\lim{k\rightarrow\infty} \frac{1}{k}\sum_{i=1}^ka_i=c\right)\implies \left(\left(\liminf_{k\rightarrow\infty} a_k\leq c \right)\mbox{and} \left(\limsup_{k\rightarrow\infty} a_k\geq c\right)\right)$$ – Michael Jul 04 '23 at 20:53

2 Answers2

3

This completes my previous answer, based on the comment by Papagon (and mainly using only Claim 2 and Lemma 1 of the previous).

The situation is that $\{M_t\}_{t=0}^{\infty}$ is an irreducible and aperiodic DTMC with finite or countably infinite state space $S$. Assume the DTMC is positive recurrent and let $(\pi_i)_{i \in S}$ be the stationary distribution (it is known to exist and to satisfy $\pi_i>0$ for all $i \in S)$. Let $f:S\rightarrow[0,\infty)$ be any nonnegative function.

Define $c \in [0, \infty) \cup \{\infty\}$ by $$ c = \sum_{i \in S} f(i) \pi_i$$

Claim 3: $$ \lim_{t\rightarrow\infty} E[f(M_t)|M_0=j] = c \quad \forall j \in S$$

Proof: First suppose $c=\infty$. Then the result holds by Lemma 1 of my previous answer.

Now suppose $c<\infty$. The result is easy when $S$ is finite, so assume $S$ is infinite and without loss of generality assume $S=\{1, 2, 3, ...\}$. For each positive integer $k$ define $g_k:S\rightarrow [0, \infty)$ by $$g_k(s) = f(s)1_{s>k} \quad \forall s \in S$$ [This function $g_k$ is inspired by the comment of Papagon.]

For each positive integer $k$ define $$ d_k = \sum_{s \in S} g_k(s)\pi_s = \sum_{s=k+1}^{\infty} f(s)\pi_s$$ Then $$ c = \sum_{s=1}^k f(s)\pi_s+ d_k$$ and since $c<\infty$ we get $d_k<\infty$ for all $k$ and $d_k\rightarrow 0$. Now by Claim 2 applied to the function $g_k$ we get for any $j \in S$: $$ E[g_k(M_t)|M_0=j]\leq \frac{d_k}{\pi_j} \quad \forall t \in \{0, 1, 2, ...\}$$ In particular $$ \boxed{E[f(M_t)1_{M_t>k}|M_0=j] \leq \frac{d_k}{\pi_j} \quad \forall t \in \{0, 1, 2, ...\}}$$ Then for all $t \in \{0, 1, 2, ...\}$ \begin{align} &E[f(M_t)|M_0=j]\\ &=E[f(M_t)1_{M_t\leq k}|M_0=j] + E[f(M_t)1_{M_t>k}|M_0=j]\\ &\leq E[f(M_t)1_{M_t\leq k}|M_0=j] + \frac{d_k}{\pi_j}\\ &=\sum_{s=1}^kf(s)P[M_t=s|M_0=j] + \frac{d_k}{\pi_j} \end{align} Taking $t\rightarrow\infty$ gives $$ \limsup_{t\rightarrow\infty} E[f(M_t)|M_0=j]\leq \sum_{s=1}^k f(s)\pi_s + \frac{d_k}{\pi_j}$$ This holds for all positive integers $k$ and so taking $k\rightarrow \infty$ and using $d_k\rightarrow 0$ gives $$ \limsup_{t\rightarrow\infty} E[f(M_t)|M_0=j]\leq \sum_{s \in S} f(s)\pi_s = c$$ Using this with Lemma 1 of the previous answer proves the result. $\Box$

Michael
  • 23,905
0

Here is a slight generalization of my above comments: Assume:

  • $\{M_t\}_{t=0}^{\infty}$ is an irreducible, aperiodic, discrete time Markov chain (DTMC).

  • State space $S$ is finite or countably infinite.

  • The DTMC is positive recurrent and has stationary mass function $(\pi_i)_{i\in S}$.

  • $f:S\rightarrow [0, \infty)$ is any nonnegative function.

It is well known that $\pi_i>0$ for all $i \in S$.

Claim 1: We have $$ \liminf_{t\rightarrow\infty} E[f(M_t)|M_0=j] = c \quad \forall j \in S$$ where $c$ is the (possibly infinite) constant defined by $c = \sum_{i \in S} f(i) \pi_i$.

Claim 2: If $c<\infty$ we have for all $j \in S$: $$ 0\leq E[f(M_t)|M_0=j]\leq \frac{c}{\pi_j} \quad \forall t \in \{0, 1, 2, ...\}$$

The two claims are proven below.

Lemma 1: For all $j \in S$ we have $\liminf_{t\rightarrow\infty} E[f(M_t)|M_0=j]\geq c$.

Proof: Fix $j \in S$. Order $S$ by $S = \{s_1, s_2, s_3, ...\}$. For each positive integer $k$ and each $t \in \{0, 1, 2, ...\}$ we have $$E[f(M_t)|M_0=j] \geq \sum_{i=1}^kf(s_i)P[M_t=s_i|M_0=j]$$ Taking a limit as $t\rightarrow\infty$ and using the fact that probabilities converge to the stationary mass function regardless of the initial condition gives $$ \liminf_{t\rightarrow\infty} E[f(M_t)|M_0=j]\geq \sum_{i=1}^k f(s_i)\pi_{s_i}$$ This holds for all positive integers $k$, so taking $k\rightarrow\infty$ gives the result. $\Box$

Note that Lemma 1 proves the main claim in the special case $c=\infty$, so from hereafter we assume $c<\infty$.

Proof of Claim 2: Let $\{M_t\}_{t=0}^{\infty}$ be a version of this DTMC when the intial state $M_0$ is chosen according to the stationary mass function $(\pi_i)_{i\in S}$. Then $P[M_t=i]=\pi_i$ for all $i \in S$ and all $t \in \{0, 1, 2, ...\}$. Then, for all $t \in \{0, 1, 2, ...\}$ we have
$$ E[f(M_t)] = \sum_{i\in S} f(i)\pi_i = c $$ On the other hand, given any $j \in S$ we have $$ E[f(M_t)] = \sum_{i \in S} E[f(M_t)|M_0=i]\pi_i\geq E[f(M_t)|M_0=j]\pi_j$$ Thus $c \geq E[f(M_t)|M_0=j]\pi_j$. $\Box$

Lemma 2: If $\{a_i\}_{i=1}^{\infty}$ is any sequence of real numbers and if $c \in \mathbb{R}$ then \begin{align} &\left(\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^na_i = c \right)\\ & \implies \left(\left( \liminf_{n\rightarrow\infty} a_n \leq c\right) \mbox{ and} \left(\limsup_{n\rightarrow\infty} a_n\geq c\right)\right) \end{align}

Proof: Omitted for brevity. $\Box$

Proof of Claim 1: It suffices to treat the remaining case $c<\infty$. It can be shown by the Elementary Renewal Theorem that for all $j \in S$ we have $$ \lim_{n\rightarrow\infty} \frac{1}{n}\sum_{t=0}^{n-1}E[f(M_t)|M_0=j] = c$$ Lemma 2 then implies $\liminf_{n\rightarrow\infty} E[f(M_t)|M_0=j] \leq c$. Combining this with Lemma 1 proves Claim 1. $\Box$

Michael
  • 23,905
  • For aperiodic DTMCs, it would would be counter-intuitive for $\liminf_{t\rightarrow\infty} E[f(M_t)|M_0=j]$ to be different from $\limsup_{t\rightarrow\infty} E[f(M_t)|M_0=j]$, but I cannot seem to get a proof that $\liminf=\limsup$ at this point. – Michael Jul 05 '23 at 16:45
  • A stochastic coupling argument between $M^{\pi}_t$ (which starts in steady state) and $M^j_t$ (which starts in state $j$) seems promising, but the problem is that certain conditional expectations that concern the meeting time would need to be shown to be bounded. – Michael Jul 05 '23 at 17:01
  • 1
    Thank you. I think your Claim 2 applied to $j=k_0$, $f(x)=x 1_{x>K}$ provides a uniform bound to $E(M_n 1_{M_n>K})$, and the other part, $E(M_n 1_{M_n\leq K})$, clearly converges to $E_{X\sim \mu}(X 1_{X\leq K})$, so it proves the result that the expectation does converge... – Papagon Jul 05 '23 at 17:23
  • Aha! I didn't think of that. So then my Claim 2 was really the main thing needed. I didn't need it to prove Claim 1 but I kept it in since it seemed generally useful. So Claim 1 can be strengthened to replace $\liminf$ with $\lim$. With $S={s_1, s_2, ...}$, define $g_k(s_i) = f(s_i)1_{i>k}$, then $d_k=\sum_{s_i:i>k}f(s_i)\pi_{s_i}$, so Claim 2 applied to $g_k$ gives $$ E[g_k(M_t)|M_0=j]\leq \frac{d_k}{\pi_j}$$ now if $\sum_{i \in S} f(s_i)\pi_i<\infty$ then $d_k\rightarrow 0$. And we don't need the Elementary renewal theorem anywhere. – Michael Jul 05 '23 at 23:31