Markov process

A Markov process is a stochastic process for which, conditional on the present state, the future is independent of the past. Its transition probabilities therefore determine every finite-dimensional distribution once the initial distribution is known.

A Markov chain has a future conditional distribution depending on the present state alone.

A Markov kernel $K(x,\cdot )$ assigns a probability distribution to each current state $x$ and acts on a distribution $P$ by $(PK)(A)=\int K(x,A)P(dx)$.

A birth-death chain is a discrete-time Markov chain on nonnegative integers that can move only to the same state or a neighbouring state.

Independent Markov chains with transition matrices $P$ and $Q$ form a product chain with transition matrix $P\otimes Q$. If their stationary distributions are $\pi$ and $\rho$, the product distribution $\pi \otimes \rho$ is stationary.

The transition matrix of a finite Markov chain has entries

A Markov chain is irreducible when every state can reach every other state along a path of positive-probability transitions.

A state is aperiodic when the greatest common divisor of its positive-probability return times is one. A Markov chain is aperiodic when all its states are aperiodic.

A state is recurrent when a Markov chain started there returns to it with probability one.

A state is transient when its probability of ever returning is less than one.

The first return time to a state $i$ is

The mean recurrence time of $i$ is ${\mathbb{E}}_i{T}_i^{+}$. In a finite irreducible Markov chain with stationary distribution $\pi$, it equals $1/{\pi }_i$.

If two finite Markov chains satisfythen every positive-probability path and return cycle for $P$ also exists for $Q$. Consequently irreducibility and aperiodicity pass from $P$ to $Q$. Recurrence and mean return time need not do so, because the added transitions and changed probabilities can create escape routes or make returns less frequent.

For independent random variables with a common law, $L_n={\min }_{j\le n}{X}_j$ satisfies $L_{n+1}=\min (L_n,X_{n+1})$. The next-state law therefore depends on the past only through $L_n$.

For i.i.d. Bernoulli variables, $K_n=X_{n-1}+X_n$ hides which summand is the newest one. Given $K_n=1$, the previous value can reveal $X_n$ and thereby change the conditional law of $K_{n+1}$, so $(K_n)$ need not be a Markov chain.

A Markov chain is reversible when its stationary flow satisfies detailed balance.

Detailed balance is the identity pi_i P_ij = pi_j P_ji for every pair of states.

For a reversible transition matrix $P$ with invariant distribution $\pi$,

For a transient weighted graph, $H_0$ is the completion of the finitely supported functions in the norm $\Vert f{\Vert }_{H_0}=\mathcal{E}(f,f{)}^{1/2}$. Its elements have finite Dirichlet energy and vanish at infinity in the energy sense.

The relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap: $t_{\mathrm{rel}}=(1-{\lambda }_2{)}^{-1}$.

The spectral profile minimizes a Dirichlet-form Rayleigh quotient over nonnegative functions supported on sets of stationary mass at most $r$.

For the isoperimetric profile ${\Phi }_{\ast }(r)$ of a reversible chain and $r\le 1/2$,

For a reversible Markov chain with stationary flow $Q(x,y)=\pi (x)P(x,y)$, the conductance of a set $A$ isIts Cheeger constant minimizes the boundary flow divided by the smaller stationary mass of the two sides of the cut.

The Cheeger constant of a finite reversible chain is the least stationary boundary flow divided by the smaller stationary mass of a set and its complement.

For a reversible chain with spectral gap $\gamma$ and Cheeger constant $\Phi$,

The $\epsilon$-mixing time is the least $t$ for which every initial state has total variation distance at most $\epsilon$ from the invariant distribution after $t$ steps.

A randomized stopping time $\tau$ is a strong stationary time for a Markov chain with stationary distribution $\pi$ when $X_{\tau }$ has distribution $\pi$ and is independent of $\tau$. Equivalently,

For a finite Markov chain with stationary distribution $\pi$, the separation distance from an initial state $x$ isIf $\tau$ is a strong stationary time, then $s_x(t)\le {\mathbb{P}}_x(\tau >t)$, and total variation distance is at most separation distance.

For a finite transitive reversible chain with nontrivial eigenvalues ${\lambda }_i$,

A sequence of chains exhibits cutoff when its distance from stationarity drops from near one to near zero in a time window negligible compared with its mixing-time scale.

If adjacent states admit one-step couplings that contract a path metric by a common factor, then the induced Wasserstein distance contracts by the same factor for arbitrary starting distributions.

A lumped Markov chain records only a partition class of the original state. It is Markov when the transition probability into every class is constant within each source class.

A hitting probability is the probability of reaching one set before another and solves a discrete harmonic boundary problem.

Suppose an urn starts with $m$ green balls and $m+2$ red balls. Drawing green removes one green ball, while drawing red adds one green and one red ball. The difference remains two, and $h(g)=1/(g+1)$ is harmonic for the green-ball chain. Stopping $h$ on hitting $0$ or $N$ and then letting $N$ tend to infinity gives termination probability

