In many applications, we observe a system transitioning through various possible states and the probability of observing the system in any given state is conditioned by states occupied at previous times. A key example is a queue, or waiting line, where jobs arrive for service and the state of the system is the number of jobs in the system. This number is random and, at any point in time, depends on arrivals to the system and service to jobs in the system prior to that point. Since arrivals and service times are random, so is the state of the system. In the next three sections, we study systems for which conditional state probabilities depend only on the most recent conditioning event. The first two sections treat mainly discrete-time processes; the third treats continuous-time processes.

5.1.1. Chapman-Kolmogorov Equations

Given values of a one-dimensional, discrete-valued random process at times prior to some time t′ (excepting independence) X(t) will depend on one or more of the preceding observations. For instance, for t<t′ we consider the transition probability

In the current context, the set of all possible process values is called the state space and the transition probability p_x,x′(t,t′) gives the conditional probability of being in state x′ at time t′ given the process is in state x at time t. More generally, we consider conditional probabilities P(X(t′) = x′|V), where V is a set of values for X(t) at some number of points prior in time to t′. In many important situations, conditioning the process on its values at some collection of previous time points reduces to conditioning only at the last time point at which it is conditioned. A discrete-state-space stochastic process is said to be a Markov chain if, given any set of time points t₁<t₂<…<t_n, it satisfies the Markov property