Discrete-time Markov chain ($\mathbb{P}(Y_{n+1}=j\mid {\mathcal{F}}_n)=P_{Y_{n}j}$)

A time-homogeneous Discrete-time Markov chain is a sequence of random variables $Y_0,Y_1,\dots$ indexed by nonnegative integers, with the displayed conditional probabilities. Here ${\mathcal{F}}_n$ is its natural filtration and $P$ is a row-stochastic transition matrix. The Markov property removes dependence on earlier observations once $Y_n$ is specified; the time-homogeneous Markov property makes $P$ independent of $n$.

Consider states $S$ (sunny) and $R$ (rainy), with the constructed transition matrixRows give today's state and columns tomorrow's, in order $S,R$. These numbers define an illustrative model, with one step interpreted as one day; they are not estimates of real weather. Let $q_n=\mathbb{P}(Y_n=S)$. The law of total probability gives the recurrence relationSubtracting $2/3$ makes the deviation multiply by $0.4$ at each step. ThusStarting sunny gives $q_0=1$, $q_1=0.8$, $q_2=0.72$ and $q_3=0.688$; starting rainy gives $q_0=0$ and $q_2=0.56$. The two predictions approach the same stationary distribution while retaining a shrinking trace of the initial probability distribution.

An expected hitting time answers a different question. Starting sunny, let $T_R=\inf \{n\ge 0:Y_n=R\}$. Every day before the first rain remains sunny, soThis geometric distribution has finite expected value. A first-step calculation gives $h_S=1+0.8h_S+0.2h_R$, with $h_R=0$, hence $h_S=5$ days. The same result follows from the geometric series ${\mathbb{E}}_S{T}_R={\sum }_{n\ge 0}0.8^n=5$. This is a mean waiting time, not a prediction that rain first occurs exactly five days later.

A probability row vector $\pi$ is a stationary distribution when $\pi P=\pi$. The Markov chain is reversible in that law when detailed balance holds: ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$. Multiplying those equations along a finite path gives equal forward and reversed stationary path probabilities.

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.