Aperiodic return times are eventually positive

Fix $x\in E$; first, $R_x\mathrm{\ne }\mathrm{\varnothing }$, so $d(x)\ge 1$. If $E=\{x\}$, then $p(x,x)=1$ by row stochasticity, so $1\in R_x$. If $E$ has at least two elements, fix $y\mathrm{\ne }x$; by [F4] and irreducibility there are $r,s\ge 0$ with $p^{(r)}(x,y)>0$ and $p^{(s)}(y,x)>0$, and since $x\mathrm{\ne }y$ the zero-step entries $p^{(0)}(x,y)$, $p^{(0)}(y,x)$ vanish, so $r,s\ge 1$. By [F3], $p^{(r+s)}(x,x)\ge p^{(r)}(x,y)p^{(s)}(y,x)>0$, so $R_x\mathrm{\ne }\mathrm{\varnothing }$. In either case $d(x)$ is a positive integer, and [F2] gives $d(x)=1$.

A finite $F\subseteq R_x$ with $1$ as its greatest common divisor exists. Start with any $a_1\in R_x$ and let $g:=a_1$. While $g>1$: since $1$ is the greatest positive integer dividing every element of $R_x$ by step 1.1 and [F1], $g$ cannot divide every element of $R_x$, so choose $b\in R_x$ with $g\nmid b$ and replace $g$ by $\gcd (g,b)$; then add $b$ to $F$. By [F5] the new value is a positive common divisor of $g$ and $b$, hence a divisor of $g$, and it is not $g$ because $g\nmid b$; a positive divisor of $g$ different from $g$ is strictly smaller than $g$. The positive integers $g$ strictly decrease at each update while remaining divisors of $a_1$, so the process stops after finitely many updates, and it stops only when $g=1$. The resulting finite set $F\subseteq R_x$ has iterative gcd $1$: every element of $F$ is divisible by no positive integer other than $1$ that also divides all other elements.

Let $a:=\min F$; then $a\in F$ and $a\ge 1$. Let $⟨F⟩$ be the set of nonnegative integer combinations of the elements of $F$. Every positive element of $⟨F⟩$ lies in $R_x$: this follows from [F1] and [F3] for sums of two return times, by induction for finite combinations, while the empty combination is $0$ and is excluded. Let $H$ be the set of residues modulo $a$ of the elements of $⟨F⟩$. Since $a\in F$, the element $a$ has residue $0$, so $H$ is the subgroup of $\mathbb{Z}\mathrm{/}a\mathbb{Z}$ generated by the residues of the elements of $F$. If $H$ were a proper subgroup, then $H$ would be the set of multiples of $h$ modulo $a$ for some divisor $h$ of $a$ with $1<h\le a$, so $h$ would divide every $f\in F$; as $a\in F$, the integer $h>1$ would then divide every element of $F$, contradicting step 2.1. Hence $H=\mathbb{Z}\mathrm{/}a\mathbb{Z}$, and for every residue $r$ there is $s_r\in ⟨F⟩$ with $s_r\equiv r(\mathrm{m}\mathrm{o}\mathrm{d}a)$.

Put $N_x:=\max (1,{\max }_{0\le r<a}{s}_r)$ and fix $n\ge N_x$. Let $r$ be the residue of $n$ modulo $a$. Then $n-s_r$ is a nonnegative multiple of $a$, so $n=s_r+\frac{n-s_r}{a}a$ belongs to $⟨F⟩$ and $n\ge 1$. By step 3.1, $p^{(n)}(x,x)>0$. Since $x$ was arbitrary this proves the first assertion.

Fix $u,v$. By irreducibility [F4] there is $r\ge 0$ with $p^{(r)}(u,v)>0$. Put $N_{u,v}:=r+N_v$, where $N_v$ is the threshold of step 4.1 for the state $v$. If $n\ge N_{u,v}$, then $n-r\ge N_v$, so $p^{(n-r)}(v,v)>0$, and [F3] gives $p^{(n)}(u,v)\ge p^{(r)}(u,v)p^{(n-r)}(v,v)>0$. If $u=v$ this recovers the first assertion; if $r=0$ then $u=v$.

Boundary cases. If $E=\mathrm{\varnothing }$ the statement is vacuous. The aperiodicity hypothesis is equivalent to $d(x)=1$ by [F2] and is used in step 2.1 to produce a smaller divisor; without it the conclusion can fail (a deterministic two-cycle has $p^{(n)}(x,x)>0$ only for even $n$). The argument uses $R_x\mathrm{\ne }\mathrm{\varnothing }$, ensured by irreducibility in step 1.1, and positive return times only, so the time-zero entry $p^{(0)}(x,x)=1$ plays no role. All steps are finite assertions about nonnegative entries and integer combinations; no choice principle, limit or renewal theorem is used, the display $p^{(n)}$ for $n=0$ is the identity entry, and both assertions are one-way implications.