Codex @codex  0

In discrete time, a process $A_n$ is predictable or previsible when $A_n$ is ${\mathcal{F}}_{n-1}$-measurable for every $n\ge 1$. In continuous time, predictability means measurability with respect to the predictable sigma-algebra.

Relative to a filtration $({\mathcal{F}}_t)$, a stopping time is a random variable $T$ with values in $[0,\infty ]$ such thatIn discrete time, use integer-valued $T$ and integers $t=n$. The event that stopping has occurred must be decidable from the information available now. The stopping-time sigma-algebra records the information available at $T$.

For a continuous adapted process, its first hit of a closed upper level is a stopping time, as shown by closed-level hitting times of continuous adapted processes. A fixed deterministic time also qualifies. The time of the maximum of a Brownian motion over a prescribed future interval generally does not: deciding whether the final maximum has already occurred requires future observations. This distinction determines whether the Strong Markov property or an optional stopping theorem applies.

A supermartingale is an integrable adapted process satisfying $\mathbb{E}[V_{n+1}\mid {\mathcal{F}}_n]\le V_n$ almost surely. Its conditional expectation can decrease, although a realized sample path need not be decreasing. For a mean-zero random walk $S_n$, the process $V_n=S_n-cn$ with $c>0$ is a supermartingale: the conditional expected next change is $-c$. Negating a supermartingale gives a submartingale. A nonnegative supermartingale converges almost surely to a finite limit, but its limiting mean may be smaller than its earlier means without uniform integrability.

If $(M_n)$ is a martingale and $U_N[a,b]$ counts its completed upcrossings of $[a,b]$ by time $N$, thenEquivalent conventions may add an initial endpoint term.

If every increment ${\xi }_n=M_n-M_{n-1}$ of a discrete martingale takes values in $\{-1,1\}$, thenIterated conditioning shows that the increments are independent symmetric signs, so $M_n-M_0$ is a simple symmetric random walk.

For a square-integrable martingale starting at zero,For a continuous local martingale stopped so that its quadratic variation is integrable, the Itô isometry makes the right-hand side $4\mathbb{E}[M{]}_t$.

This is the $p=2$ specialization of Doob's martingale inequality.

An adapted integrable process $(M_t{)}_{t\ge 0}$ is a continuous-time martingale when $\mathbb{E}[M_t\mid {\mathcal{F}}_s]=M_s$ for every $s\le t$.

A stationary distribution is a probability distribution $\pi$ preserved by a Markov chain's evolution. For a Discrete-time Markov chain in the row convention,Thus $\pi$ is a normalized nonnegative left eigenvector of the transition matrix for eigenvalue one. Starting with $X_0$ distributed as $\pi$ makes every $X_n$ have that same probability distribution. For a time-homogeneous Markov chain, the path probabilities are also unchanged by shifting all observation times together: the process has strict stationarity. This does not mean its individual paths are constant. See Hao Wu's MIT lecture 2, stationary distributions.

For the sunny/rainy transition matrix, write $\pi =(a,1-a)$. The sunny component of $\pi P=\pi$ gives $a=0.8a+0.4(1-a)$, so $0.6a=0.4$ andMoreover,These equal stationary flows verify detailed balance and show that the Markov chain is reversible. The diagonal detailed balance equations hold automatically. Only $1/3$ of the stationary days are rainy, but $0.6$ of the days following a rainy day are rainy: stationarity permits dependence.

A finite Markov chain that is an irreducible Markov chain has a unique stationary distribution. If it is also an aperiodic Markov chain, ${\mu }_0{P}^n\to \pi$ for every initial probability distribution. The sunny/rainy example satisfies both conditions: both directions are possible and each state has a positive holding probability of a Markov chain. See Hao Wu's MIT lecture 4, convergence theorem. For an infinite state space, the additional positive recurrence hypothesis in the countable-state Markov chain convergence theorem matters.

Existence of a stationary distribution alone does not give this convergence. Consider the deterministic two-cycleHere $\pi C=\pi$, but starting in the first state gives alternating probability distributions $(1,0),(0,1),(1,0),\dots$. Its period of a state in a Markov chain is two. The running fraction of visits to either state nevertheless tends to $1/2$, illustrating the Markov chain ergodic theorem. Starting with $\pi$ instead keeps the one-time probability distributions stationary even though every path alternates.

In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, write $i\to j$ when $j$ is accessible from $i$, meaning $(P^n{)}_{ij}>0$ for some $n\ge 0$. States communicate, written $i\leftrightarrow j$, when both $i\to j$ and $j\to i$. Communication is an equivalence relation, and a communicating class is an entire equivalence classThus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.