For a target set $A$, the expected hitting time $g(i)={\mathbb{E}}_i{T}_A$ satisfies $g=0$ on $A$ andoutside $A$, whenever the expectation is finite.

The expected number $u(i)$ of visits to a state $k$ before absorption satisfies the reward equationwith zero boundary data at absorbing states where counting stops.

For the chain with $0$ absorbing, equal-probability nearest-neighbour moves between $1,2,3$, and a probability-$1/2$ self-loop at $3$, starting from $1$ the expected absorption time is $6$, the probability of visiting $3$ before $0$ is $1/3$, and the expected number of visits to $3$ before absorption is $2$.

A conditional hitting time measures time to a target under a specified successful hitting event and can be computed by weighted first-step equations.

A periodic chain can return to a state only at times sharing a common divisor greater than one.

A lazy chain stays put with positive probability, removing periodicity without changing invariant distributions.

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

A state is recurrent when the chain returns to it almost surely after starting there.

A recurrent state is positive recurrent when its expected return time is finite.

A recurrent state is null recurrent when its expected return time is infinite.

A state is recurrent exactly when the sum over time of its return probabilities diverges.

For nearest-neighbour random walk on ${\mathbb{Z}}_{+}$ with upward probability $p>q$, the probability of ever hitting zero from $i$ is $(q/p{)}^i$.

A random walk is a stochastic process formed by successive random steps.

A random walk on a graph moves along an incident edge at each step.

A weighted graph assigns a symmetric nonnegative conductance ${\mu }_{xy}$ to each edge. With killing weights ${\kappa }_x$, the associated discrete-time walk moves from $x$ to $y$ with probability ${\mu }_{xy}/{\mu }_x$ and is killed with probability ${\kappa }_x/{\mu }_x$, where ${\mu }_x={\kappa }_x+{\sum }_y{\mu }_{xy}$.

The killing measure assigns the weight ${\kappa }_x$ of the transition from $x$ to a cemetery state.

An electrical network is a weighted graph whose edge weights are interpreted as electrical conductances. Random-walk hitting quantities can then be expressed through voltages, currents, and effective resistance.

The effective resistance between vertices $a$ and $z$ is the voltage difference required to send one unit of current from $a$ to $z$.

Thomson principle says that effective resistance is the minimum energy among unit flows from $a$ to $z$:

If ${\Pi }_1,\dots ,{\Pi }_m$ are pairwise edge-disjoint cutsets separating $a$ from $z$ in an electrical network, then

For a random walk on a finite electrical network,

A bishop random walk moves uniformly among the current square and all chessboard squares sharing a diagonal with it.

A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.

For the walk on a weighted graph, the Green function normalized by vertex weight isSymmetry of the conductances makes $g(x,y)=g(y,x)$, and $\mathcal{E}(g(\cdot ,y),f)=f(y)$ for finitely supported $f$.

For simple random walk on ${\mathbb{Z}}^d$ with $d\ge 3$,Consequently the probability of ever hitting $x$ from the origin has the same order.

For a finite vertex set $A$, its equilibrium potential is $h_A(x)=P_x(H_A<\infty )$. It equals one on $A$, is harmonic off $A$, and belongs to the Dirichlet energy space with zero boundary at infinity.

The equilibrium measure is supported on $A$ and is given by

The capacity of a finite set is the total mass of its equilibrium measure of a finite set:Capacity is monotone under inclusion, though strict inclusion need not give strict inequality.

For a vertex $o$,

A last-exit decomposition partitions a transient path event according to the final visit to a finite set. Reversing the finite path before that visit and using detailed balance converts last-exit probabilities into hitting probabilities weighted by an equilibrium measure of a finite set.

A loop-erased random walk is the self-avoiding path obtained by chronologically erasing loops from a random-walk path.

Chronological loop erasure removes each loop from a finite or transient infinite path as soon as the loop is formed, producing a self-avoiding path.

On a finite undirected graph, the reversal of a loop-erased random walk from $x$ to $y$ has the law of a loop-erased random walk from $y$ to $x$. The uniform-spanning-tree path representation proves the identity.

A simple random walk on a locally finite graph chooses each neighbouring vertex with equal probability.

A simple random walk on ${\mathbb{Z}}^2$ visits its starting point infinitely often almost surely and hits every fixed vertex almost surely.

If the independent increments are $+1$ with probability $p$ and $-1$ with probability $q=1-p$, thenThus $\mathbb{E}{S}_n=n(p-q)$ and $\mathrm{var}(S_n)=4npq$.

For the symmetric walk and $V_{2n}=|\{0\le j\le 2n:S_j=0\}|$,Since the central binomial coefficient satisfies $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)/4^k\asymp k^{-1/2}$, this expectation is of order $\sqrt{n}$.

For $d$ independent symmetric walks on $\mathbb{Z}$, the probability that all are at the origin at time $2n$ isThe Borel-Cantelli lemmas therefore show that simultaneous returns occur only finitely often almost surely when $d\ge 3$.

