[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Assume that an ergodic Markov chain has states [math]s_1, s_2, \ldots, s_k[/math]. Let [math]S^{(n)}_j[/math] denote the number of times that the chain is in state

[math]s_j[/math] in the first [math]n[/math] steps. Let [math]\mat{w}[/math] denote the fixed probability row vector for this chain. Show that, regardless of the starting state, the expected value of [math]S^{(n)}_j[/math], divided by [math]n[/math], tends to [math]w_j[/math] as [math]n \rightarrow \infty[/math]. Hint: If the chain starts in state [math]s_i[/math], then the expected value of [math]S^{(n)}_j[/math] is given by the expression

[[math]] \sum_{h = 0}^n p^{(h)}_{ij}\ . [[/math]]