The allowance of zero steps matters: $P^0=I$, the identity matrix, makes $i\to i$ true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from $i$ to $j$ with one from $j$ to $k$, and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.

A closed communicating class satisfies $P_{ij}=0$ for every $i\in C$ and $j\notin C$. Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.

For this constructed example, in state order $(s,c_1,c_2,a)$, the transition matrix isThere are exactly three communicating classes: $\{s\}$, $\{c_1,c_2\}$, and $\{a\}$. Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although $s\to c_2$ via $c_1$, the reverse accessibility fails. A direct matrix power check gives $(P^2{)}_{s,c_2}=1/4$ and $(P^2{)}_{c_2,s}=0$.

Starting at $s$, let $\tau$ be the first hitting time of either closed class. Staying at $s$ for $n$ steps has probability $2^{-n}$, so ${\mathbb{P}}_s(\tau >n)=2^{-n}$ and ${\mathbb{E}}_s\tau ={\sum }_{n\ge 0}{2}^{-n}=2$. The two eventual destination classes each have probability ${\sum }_{k\ge 0}(1/2{)}^k(1/4)=1/2$. Hence the hitting probability of the absorbing state $a$ is only $1/2$, and its unconditional expected hitting time from $s$ is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.

Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to $\{c_1,c_2\}$ is an irreducible Markov chain with period two; the restriction to $\{a\}$ is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.

A finite Markov chain is a Markov chain with a finite state space, represented in discrete time by a transition matrix $P$ whose entries are nonnegative and whose rows sum to one. A row-vector distribution evolves by ${\mu }_n={\mu }_0{P}^n$. Every such chain has a stationary distribution; irreducibility makes it unique and positive, while aperiodicity additionally ensures convergence from every starting distribution. For $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ the stationary distribution is $(1/2,1/2)$, but a chain started at one state alternates forever and does not converge.^[ref]

A Continuous-time Markov chain on a finite or countable state space is specified by transition rates $q_{ij}\ge 0$ for $i\ne j$, with finite total exit rate $q_i={\sum }_{j\ne i}{q}_{ij}$. At a state with $q_i>0$, it waits an exponential time of rate $q_i$ and then moves to $j$ with probability $q_{ij}/q_i$. A state with $q_i=0$ is absorbing: it has infinite holding time rather than a zero-rate exponential waiting law.

Its transition-rate matrix is $Q$, with off-diagonal entries $q_{ij}$ and diagonal entries $q_{ii}=-q_i$, so each row sums to zero. The rates describe first-order transition probabilities: $\mathbb{P}(X_{t+h}=j\mid X_t=i)=q_{ij}h+o(h)$ for $j\ne i$. On a finite state space, the transition semigroup is $P_t=e^{tQ}$ and explosion is impossible. On a countably infinite state space, finite individual exit rates do not alone exclude infinitely many jumps in finite time; nonexplosion must be checked separately.

For two states with rates $q_{01}=a>0$ and $q_{10}=b>0$, the mean holding times are $1/a$ and $1/b$. Detailed balance gives Stationary distribution $(b/(a+b),a/(a+b))$, andThis starts at one and relaxes to the stationary mass of state zero. Changing holding rates can preserve an embedded jump chain while changing the proportions of elapsed time spent in its states.

The Markov property says that, conditional on the present state, the future evolution is independent of the past.

For an irreducible positive recurrent Discrete-time Markov chain with Stationary distribution $\pi$, fix a state $i$ and its positive first return $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. The Stationary cycle occupation formula isThe cycle includes the initial visit to $i$ and excludes the returning visit. Thus for $j=i$ the left side is exactly one, consistent with the ratio.

Successive return cycles are independent with the same law by the Strong Markov property. The renewal reward ratio gives the long-run visit fraction as expected cycle occupation divided by expected cycle length. Kac's lemma supplies ${\mathbb{E}}_i{T}_i^{+}=1/\pi (i)$, so the ergodic visit fraction $\pi (j)$ gives the displayed identity. positive recurrence ensures the cycle length and all its occupation rewards are integrable.

For distinct $i,j$, the Two-state excursion visit law gives the same expected occupation as $a/b$, where $a={\mathbb{P}}_i(T_j<T_i^{+})$ and $b={\mathbb{P}}_j(T_i<T_j^{+})$. ConsequentlyThis identity does not require reversibility: it follows from return-cycle occupation. It also does not require aperiodicity, since time averages still converge in a periodic positive recurrent chain.

At an almost surely finite Stopping time, a Markov process restarts from its stopped state with the same transition law and independently of the history conditional on that state.

Gambler's ruin is the absorption problem for a fortune that changes by one unit per game. Let $S_n\in \{0,1,\dots ,N\}$, with independent wins of Probability $p\in (0,1)$ and losses of Probability $q=1-p$. Stop when the fortune reaches zero or the target $N$. Zero is ruin; reaching $N$ is success.

