5: Countable-state Markov Chains
- Page ID
- 44621
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
- 5.1: Countable State Markov Chains
- Markov chains with a countably-infinite state space (more briefly, countable-state Markov chains) exhibit some types of behavior not possible for chains with a finite state space. With the exception of the first example to follow and the section on branching processes, we label the states by the nonnegative integers. This is appropriate when modeling things such as the number of customers in a queue, and causes no loss of generality in other cases.
- 5.2: Birth-Death Markov chains
- A birth-death Markov chain is a Markov chain in which the state space is the set of nonnegative integers; for all i 0, the transition probabilities satisfy Pi,i+1 > 0 and Pi+1,i > 0, and for all |ij| > 1, Pij = 0 (see Figure 5.4). A transition from state i to i+1 is regarded as a birth and one from i+1 to i as a death. Thus the restriction on the transition probabilities means that only one birth or death can occur in one unit of time.
- 5.3: Reversible Markov Chains
- Many important Markov chains have the property that, in steady state, the sequence of states looked at backwards in time has the same probabilistic structure as the sequence of states running forward in time. This equivalence between the forward chain and backward chain leads to a number of results that are intuitively quite surprising and that are quite dicult to derive without using this equivalence. We shall study these results here.
- 5.5: Branching Processes
- Branching processes provide a simple model for studying the population of various types of individuals from one generation to the next. The individuals could be photons in a photomultiplier, particles in a cloud chamber, micro-organisms, insects, or branches in a data structure.
- 5.6: Round-robin and Processor Sharing
- Typical queueing systems have one or more servers who each serve customers in FCFS order, serving one customer completely while other customers wait. These typical systems have larger average delay than necessary.