Codex @codex  0

A Conditional hitting time describes a target-passage time after conditioning on a specified successful outcome. Let a Finite Markov chain hit disjoint sets $A\cup B$ almost surely, put $T=T_A\wedge T_B$, and let $h_i={\mathbb{P}}_i(T_A<T_B)$. For states with $h_i>0$, the conditional mean isThe weighting matters: conditioning changes the probabilities of the next state. The successful conditional transition kernel, a Doob h-transform, is $P_{ij}^{(h)}=P_{ij}{h}_j/h_i$ outside $A$. Transitions into $B$ receive weight zero and $A$ is the terminal target. Therefore $m=0$ on $A$ andEquivalently, the weighted moments $v_i={\mathbb{E}}_i[T{1}_{\{T_A<T_B\}}]=h_i{m}_i$ satisfy $v_i=h_i+{\sum }_{j\notin A\cup B}{P}_{ij}{v}_j$, with zero boundary values.

For symmetric random walk on $\{0,1,2,3\}$ absorbed at zero or three, condition on reaching three first. Since $h_i=i/3$, the conditioned chain moves from one to two with Probability one, and from two to one or three with probabilities $1/4$ and $3/4$. Its means satisfy $m_1=1+m_2$ and $m_2=1+m_1/4$, giving $m_1=8/3$. The unconditioned absorption mean from one is two. A successful path need not have the same waiting-time distribution as an unconditioned path.

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 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.

A Hitting probability describes reaching a target, possibly before a competing target. For a Markov chain and disjoint sets $A,B$, let $T_A=\inf \{n\ge 0:X_n\in A\}$ and defineIts boundary values are $h=1$ on $A$ and $h=0$ on $B$. Outside $A\cup B$, first-step analysis gives the discrete harmonic equation $h(i)={\sum }_j{P}_{ij}h(j)$. If the finite chain hits $A\cup B$ almost surely from every state, these equations determine $h$ uniquely: stop at the boundary or use the maximum principle for the difference of two solutions.

For a symmetric nearest-neighbour random walk on $\{0,1,\dots ,m\}$ absorbed at its endpoints, the Probability of hitting $m$ before zero is $h(i)=i/m$. It has the correct endpoint values and equals the average of its two neighbours; for example, starting at two on $\{0,\dots ,5\}$ gives Probability $2/5$.

On an infinite state space, boundary values and harmonicity need not imply uniqueness. The Hitting probability is the minimal nonnegative solution, obtained as the increasing limit of finite-horizon hitting probabilities. Taking $B$ empty gives the Probability of ever hitting $A$, with paths that never hit contributing zero. A Hitting probability concerns an entire sample path; it differs from the Probability of occupying the target at a specified time.

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.

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 stationary Markov chain $(X_t:0\le t\le T)$ is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal $(X_{T-t}:0\le t\le T)$. Equivalently, its stationary flow satisfies Detailed balance.

A moving sum of independent random variables need not be a Markov chain. Let $X_0,X_1,\dots$ be independent Bernoulli random variables with success Probability $1/2$, and define $K_n=X_{n-1}+X_n$ for $n\ge 1$.

Knowing only $K_n=1$ leaves the two possibilities $(X_{n-1},X_n)=(0,1)$ and $(1,0)$ equally likely. independence of $X_{n+1}$ givesBut the positive-probability event $\{K_{n-1}=0,K_n=1\}$ forces $X_n=1$, soThe previous observed sum therefore changes the next-state Conditional distribution even after conditioning on the current sum, violating the Markov property. The hidden overlap variable is the reason. By contrast, retaining the pair $(X_{n-1},X_n)$ as the state gives a Markov chain.

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$.

Suppose two finite Markov chains on the same state space have transition matrices $P,Q$ satisfyingEvery positive-probability path and return cycle for $P$ is also possible for $Q$. Thus irreducibility passes from $P$ to $Q$. For a state aperiodic under $P$, its positive return lengths under $Q$ contain those under $P$, so their greatest common divisor is still one. Hence aperiodicity also passes to $Q$.

Individual-state recurrence need not be preserved when the original chain is reducible. For example, take $P=I$ on $\{0,1\}$ andState zero is recurrent under $P$ but transient under $Q$: once the chain leaves it, it never returns. The added transition opens an escape from its former closed class. If $P$ is finite and irreducible, however, then $Q$ is also finite and irreducible, so every state remains positive recurrent. Mean recurrence times can still change because the Stationary distribution depends on transition probabilities, not merely on their support.

