markov chains
The Markov chain is the mathematical model of a system that moves among a set of states over time, where the next state depends only on the present state and not on the entire history, and it is the natural continuation of the stochastic processes and the probability distributions keywords of this series. A Markov chain is a sequence of random variables in which the future is conditionally independent of the past given the present, so that the system has no memory of anything before its current state, and this single assumption makes the analysis of the process tractable. Every fab is full of Markov chains in disguise: a piece of equipment that moves among its operating states, a wafer lot that progresses through a sequence of process steps, and a system that shifts between the working and the failed state all behave according to the same mathematics. The engineer who understands the Markov chain can predict the long-run behavior of such systems, find the probability of being in each state, and compute the expected time to a failure or to an absorbing state. This document develops the states and the transition matrix, the Chapman-Kolmogorov equations, the classification of states, and the steady state, and it shows how each applies to the equipment, the yield, and the reliability of a fab.
**The Markov property is the defining assumption of a Markov chain, and it states that the conditional distribution of the next state depends only on the current state and not on the earlier ones.** If the state of the system at time $n$ is $X_n$, then the Markov property says that the probability of $X_{n+1}$ given the entire history depends only on $X_n$, so that the past is forgotten once the present is known. This assumption is the memoryless structure that makes the chain tractable, and it is why a Markov chain is sometimes described as a system with no memory beyond its current state. The Markov property is a model assumption, and the engineer checks whether the real process is well described by it, which is often the case for a system whose dynamics depend only on its present configuration. The sequence of states is called a Markov chain when the Markov property holds, and it is described by its initial state and by the probabilities of moving from each state to each other state. The Markov property is the single idea that the entire theory of Markov chains is built upon. The engineer who identifies the Markov property in a system can apply the full machinery of the subject.
**The state space of a Markov chain is the set of all the states that the system can occupy, and it may be finite or countably infinite, although the finite case is the one used most in engineering.** Each state is a distinct condition of the system, such as the idle, processing, and failed states of a tool, or the working and the failed states of a component, and at any time the system is in exactly one of the states. The state space is the first object the engineer defines when building a Markov model, because the choice of states determines what the model can represent, and a good state definition captures the meaningful distinctions while keeping the model small. The transition probabilities give the chance of moving from one state to another in a single step, and together with the state space they completely determine the behavior of the chain. The transition probabilities from a given state to all the states sum to one, because the system must move to some state at each step. The state space and the transition probabilities are the two ingredients of a Markov chain. In a fab the engineer defines the states of a tool or a process carefully, because the states determine what the Markov model can say about the system.
**The transition matrix is the complete description of how a finite Markov chain moves among its states in a single step, and it collects all the transition probabilities into a single array.** The transition matrix $P$ has one row and one column for each state, and the entry $p_{ij}$ is the probability of moving from state $i$ to state $j$ in one step, so that the rows give the distribution of the next state from each present state. Every entry of the transition matrix is between zero and one, and every row sums to one, because the system must move somewhere at each step, and a matrix with these two properties is called a stochastic matrix. The transition matrix together with the initial distribution of the states completely determines the entire future behavior of the chain, because at each step the next state is chosen according to the row of the present state. The transition matrix is the compact and powerful representation that makes the Markov chain amenable to matrix algebra, and it is the object on which most of the calculations of the subject are performed. In a fab the engineer writes the transition matrix of a tool from its observed state-to-state frequencies, and then uses the matrix to predict the future. The transition matrix is the engine of the Markov chain.
**The Chapman-Kolmogorov equations give the probabilities of moving between states over several steps, and they are the fundamental tool for computing the multi-step behavior of a chain.** If $p_{ij}^{(n)}$ is the probability of moving from state $i$ to state $j$ in exactly $n$ steps, then the Chapman-Kolmogorov equation states that the two-step probability is the sum over all intermediate states of the product of the two one-step probabilities, and the general equation expresses the $n$-step probability in terms of a sum over an intermediate step. In matrix form, the $n$-step transition matrix is the $n$-th power of the one-step transition matrix, $P^n$, and its entries give the probabilities of the chain being in each state after $n$ steps from each starting state. The matrix power is the practical way to compute the multi-step probabilities, because the powers of a matrix can be computed efficiently, and they reveal how the chain mixes as it evolves. The Chapman-Kolmogorov equations are the basis of the analysis of the long-run behavior, because they connect the one-step transitions to the multi-step and the eventual steady state. In a fab the engineer uses the powers of the transition matrix to find the probability that a tool is failed after a given number of steps. The Chapman-Kolmogorov equations extend the single-step transitions to the whole future of the chain.
**The classification of states divides the states of a Markov chain into the recurrent, the transient, and the absorbing classes, and it determines the long-run structure of the chain.** A state is recurrent if the chain, once it leaves the state, eventually returns to it with probability one, and it is transient if there is a positive chance that the chain never returns to it. A state is absorbing if, once the chain enters it, it never leaves, and an absorbing state is a special recurrent state whose exit probabilities are all zero. The states of a finite chain partition into communicating classes, where two states are in the same class if the chain can go from each to the other, and within an irreducible chain all the states form a single class and are all recurrent. The classification determines whether the chain reaches a single steady state, whether some states are only visited occasionally, and whether the chain is eventually absorbed into a subset of states. In a fab the failed state of a component that is not repaired is absorbing, while the states of a repaired tool are all recurrent, and the classification tells the engineer which structure to expect. The classification of the states is the first step in analyzing any Markov chain.
**The period of a state is a property that controls how often the chain can return to the state, and a chain is aperiodic when it has no such cyclic restriction.** The period of a state is the greatest common divisor of the numbers of steps at which a return to the state is possible, and a state with period one is aperiodic, meaning that a return can happen at any large number of steps. A chain that is irreducible and aperiodic is said to be ergodic, and an ergodic chain has the important property that the chain converges to a unique stationary distribution regardless of where it starts. The periodicity matters because it governs whether the long-run distribution is reached smoothly, and a periodic chain, such as one that must alternate between two states, does not settle into a single limiting distribution in the same way. In a fab most process chains are aperiodic, because a system can return to a state at essentially any time, and so the ergodic theory applies. The concept of aperiodicity is what guarantees the convergence to a steady state. The engineer who verifies that a chain is ergodic can be sure that its long-run behavior is well defined.
**The stationary distribution of a Markov chain is the long-run distribution of the states, and it gives the proportion of the time the chain spends in each state over the long run.** A distribution $\pi$ is stationary if it satisfies the balance equation $\pi = \pi P$, meaning that the distribution does not change when the chain takes a step, and it can be found by solving this linear system together with the condition that the probabilities sum to one. For a finite irreducible and aperiodic chain, the chain converges to the stationary distribution from any starting state, so that the probability of being in a state after many steps approaches the corresponding entry of $\pi$ regardless of the initial state. The stationary distribution is the central result of the theory of Markov chains, because it answers the question of the long-run proportions that the engineer cares about, and it is computed by solving a system of linear equations. The balance equation $\pi = \pi P$ is the mathematical statement that the probability flow into each state equals the flow out of it in the steady state. In a fab the stationary distribution of a tool gives the long-run proportion of time that the tool spends idle, processing, and failed, which is the basis of the availability calculation. The stationary distribution is the long-run answer that the entire theory is built to produce.
**The absorbing chains are the Markov chains in which some states trap the chain forever, and they arise whenever a system can reach a terminal condition from which it cannot return.** In an absorbing chain the absorbing states are the terminal conditions, and the analysis focuses on the probability that the chain is absorbed in each absorbing state and on the expected number of steps until absorption. The fundamental matrix of an absorbing chain, which is the inverse of a certain submatrix of the transition matrix, gives both the expected time spent in each transient state and the absorption probabilities, so that the whole behavior of an absorbing chain is computed from this single object. The gambler's ruin problem is the classic absorbing chain, in which a gambler with a finite fortune bets repeatedly until reaching either a target fortune or ruin, and it is used to model processes that continue until one of two absorbing endpoints. In a fab an absorbing chain models a wafer lot that moves through process steps until it is either completed or scrapped, and a component that eventually fails, and the absorption probabilities give the chance of each terminal outcome. The absorbing chains model the processes that do not go on forever. The fundamental matrix and the absorption probabilities are the tools that the engineer uses on such chains.
**The random walk is the simplest and most instructive Markov chain, and it is the model of a quantity that takes unit steps up or down with fixed probabilities.** In a simple random walk the state is an integer, and at each step the walk moves up by one with probability $p$ and down by one with probability $1 - p$, so that the future of the walk depends only on its current position, which makes it a Markov chain. The random walk is the model of a fluctuating quantity, such as a cumulative error or a drifting process measurement, and its long-run behavior depends on the drift $p$: a symmetric walk with $p$ equal to one half is recurrent, while a walk with a drift is eventually absorbed or drifts away. The random walk is also the discrete-time building block of the Brownian motion that appears in the stochastic processes keyword, because a scaled random walk converges to Brownian motion, and it is the underlying process of the Markov chain Monte Carlo samplers. The expected position of a random walk grows with the drift, while its variance grows with the number of steps, so that the walk spreads out over time. In a fab a random walk models a measurement that wanders from a target, and the engineer watches for the drift that signals a process change. The random walk is the gentle introduction to the dynamics that all Markov chains share.
**The Markov chain Monte Carlo method, abbreviated MCMC, is the application of Markov chains to computing difficult integrals and expectations, and it is one of the most important practical uses of the subject.** The idea of MCMC is to build a Markov chain whose stationary distribution is the target distribution, and then to sample the chain so that the long-run samples approximate draws from the target. The Metropolis-Hastings algorithm constructs such a chain by proposing moves and accepting them with a probability that ensures the target distribution is stationary, and the Gibbs sampler constructs it by updating one coordinate at a time from its conditional distribution. The samples from the chain are used to estimate expectations and probabilities, and the correlation between successive samples is the cost of using a chain rather than independent draws. The MCMC method underlies the bayesian statistics keyword, because it is the standard way to sample from the complicated posterior distributions that bayesian analysis produces, and it is the bridge from the theory of Markov chains to the computational statistics of the series. In a fab the MCMC method samples the posterior distribution of a process parameter, giving the engineer a full picture of its uncertainty. The MCMC method turns the Markov chain from a model into a computational engine.
**The equilibrium behavior of a Markov chain is described by its stationary distribution, while the transient behavior is described by the powers of the transition matrix, and the balance between the two is the practical way to analyze a system.** To study the transient behavior, the engineer computes the distribution of the chain at a finite number of steps by multiplying the initial distribution by the powers of the transition matrix, and to study the long-run behavior the engineer solves the stationary equations. The matrix powers converge to a matrix in which every row is the stationary distribution for an ergodic chain, which is the mathematical reason that the long-run behavior is independent of the starting state. The rate of convergence is governed by the second-largest eigenvalue of the transition matrix, and a smaller second eigenvalue means faster mixing, so that the mixing time of the chain tells the engineer how many steps are needed to approach the steady state. The study of the transient and the steady state together gives the complete picture of the chain, and the eigenvalue structure is the key to understanding the speed of convergence. In a fab the mixing time tells the engineer how quickly a tool reaches its steady-state availability after a restart. The equilibrium and the transient analysis complete the treatment of the Markov chain.
**The Markov chain is also the natural model of the yield and the quality states of a wafer as it moves through the manufacturing line, and this application ties the subject directly to the yield engineering of a fab.** Each process step can be modeled as a transition between the good and the defective state, with a probability of passing each step, and the chain then describes how a wafer moves through the sequence of steps until it is either completed good or scrapped. The probability that a wafer is good after all the steps is the product of the step yields only when the steps are independent, and the Markov chain extends this to the case in which the state carries over from step to step. The absorbing chain models the wafer lot as it moves until it is completed or scrapped, and the absorption probability is the expected yield. In a fab the Markov chain gives a principled way to combine the step yields into a final yield, and to compute the effect of improving a single step on the overall yield. The yield chain is one of the most valuable applications of the subject to semiconductor manufacturing. The engineer who models the yield as a Markov chain can quantify the effect of every step.
**The connection between the Markov chain and the other keywords of the series is direct, and it deepens the stochastic and the computational threads that the series has been weaving.** The probability distributions keyword supplies the distributions of the states and the expectations that the chain uses, and the stochastic processes keyword introduces the Markov process as one of its families, while the Markov chain develops the discrete-time machinery in full. The probability stats keyword supplies the laws of probability that govern the transitions, and the bayesian statistics keyword uses the Markov chain Monte Carlo method to sample its posterior distributions. The multivariate statistics keyword supplies the matrices and the eigenvectors that the transition matrix uses, because the stationary distribution is an eigenvector of the transition matrix, and the linear algebra keyword supplies the matrix powers and the eigenvalue decompositions that drive the analysis. The inference statistics keyword supplies the estimation and the testing that connect the fitted chain to the data. The Markov chain is the bridge between the discrete-time dynamics of the series and the computational statistics of bayesian inference. The engineer who masters the Markov chain can model the dynamics of a system and compute its long-run behavior.
**The history of the Markov chain is the story of the mathematician who created the subject and of the scientists who turned it into a computational tool, and their names mark the principal results.** Andrey Markov introduced the chain that bears his name in the early twentieth century while studying the statistics of language, and he proved the law of large numbers for his chains, establishing the theory of the subject. Sergei Chapman and Andrey Kolmogorov developed the equations that bear their names for the multi-step transition probabilities, and John von Neumann and Stanislaw Ulam invented the Monte Carlo method, while Nicholas Metropolis, with Arianna Rosenbluth and others, generalized it into the Metropolis algorithm for sampling, and W. K. Hastings extended it to the general form used today. Stuart Geman and Donald Geman introduced the Gibbs sampler and the simulated annealing, and Steve Brooks and others consolidated the theory and the diagnostics of MCMC. The names on the subject are the names of the mathematicians and the computational scientists who built the field from the study of chains to the machinery of modern computation. The history shows that the Markov chain grew from a curiosity about language into one of the most widely used tools of applied statistics. The engineer who uses a Markov chain is standing on a century of mathematics.
**The expected hitting time is the average number of steps that the chain takes to reach a given set of states for the first time, and it is one of the most useful quantities that a Markov chain can answer. The hitting time of a set of states is the first step at which the chain enters that set, and its expected value satisfies a system of linear equations that expresses the expectation from each starting state in terms of the expectations from the next states. The equations are solved to give the mean first passage time from each state to the target, which is the average number of steps the chain takes to arrive, and the solution is related to the fundamental matrix of an absorbing chain. The mean first passage time is the answer to many engineering questions, such as how long a process takes on average to reach a target condition, and it is computed by solving a linear system rather than by simulating. In a fab the mean first passage time gives the expected time for a tool to reach the failed state, and the expected time for a wafer to complete its process sequence. The hitting times turn the Markov chain into a tool for computing expected durations.
**The expected number of visits to a state is the companion of the hitting time, and it measures how often the chain passes through a state over the course of its evolution.** For a transient state, the expected number of visits before absorption is finite and is given by an entry of the fundamental matrix, while for a recurrent state the expected number of visits is infinite because the chain returns infinitely often. The fundamental matrix of an absorbing chain therefore contains the expected visits to each transient state, and it is the single object from which both the expected durations and the absorption probabilities are read. The expected number of visits to a state times the expected holding time in that state gives the expected total time that the chain spends in the state, which is how the fundamental matrix is used to compute expected durations of an absorbing process. In a fab the expected number of visits to a maintenance state tells the engineer how often a tool is expected to need attention over a horizon. The expected visits complete the quantitative picture of an absorbing chain.
**The detailed balance condition is a sufficient condition for a probability distribution to be stationary, and it is the mechanism by which the MCMC algorithms guarantee convergence.** A transition matrix and a distribution satisfy detailed balance when the probability of being in a state and moving to another equals the probability of being in the other and moving back, so that the probability flows between every pair of states are balanced in each direction. If detailed balance holds for a distribution, then the distribution is stationary, because the total flow into each state balances the total flow out of it, although detailed balance is stronger than stationarity and does not always hold. The Metropolis-Hastings algorithm is constructed precisely so that its target distribution satisfies detailed balance, which is the mathematical guarantee that the chain converges to the target, and this is why the acceptance rule is chosen as it is. The detailed balance is the bridge from the abstract stationarity to the construction of the MCMC samplers. In a fab the detailed balance is rarely verified directly, but it is the reason that the bayesian samplers of the series work at all. The detailed balance gives the engineer the confidence that a correctly built chain reaches its target.
**The hidden Markov model is the extension of the Markov chain to the situation in which the states are not directly observed but are inferred from a sequence of emitted observations, and it is one of the most important applications of the theory.** In a hidden Markov model the state sequence follows a Markov chain, but the engineer observes only a sequence of emissions that depend on the hidden states through an emission distribution, so that the states must be inferred from the observations. The hidden Markov model is used to model a process whose underlying state is unobserved, such as the health of a tool that emits noisy sensor readings, and the inference of the hidden states is carried out by the forward-backward algorithm and the Viterbi algorithm. The forward-backward algorithm computes the probability of being in each hidden state at each time given the observations, and the Viterbi algorithm finds the most likely sequence of hidden states. In a fab a hidden Markov model might infer the unobserved wear state of a chamber from the noisy measurements of its performance. The hidden Markov model extends the Markov chain from a model of an observed process to a model of a process whose state must be uncovered.
**The burn-in and the convergence diagnostics are the practical tools that make the MCMC samples trustworthy, because a Markov chain does not sample its stationary distribution from the first step.** The burn-in is the initial segment of the chain that is discarded, because it still reflects the starting point rather than the target distribution, and the remaining samples are used for estimation only after the chain has converged. The convergence is assessed by diagnostics such as the trace plot, which shows the samples over time and reveals whether they have settled, and the autocorrelation, which shows how much the successive samples depend on one another. The effective sample size is the number of independent samples that the correlated chain is worth, and it is smaller than the number of raw samples, so that the engineer estimates the standard error of the Monte Carlo estimate from the effective sample size. In a fab the engineer discards a burn-in from a bayesian sampler and checks the trace before trusting the posterior estimates. The convergence diagnostics are the quality control of the MCMC method.
**The law of large numbers for Markov chains generalizes the classical law of large numbers to a dependent sequence, and it states that the long-run average of a function of the chain converges to its expectation under the stationary distribution.** If the chain is irreducible and has a stationary distribution, then the average over the first $n$ steps of any bounded function of the states converges to the expected value of that function under the stationary distribution, so that the time average equals the space average. This ergodic theorem is the justification for estimating a long-run quantity by the long-run proportion of the time that the chain spends in the states, and it is why the stationary distribution can be estimated by the empirical frequencies of the states over a long run. The ergodic theorem also underlies the MCMC estimation, because the long-run average of a function over the sampled chain estimates its expectation under the target distribution. In a fab the ergodic theorem justifies estimating the availability of a tool by the long-run proportion of the time that it is observed to be in the working state. The law of large numbers for Markov chains is the guarantee that the long-run estimates are valid.
**A numerical example makes the theory concrete, and the example of a two-state tool that is either working or failed illustrates the whole computation.** Suppose the working state is $W$ and the failed state is $F$, and the transition matrix has the probability of staying working at $0.95$, of failing at $0.05$, and the probability of being repaired from failed at $0.9$, so that the matrix rows are $0.95$ and $0.05$ for the working state and $0.9$ and $0.1$ for the failed state. The stationary distribution solves $\pi = \pi P$, which gives the two equations $0.95\pi_W + 0.9\pi_F = \pi_W$ and $0.05\pi_W + 0.1\pi_F = \pi_F$, and the second simplifies to $0.05\pi_W = 0.9\pi_F$, so that the tool is working about ninety-five percent of the time in the long run. The expected number of consecutive working steps, which is the mean return time to the failed state, is the reciprocal of the failure probability and is twenty steps, and the expected repair time is the reciprocal of the repair probability and is about one point one steps. The example shows how the balance equation and the mean return times are computed from the transition matrix by solving simple linear equations. This small example is the seed of every larger Markov analysis in a fab.
**The application of the Markov chain to the preventive maintenance of a tool shows how the subject supports the reliability engineering of a fab, and it ties the chain to the availability and the maintenance planning.** The state space of a maintained tool includes the working, the degraded, and the failed states, and the transition matrix includes the probabilities of degradation and of failure, while the maintenance actions move the tool from the degraded or the failed state back to the working state. The stationary distribution then gives the long-run proportion of the time that the tool is available, and the cost of the maintenance is balanced against the cost of the downtime by solving a decision problem over the chain. The Markov chain supports the comparison of maintenance policies by computing the availability and the cost of each policy, and the optimal policy balances the preventive maintenance against the failure risk. In a fab the engineer uses a Markov model to choose how often to perform preventive maintenance on a tool, trading the cost of the maintenance against the cost of the unexpected failures that it prevents. The Markov chain turns the maintenance decision into a computed trade-off. The reliability application shows the value of the subject to the everyday operation of a fab.
**The connection of the Markov chain to the matrices and the linear algebra of the series runs deep, because the transition matrix is a matrix and the stationary distribution is an eigenvector.** The stationary distribution $\pi$ satisfies $\pi P = \pi$, which means that $\pi$ is a left eigenvector of the transition matrix with eigenvalue one, and the largest eigenvalue of every stochastic matrix is one, so that the stationary distribution is the eigenvector of the dominant eigenvalue. The powers of the transition matrix converge at a rate governed by the second-largest eigenvalue, and the spectral gap, which is the difference between the largest and the second-largest eigenvalues, determines how quickly the chain mixes. The matrix algebra of the linear algebra keyword therefore supplies the machinery that the Markov chain needs, and the eigenvalue decomposition of the transition matrix is the key to the long-run and the mixing behavior. In a fab the engineer uses the eigenvalue structure of the transition matrix to estimate how many steps a process needs to reach its steady state. The matrix view of the Markov chain connects the subject to the linear algebra that began the series.
**The extensions of the Markov chain to continuous time and to higher-order structure complete the survey of the subject, and they connect the chain to the stochastic processes keyword.** In a continuous-time Markov chain the system moves among the states at random times governed by exponential holding times, and it is the natural model of a process observed continuously, while the discrete-time chain of this document models the process observed at fixed intervals. The higher-order Markov chains let the next state depend on more than the present state, at the cost of enlarging the state space, and they are used when the Markov property is too strong for the data. The Markov chain also connects to the queueing theory that models the waiting lines of a fab, because the arrival and the service processes of a queue form a Markov structure. In a fab the continuous-time chain models a continuously monitored tool, and the queueing models describe the flow of lots through the tools. The extensions show that the discrete-time Markov chain is the foundation of a wider family of stochastic models. The engineer who masters the discrete-time chain can move easily to the continuous-time and the queueing extensions.
**The spectral gap and the mixing time are the quantitative measures of how fast a Markov chain converges, and they are important when the engineer needs to know how many steps are enough. The mixing time is the number of steps required for the distribution of the chain to become close to the stationary distribution, and it is governed by the second-largest eigenvalue of the transition matrix: the smaller that eigenvalue, the faster the chain mixes. The spectral gap is the difference between the largest eigenvalue, which is one, and the second-largest eigenvalue, and a large spectral gap means rapid convergence while a small gap means slow convergence. The mixing time is approximately the reciprocal of the spectral gap, so that a chain with a gap of one tenth mixes in about ten steps, and this estimate guides how long a chain must run before its samples are useful. In a fab the mixing time tells the engineer how many cycles a process needs to reach its steady-state behavior, and in an MCMC run it tells how many samples to discard. The spectral gap turns the vague idea of convergence into a computable quantity.
**The redundant and the repairable systems that appear throughout a fab are modeled naturally with Markov chains, and they show the subject at work on the reliability of the hardware.** A redundant system with two identical units in parallel, each of which can work or fail, has four states that describe which units are working, and the transition matrix gives the probabilities of the units failing and being repaired. The availability of the system is the probability that at least one unit is working, which is computed from the stationary distribution, and the reliability is the probability that the system survives without ever entering the state in which both units have failed. The Markov chain lets the engineer compare a redundant design with a single-unit design, computing how much the redundancy improves the availability, and it extends to systems with many units and with partial failure states. In a fab the redundancy of the critical equipment is evaluated with a Markov model, and the availability target is checked against the computed stationary distribution. The reliability models turn the Markov chain into the tool of the availability engineer.
**The comparison of the Markov chain with the queueing models of the fab shows how the subject scales from a single system to a whole line, and it connects the chain to the flow of wafers.** A queue is a Markov structure in which lots arrive, wait for a tool, receive service, and leave, and the Markov chain models the number of lots waiting as it evolves over time. The balance equations of the queue are solved to give the stationary distribution of the queue length, from which the average waiting time and the utilization of the tool are computed. The queueing analysis is the natural extension of the single-system Markov chain to the flow of many lots, and it is the basis of the line-balancing and the throughput analysis of a fab. In a fab the engineer uses a queueing model of a bottleneck tool to predict the waiting time of the lots and to decide how much buffering to provide. The queueing extension shows that the Markov chain is not limited to a single system but scales to the flow of the whole manufacturing line. The queueing theory is the Markov chain applied to the movement of lots.
**The transition matrix of a Markov chain is estimated from data by counting the observed transitions between the states, and the estimation connects the model to the measured history of a system. If the engineer records the sequence of states of a tool over time, the maximum likelihood estimate of the transition probability from state $i$ to state $j$ is the number of observed transitions from $i$ to $j$ divided by the total number of departures from $i$, so that each row of the estimated matrix is the empirical distribution of the next state given the present. The estimate is consistent as the length of the observed sequence grows, and its uncertainty can be assessed, so that the engineer knows how much to trust the fitted chain. The estimated transition matrix is then used to compute the availability, the hitting times, and the stationary distribution of the system. In a fab the engineer fits the transition matrix from the tool history log, and the fit is the bridge from the data to the Markov model. The estimation of the transition matrix makes the subject directly applicable to observed systems.
**The advanced process control of a fab also draws on the Markov structure, because the run-to-run controllers that adjust the process from lot to lot respond to the current state of the process.** The run-to-run control models the process output as a function of the previous state and the controller setting, and the Markov property holds when the next process state depends on the current state rather than on the whole history. The controller uses the predicted future states to choose the setting that brings the output to target, and the analysis of the closed-loop behavior can be cast in the language of a chain of states. In a fab the run-to-run controllers of the etch and the deposition tools are analyzed with this Markov view, and the stability of the control loop is assessed by the behavior of the resulting chain. The control application shows that the Markov chain reaches beyond the reliability and the yield models to the very controllers that run the process. The subject is woven throughout the operation of a modern fab.
The software tools that compute the Markov chain quantities make the subject practical, and they let the engineer analyze a chain of any size without solving the equations by hand.** The transition matrix of a finite chain is entered into a computational tool that computes the powers of the matrix, the stationary distribution, the hitting times, and the absorption probabilities by matrix operations and linear solves. The matrix powers are computed efficiently by repeated squaring, and the stationary distribution is found by solving a linear system or by an iterative power method that repeatedly multiplies a distribution by the transition matrix until it converges. The MCMC samplers are available in the statistics libraries of most programming languages, and they hide the details of the Metropolis-Hastings and the Gibbs algorithms behind a simple sampling function. In a fab the engineer uses such a tool to compute the availability and the failure risk of every piece of equipment, and to run the bayesian samplers of the series. The computational tools turn the mathematics of the Markov chain into an everyday engineering instrument. The engineer who can use a matrix and a sampling library can analyze any Markov chain.
The verification of the Markov property on real data is an important practical step, and it checks whether the Markov assumption is a good model for a process before the machinery is applied.** The Markov property can be tested by comparing the transition frequencies from a state with and without conditioning on the earlier states, and a process satisfies the assumption when the transition probabilities do not depend on how the present state was reached. A common diagnostic tests whether the one-step transitions are independent of the two-step history, and a lack of dependence supports the Markov model. When the data fail the test, the engineer enlarges the state space or adds more history, because a higher-order chain can often restore the Markov property. In a fab the engineer verifies the Markov property on the observed state transitions of a tool before trusting the availability calculation. The verification step keeps the Markov model honest. The model is only as good as the assumption that it makes.
The theory of Markov chains is summarized in a compact table of the principal objects and the equations that define them, and the table organizes the machinery so that it can be applied quickly.** The table pairs each concept with its definition and its purpose, and it is the reference that the engineer consults when analyzing a chain.
| Concept | Definition | Purpose |
|---|---|---|
| Markov property | next state depends only on the present | the defining assumption |
| State space | set of all possible states | defines what the model represents |
| Transition matrix P | p_ij = P(step to j from i) | single-step transitions |
| Stochastic matrix | rows nonneg, sum to one | valid transition matrix |
| Chapman-Kolmogorov | P^(n) = P^n | multi-step probabilities |
| Recurrent state | returns with probability one | long-run structure |
| Transient state | positive chance of no return | occasional states |
| Absorbing state | never leaves once entered | terminal conditions |
| Communicating class | mutually reachable states | partitions the states |
| Stationary distribution π | π = πP, Σπ = 1 | long-run proportions |
| Aperiodic / ergodic | period 1, irreducible | guarantees convergence |
| Fundamental matrix | inverse of transient submatrix | absorption probabilities |
| Metropolis-Hastings | chain with target π | MCMC sampling |
**The classification of a Markov chain and the computation of its stationary distribution follow a decision procedure, and the following flowchart routes the analysis from the transition matrix to the long-run behavior.** The first question is whether the chain is finite and irreducible, and the second is whether it is aperiodic, and the answers determine whether a stationary distribution exists and how it is found. Working through the flowchart gives the engineer the structure of any Markov chain.
```flowchart
A([Transition matrix P]) --> B{Finite and irreducible?}
B -- no --> C[partition into communicating classes; classify states]
B -- yes --> D{Aperiodic?}
D -- no --> E[periodic: no single limiting distribution]
D -- yes --> F{Find stationary distribution}
F --> G[solve π = πP with Σπ = 1]
G --> H[ergodic: converge to π from any start]
C --> I[absorbing states?]
I -- yes --> J[fundamental matrix → absorption probs & expected time]
I -- no --> H
H --> K[compute availability / long-run proportions]
J --> K
```
**A concrete example ties the machinery together and shows how a Markov chain is analyzed in a fab, and the example of the availability of an etch tool illustrates the complete workflow.** The engineer models the tool with three states, the idle, the processing, and the failed state, and writes the transition matrix from the observed rates of starting, finishing, and failing. The engineer verifies that the chain is irreducible and aperiodic, solves the balance equation for the stationary distribution, and finds that the tool spends the largest proportion of its time in the processing state and a small but important proportion failed. The engineer uses the absorption probability of the failed state to compute the expected time until a failure, and uses the Markov chain Monte Carlo method to sample the uncertainty in the transition rates. The example shows that the Markov chain is not a purely theoretical object but the working model of every tool and every process line. This single example shows how the Markov chain turns the observed transitions of a tool into its availability, its failure risk, and its long-run behavior.
**The closing lens for Markov chains is that a Markov chain is a model of a system with a short memory, and the value of the subject is in turning a sequence of transitions into the long-run behavior.** With this lens the engineer sees every tool as a set of states and every transition as an entry in a stochastic matrix, sees the Markov property as the simplifying assumption that makes the analysis possible, sees the stationary distribution as the long-run answer to every question about the system, and sees the absorbing states as the terminal conditions of processes that do not go on forever. The mastery of the Markov chain is the mastery of modeling a system that changes over time and predicting where it is headed, which is precisely the situation that the equipment, the yield, and the reliability of a fab present every day. Read markov chains through a transition-matrix lens rather than a state-list lens.