On a finite undirected graph, stationary mass is proportional to vertex degree.

A biased nearest-neighbor walk steps right and left with unequal probabilities.

Let a discrete-time chain move up with probability $q$ and down with probability $p=1-q$ away from zero, while at zero it moves up with probability $q$ and stays with probability $p$. It is transient for $q>p$, null recurrent for $q=p$, and positive recurrent for $q<p$. In the positive-recurrent case its invariant distribution isand aperiodicity from the self-loop at zero implies convergence to this distribution.

Gambler's ruin studies a nearest-neighbour random walk stopped on reaching either endpoint of a finite interval.

For a symmetric random walk started at $i\in \{-a,\dots ,b\}$ and stopped on first reaching $-a$ or $b$, the mean duration isIn particular, ${\mathbb{E}}_{0}T=ab$. This follows either from the first-step recurrence or by stopping the martingale $S_n^2-n$.

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.

Let $a={\mathbb{P}}_i(T_j<T_i)$ and $b={\mathbb{P}}_j(T_i<T_j)$. Before returning to $i$, the chain visits $j$ zero times with probability $1-a$ and, for $k\ge 1$, exactly $k$ times with probabilityWhen $b>0$, the expected number of visits is $a/b$.

For an irreducible positive-recurrent Markov chain with invariant distribution $\pi$, the expected number of visits to $j$ during one return cycle from $i$ to $i$ isCombining this with the two-state excursion visit law gives

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

The time-homogeneous Markov property says that the conditional law of a future state depends only on the current state and the elapsed time, not on the current calendar time or earlier history.

A continuous-time Markov chain waits an exponential time of rate $q_i$ in state $i$ and then jumps according to probabilities $p_{ij}=q_{ij}/q_i$.

A finite-state process has generator $Q$ exactly when, for every function $f$ on the state space,is a martingale with respect to the process filtration.

A Q-matrix has nonnegative off-diagonal entries and row sums zero. Its diagonal entry is the negative total rate out of the state.

For a continuous-time Markov chain, $P_{ij}(t)={\mathbb{P}}_i(X_t=j)$ and the matrices satisfy $P(s+t)=P(s)P(t)$. On a finite state space with Q-matrix $Q$, $P(t)=e^{tQ}$.

For a finite-state continuous-time Markov chain with Q-matrix $Q$, the backward and forward equations are $P^{\prime }(t)=QP(t)$ and $P^{\prime }(t)=P(t)Q$, respectively.

A Markov reward model attaches a reward rate to each state and integrates it over the time spent there.

For transition rates $q_{nm}$, the generator acts on a function $f$ byWhenever the expectations are finite,Choosing polynomial functions $f$ gives differential equations for the moments.

Conditioned on a finite jump path $i_0,\dots ,i_n$, the holding times are independent exponentials with the corresponding rates. Multiplying the probability of occupying $i_n$ at time $t$ by $q_{i_n}$ turns its simplex density into a product symmetric under reversal of the time portions and the state sequence.

For $h>0$, the fixed-time skeleton has matrix $P(h)$. If $q_i$ is the holding rate, then for $nh\le t\le (n+1)h$,Thus ${\int }_0^{\infty }{p}_{ii}(t)dt$ diverges exactly when ${\sum }_n{p}_{ii}(nh)$ does, proving recurrence equivalence for an irreducible chain.

The jump chain records the successive states visited by a continuous-time Markov chain while discarding its holding times.

On $\mathbb{N}$, let the chain jump from every $i\ge 1$ to $i+1$ with probability $p$ and to $i-1$ with probability $1-p$, and jump from zero to one. It is recurrent exactly when $p\le 1/2$; at $p=1/2$ it is null recurrent.

For holding rates $q_i$, a measure $\pi$ satisfies $\pi Q=0$ exactly when ${\mu }_i=q_i{\pi }_i$ is invariant for the jump chain. Thus ${\pi }_i={\mu }_i/q_i$ when normalization is possible.

Even when the jump chain has invariant probability $\mu$, the continuous-time invariant measure ${\mu }_i/q_i$ may have infinite mass if holding rates become too small, producing infinite mean return time.

A recurrent jump chain with infinite invariant measure $\mu$ can yield a positive-recurrent continuous-time chain when ${\sum }_i{\mu }_i/q_i<\infty$.

If the jump chain visits a state of finite holding rate infinitely often, the sum of its independent positive holding times at that state diverges almost surely, preventing explosion.

Explosion occurs when infinitely many jumps take place in finite time.

Conditional on a jump path $(Y_n)$, if ${\sum }_{n}1/q_{Y_n}<\infty$, then the sum of exponential holding times has finite expectation and is finite almost surely.

Suppose a transient nearest-neighbour jump chain on $\mathbb{N}$ has uniformly bounded expected visits to each state and the holding rate at $i$ grows geometrically. Thenso the continuous-time chain explodes almost surely.

Under the generator convention, an invariant distribution satisfies $\pi Q=0$.