Reset-or-increment Markov chain ($P(0,1)=1,P(k,k+1)=p,P(k,0)=1-p(k\ge 1)$)

For $0<p<1$, consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing $q=1-p$, its stationary distribution isThe balance equations give ${\pi }_1={\pi }_0$ and ${\pi }_k=p{\pi }_{k-1}$ for $k\ge 2$; the geometric series normalizes the result, and the zero-state equation ${\pi }_0=q(1-{\pi }_0)$ agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability $q$, so its mean recurrence time is $1+1/q$. Return paths of lengths two and three also make it aperiodic.

Suppose each new unit block independently selects one of two columns with equal probability. On the taller column it increases the maximum height; on the shorter column it sticks level with the other column, leaving the maximum unchanged. If the columns have equal height, the next block increases the maximum. Their absolute height difference $D_n$ is the reset-or-increment Markov chain with $p=1/2$.

For the maximum height $H_n$, each increment obeys $H_n-H_{n-1}=1_{\{D_n>0\}}$. The stationary distribution has ${\pi }_0=1/3$. Applying the countable-state Markov chain ergodic theorem to the bounded indicator function of the positive states givesalmost surely, from any fixed finite starting configuration. The reward average depends only on whether a reset occurred, even though the difference chain has infinitely many states.