[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]

Define [math]f(r)[/math] to be the smallest integer [math]n[/math] such that for all regular Markov chains with [math]r[/math] states, the [math]n[/math]th power of the transition matrix has all entries positive. It has been shown, that [math]f(r) = r^2 - 2r + 2[/math].

• Define the transition matrix of an [math]r[/math]-state Markov chain as follows: For states [math]s_i[/math], with [math]i = 1[/math], 2, \ldots, [math]r - 2[/math], [math]\mat {P}(i,i + 1) = 1[/math], [math]\mat {P}(r - 1,r) = \mat {P}(r - 1, 1) = 1/2[/math], and [math]\mat {P}(r,1) = 1[/math]. Show that this is a regular Markov chain.
• For [math]r = 3[/math], verify that the fifth power is the first power that has no zeros.
• Show that, for general [math]r[/math], the smallest [math]n[/math] such that [math]\mat {P}^n[/math] has all entries positive is [math]n = f(r)[/math].

Notes