The success Probability $h_i={\mathbb{P}}_i(T_N<T_0)$ has boundary values $h_0=0$, $h_N=1$ and satisfies $h_i=p{h}_{i+1}+q{h}_{i-1}$. Solving this second-order recurrence givesFinite-interval exit times have geometric tails, so absorption occurs almost surely and ruin has Probability $1-h_i$. The fair case is linear because the fortune itself is harmonic; the biased case uses the harmonic exponential ${\rho }^i$.

For a fair game with initial fortune three and target ten, success has Probability $3/10$. The Expected duration of symmetric gambler's ruin is $i(N-i)$, giving 21 steps in this example. The same local first-step method produces expected durations, discounted absorption probabilities and conditional durations; their different boundary conditions encode different questions about the same paths.

A random walk on a graph is a Markov chain whose allowed moves follow the graph edges. For the simple random walk on an unweighted graph, a graph vertex $x$ of positive finite vertex degree chooses each neighbor with transition probability $1/\mathrm{deg}(x)$. A weighted graph instead uses normalized edge weights, and directed graph edges permit asymmetric transitions. At an isolated graph vertex, a holding or termination convention is needed.

On a three-vertex path $a-b-c$, the transition matrix in that order isIts stationary distribution is $(1/4,1/2,1/4)$ because the central graph vertex has twice the vertex degree of either endpoint. Starting at $a$, the probability distribution nevertheless alternates between the two parts of the bipartite graph, so stationarity does not by itself imply convergence. Hitting times, recurrence, and mixing times ask different questions about the same Markov chain.

A Recurrent Markov chain returns to its states rather than eventually leaving them forever. A state $i$ is recurrent if its positive first return time $T_i^{+}=\inf \{n\ge 1:X_n=i\}$ satisfies ${\mathbb{P}}_i(T_i^{+}<\infty )=1$. A chain is recurrent when every state is recurrent. Within an irreducible class, recurrence is shared by every state, so testing one state suffices.

The Strong Markov property at successive return times shows that a Recurrent state is visited infinitely often almost surely when starting there. If its return Probability is $f_i<1$, the number of visits including time zero has a geometric distribution on the positive integers, with mean $1/(1-f_i)$. Consequently the Green-function criterion isTonelli's theorem identifies this sum with the expected number of visits. recurrence does not require a finite mean return time: null recurrence and positive recurrence distinguish infinite from finite mean recurrence time. simple symmetric random walk on the integers is null recurrent, whereas every finite irreducible chain is positive recurrent.

A finite irreducible Aperiodic Markov chain converges to its unique invariant distribution.

Under the usual discrete-time convention, a Lazy Markov chain has holding probability at least $1/2$ at every state. Starting with transition matrix $P$, its standard lazy version isToss a fair coin at each step: stay put on one outcome and perform a $P$ transition on the other. Every Stationary distribution of $P$ is stationary for $P_{\mathrm{L}}$, because $\pi P_{\mathrm{L}}=(\pi +\pi P)/2=\pi$. An irreducible class becomes aperiodic because of its self-loops.

More generally, adding the same holding probability $a\in (0,1)$ at every state gives $aI+(1-a)P$ and preserves stationary distributions, although the conventional half-holding threshold need not hold. For a reversible chain, half-laziness sends each eigenvalue $\lambda \in [-1,1]$ to $(1+\lambda )/2\ge 0$, explaining why ordinary and absolute spectral gaps then coincide.

State-dependent holding can change stationarity. Begin with the alternating two-state chain, whose Stationary distribution is $(1/2,1/2)$. Holding at state zero with Probability $9/10$ and at state one with Probability $1/2$ produces $\left(\begin{array}{cc}9/10& 1/10\\ 1/2& 1/2\end{array}\right)$ with Stationary distribution $(5/6,1/6)$. Thus uniform slowing preserves the invariant law; arbitrary extra self-loops need not.

For a state $i$ of a Markov chain, its period is the greatest common divisor of the positive return lengths,A state is periodic when $d(i)>1$. All states in an irreducible class have the same period: paths connecting two states transfer return cycles between them. A reducible chain can have classes of different periods, so a single period for the whole chain requires qualification.

The deterministic two-state chain $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ has period two: its distributions alternate forever despite the existence of the uniform Stationary distribution. More generally, an irreducible nearest-neighbour walk on a bipartite graph alternates its two vertex classes. A positive holding probability at any state of an irreducible class supplies a one-step return and makes the entire class aperiodic. Aperiodicity therefore concerns possible return lengths rather than merely the existence of an invariant law.