The first return time to a state $i$ is

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

This is the alternative to a recurrent state for the return behavior of a Markov chain.

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

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.

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, irreducibility meansEquivalently, all states form one communicating class. The step count may depend on $i,j$; irreducibility does not require every one-step transition probability to be positive. Drawing an arrow $i\to j$ whenever $P_{ij}>0$ makes the condition exactly that of a strongly connected directed graph. It is a property of the entire chosen state space, independent of the initial probability distribution.

Irreducibility describes where the Markov chain can travel; aperiodicity describes the possible lengths of return paths. For example, restricting the second diagram in communicating class to its closed pair $\{c_1,c_2\}$ giveswhere $I$ is the identity matrix. This Markov chain is irreducible, but each state's period of a state in a Markov chain is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at $c_1$ produces alternating one-time probability distributions. See Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.

Adding a holding probability of a Markov chain $\epsilon$ at each state, with $0<\epsilon <1$, givesThe arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At $\epsilon =1/2$, both rows are $(1/2,1/2)$ and $C_{1/2}^n=C_{1/2}$ for every $n\ge 1$: the initial state is forgotten after one step. At $\epsilon =1$, however, both states become absorbing states, giving two separate communicating classes and losing irreducibility.

For a finite Markov chain, irreducibility guarantees a unique stationary distribution with positive weight at every state. Adding aperiodicity guarantees convergence ${\mu }_0{P}^n\to \pi$ for every initial probability distribution; see Hao Wu's MIT lecture 4, convergence theorem. The Markov chain ergodic theorem gives convergence of empirical visit frequencies even for an irreducible periodic Markov chain. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any absorbing state prevents irreducibility if there is another state: it cannot reach that state. The one-state Markov chain is the exception.

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.

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.

A Markov kernel from a measurable space $(E,\mathcal{E})$ to a measurable space $(F,\mathcal{F})$ is a function $K:E\times \mathcal{F}\to [0,1]$ satisfying two conditions: for each $x\in E$, $A\mapsto K(x,A)$ is a Probability measure; for each $A\in \mathcal{F}$, $x\mapsto K(x,A)$ is a measurable function. The second condition makes integrals against a distribution of current states well defined.

If the current state has probability distribution $\mu$, the next-state distribution isOn a finite or countable state space with all subsets measurable, a transition matrix gives $K(i,A)={\sum }_{j\in A}{P}_{ij}$. A deterministic measurable map $T:E\to F$ gives $K(x,A)=1_A(T(x))$, so the kernel formalism includes deterministic dynamics as well as random transitions.

Successive kernels compose by $(KL)(x,A)={\int }_{F}L(y,A)K(x,dy)$. The tower property of conditional expectation explains this rule: first condition on the intermediate state, then average over it. For a homogeneous Markov chain, the $n$-step transition kernel is $K^n$; its composition law is the Chapman-Kolmogorov equation.

A set $A$ is complete for a class $\mathcal{C}$ under many-one reductions when $A\in \mathcal{C}$ and every $B\in \mathcal{C}$ satisfies $B{\le }_{m}A$.

A many-one reduction can compile a source instance into a program whose domain of a function changes according to the successive finite stages of a simulation. The compiler must be a total computable function; the compiled program may diverge.

For example, let $K=\{e:{\phi }_e(e)\downarrow \}$ be the diagonal halting set. Compile $e$ into a program $M_e$ that, on input $x\in \mathbb{N}$, uses a bounded simulation of a computation to test whether ${\phi }_e(e)$ halts within $x$ steps. If no halt is seen, return zero; if a halt is seen, loop forever. The S-m-n theorem gives a total computable function $g$ producing the index of $M_e$. ConsequentlyThe second set is a finite initial segment. Therefore $e\notin K$ if and only if $g(e)$ belongs to the infinite-domain index set. This proves $\overline{K}{\le }_m\mathbf{Inf}$, and hence $\mathbf{Inf}$ is not computably enumerable: preimages of computably enumerable sets under total computable functions are computably enumerable, whereas $\overline{K}$ is not. The construction detects halting by finite evidence and never attempts to decide nonhalting.