The Central Idea
At each index or time, a stochastic process occupies some possible condition. That condition is its state.
If the process is written
\[ \{X_n\}_{n\ge 0}, \]then the value of \(X_n\) tells us the state occupied at step \(n\).
The set of all values that the process is allowed to take is the state space, commonly denoted by
\[ \boxed{S}. \]Thus,
\[ \boxed{X_n\in S}. \]A state space defines the possible conditions through which the modeled system may evolve.
What Is a State?
A state is a value or collection of values used to describe the condition of a system at a particular point in its evolution.
Depending on the model, a state might represent:
- the weather today;
- the number of customers in a queue;
- the amount of inventory in a warehouse;
- the location of a moving particle;
- whether a component is functioning or failed;
- the number of organisms in a population;
- several variables recorded together.
The meaning of a state is determined by the model, not by the symbol used to represent it.
What Is a State Space?
The state space is the set containing every state that the model permits.
If a machine is either operating or failed, we might define
\[ S=\{\text{operating},\text{failed}\}. \]If \(X_n\) records the machine's state after inspection \(n\), then
\[ X_n\in S \]for every permitted index \(n\).
State Variable and State Space
It is useful to distinguish the random variable describing the current state from the set of states it may occupy.
For example, suppose \(X_n\) is the number of customers waiting after minute \(n\). Then a possible state variable is
\[ X_n=4, \]while the state space may be
\[ S=\{0,1,2,3,\ldots\}. \]The number \(4\) is one state. The set \(S\) is the state space.
A Simple Finite Example
Suppose the weather is classified each day as sunny, cloudy, or rainy.
Define
\[ S=\{\text{sunny},\text{cloudy},\text{rainy}\}. \]Then a weather process might produce a path such as
\[ \text{sunny},\text{sunny},\text{cloudy},\text{rainy},\text{cloudy},\ldots \]Every term of the path belongs to the same state space \(S\).
States May Be Labeled Numerically
Descriptive states can be assigned numerical labels when convenient.
For the weather example, we could define
\[ 0=\text{sunny},\qquad 1=\text{cloudy},\qquad 2=\text{rainy}. \]The state space then becomes
\[ \boxed{S=\{0,1,2\}}. \]These numbers are labels. Their numerical size does not automatically imply that rainy weather is "twice" cloudy weather or that differences between the labels have quantitative meaning.
Finite State Spaces
A state space is finite if it contains only finitely many states.
A general finite state space may be written
\[ \boxed{S=\{s_1,s_2,\ldots,s_m\}}. \]Examples include:
- on/off;
- working/degraded/failed;
- the face of a die;
- a bounded inventory level from \(0\) through \(100\);
- a person's location among a fixed set of rooms.
Example: A Die as a State Process
Suppose a die is rolled once per minute and \(X_n\) records the face observed on roll \(n\).
The state space is
\[ \boxed{S=\{1,2,3,4,5,6\}}. \]A realized path might be
\[ 2,5,5,1,4,6,\ldots \]The process is random because the future states are uncertain, even though the set of possible states is known in advance.
Countably Infinite State Spaces
A state space may have infinitely many states while still being countable.
For example, the number of customers in an unlimited-capacity queue can be
\[ 0,1,2,3,\ldots \]so
\[ \boxed{S=\{0,1,2,3,\ldots\}}. \]There is no fixed largest possible queue length in this idealized model.
Example: Population Size
Suppose \(X_n\) records the number of organisms in a population after generation \(n\).
A simple state space is
\[ S=\{0,1,2,3,\ldots\}. \]The state \(0\) represents extinction. Positive integers represent possible population sizes.
This type of state space will reappear when we study branching processes.
Continuous State Spaces
A state space is often called continuous when the state may range over an interval or another uncountable subset of real space.
If \(X_n\) records the temperature of a system, a simplified model might use
\[ \boxed{S=\mathbb{R}}. \]A physically restricted model could instead use an interval such as
\[ S=[-20,50]. \]The state variable is then real-valued rather than restricted to isolated integer values.
Discrete Time Does Not Require a Discrete State Space
The index set and the state space describe different parts of a stochastic process.
A sequence
\[ X_0,X_1,X_2,\ldots \]uses discrete time because its indices occur in separate steps. But each \(X_n\) could still take any real value.
For example,
\[ X_n=\text{temperature measured at hour }n \]gives a discrete-time process with a continuous state space.
Continuous Time Does Not Require a Continuous State Space
The reverse distinction is also important.
A system may evolve continuously in time while occupying only discrete states. For example, a machine can switch between
\[ \{\text{working},\text{failed}\} \]at arbitrary real-valued times.
Thus, time type and state-space type are separate modeling choices.
The Four Basic Time-State Combinations
A stochastic process can combine discrete or continuous time with discrete or continuous state values.
- Discrete time, discrete state: daily weather categories.
- Discrete time, continuous state: hourly temperature measurements.
- Continuous time, discrete state: the number of customers currently in a queue.
- Continuous time, continuous state: the continuously changing position of a particle.
These distinctions help classify stochastic-process models before any transition formulas are introduced.
Vector-Valued States
A state does not have to be one number. It may be a vector containing several quantities.
Suppose a warehouse tracks both inventory and outstanding orders. A state may be written
\[ X_n=(I_n,B_n), \]where \(I_n\) is inventory and \(B_n\) is backlog.
A possible state is
\[ X_n=(25,7). \]This means 25 units are in inventory and 7 units are backordered.
Product State Spaces
When a state contains several components, the state space may be represented as a Cartesian product.
If
\[ I_n\in\{0,1,\ldots,100\} \]and
\[ B_n\in\{0,1,2,\ldots\}, \]then a broad state space is
\[ \boxed{S=\{0,1,\ldots,100\}\times\{0,1,2,\ldots\}}. \]Each state is an ordered pair selected from this product.
Constrained State Spaces
Not every mathematical combination of variables is necessarily physically or logically possible.
Suppose \(X_n=(A_n,B_n)\) counts two types of items in a container that can hold at most 10 items total. Then
\[ A_n\ge 0,\qquad B_n\ge 0, \]and
\[ A_n+B_n\le 10. \]The state space is therefore
\[ \boxed{S=\{(a,b)\in\mathbb{Z}_{\ge0}^2:a+b\le10\}}. \]A constrained state space records the actual rules of the system rather than every imaginable coordinate pair.
State Spaces Can Be Geometric
State spaces can also be regions of geometric space.
If a moving point must remain inside the unit disk, its state might be its position
\[ X_n=(x_n,y_n), \]with state space
\[ \boxed{S=\{(x,y)\in\mathbb{R}^2:x^2+y^2\le1\}}. \]Stochastic-process state spaces may therefore involve familiar algebraic and geometric structures.
State Space Versus Sample Space
The state space and the probability-theory sample space are related but different objects.
The sample space, often denoted \(\Omega\), contains complete outcomes of the random experiment. The state space \(S\) contains values that the process may occupy.
For repeated coin tossing, one possible sample point is an entire infinite sequence such as
\[ \omega=(H,T,H,H,T,\ldots). \]If \(X_n\) records whether toss \(n\) is heads or tails, then the state space may simply be
\[ \boxed{S=\{H,T\}}. \]A Random Variable Maps Outcomes to States
For a process defined on sample space \(\Omega\), each indexed random variable can be viewed as a mapping
\[ \boxed{X_n:\Omega\to S}. \]A sample point \(\omega\in\Omega\) specifies a complete random outcome. The value
\[ X_n(\omega) \]tells us which state is occupied at index \(n\) for that outcome.
Sample Paths Move Through the State Space
Once a random outcome is realized, the stochastic process produces a sample path through the state space.
If
\[ S=\{0,1,2,3\}, \]then one possible path is
\[ 1,2,1,0,1,2,3,\ldots \]Each term is a state, and the entire ordered sequence is the path.
The Initial State
A stochastic model often begins by specifying an initial state
\[ \boxed{X_0=x_0}. \]For example, a queue may begin empty:
\[ X_0=0. \]A random walk may begin at the origin:
\[ X_0=0. \]A reliability system may begin in the working state.
A Random Initial State
The initial state does not have to be known with certainty.
Instead, the model may specify probabilities such as
\[ P(X_0=s_i)=p_i. \]For a finite state space
\[ S=\{s_1,\ldots,s_m\}, \]the initial distribution can be written as
\[ (p_1,p_2,\ldots,p_m), \]where
\[ p_i\ge0, \qquad \sum_{i=1}^{m}p_i=1. \]Probability Distributions Over States
At any step \(n\), uncertainty about the current state can be summarized by a probability distribution over the state space.
For finite \(S=\{s_1,\ldots,s_m\}\), define
\[ p_i^{(n)}=P(X_n=s_i). \]Then
\[ \boxed{\sum_{i=1}^{m}p_i^{(n)}=1}. \]The state space tells us what can happen; the distribution tells us how probability is allocated among those states at a particular step.
Support of a State Distribution
At a particular step, not every state in the full state space must have positive probability.
The support of the distribution of \(X_n\) is the collection of states that currently receive positive probability.
For a discrete state space,
\[ \operatorname{supp}(X_n)=\{s\in S:P(X_n=s)>0\}. \]The support may change with \(n\), even though the overall state space remains fixed.
Reachable States
A state may belong to the formal state space but still be unreachable from a particular starting condition under the model's transition rules.
Suppose a process starts at \(0\) and increases by either \(0\) or \(2\) at every step. Although we might initially write
\[ S=\{0,1,2,3,\ldots\}, \]the process can reach only even states:
\[ 0,2,4,6,\ldots \]Recognizing reachable states can simplify a model.
State Transitions
A stochastic process evolves by making transitions from one state to another.
If the current state is \(X_n=i\) and the next state is \(X_{n+1}=j\), then the process has made the transition
\[ \boxed{i\to j}. \]A state space identifies the possible locations of the process. Transition rules determine how movement among those locations occurs.
Not Every Transition Must Be Allowed
The fact that two states belong to the same state space does not mean that the process can move directly between them.
Suppose an inventory level changes by at most one unit per period. From state \(5\), the next state might be restricted to
\[ \{4,5,6\}. \]A direct transition from \(5\) to \(20\) would then be impossible, even if both values belong to the full state space.
Transition Diagrams
For a finite or small countable state space, possible transitions can be shown with a directed diagram.
Each state is represented by a node. A directed arrow
\[ i\to j \]indicates that a one-step move from state \(i\) to state \(j\) is allowed.
Later, probabilities can be attached to these arrows. This creates one of the standard representations of a Markov chain.
Absorbing States
An absorbing state is a state that, once entered, cannot be left under the model.
If \(a\) is absorbing, then after entering \(a\), the process remains there:
\[ X_n=a \quad\Longrightarrow\quad X_{n+1}=a. \]In a population model, extinction state \(0\) is often absorbing because a population with no organisms cannot reproduce unless outside immigration is included.
Boundary States
A boundary state occurs at an edge of the permitted state space and may have different transition options from interior states.
If inventory must remain between \(0\) and \(10\), then \(0\) and \(10\) are boundary states.
From an interior state such as \(5\), movement both upward and downward may be allowed. At \(0\), a move to \(-1\) is forbidden by the state-space constraint.
Choosing the Right State Description
A useful state should contain enough information to describe the condition of the modeled system for the purpose at hand.
Suppose we model a delivery truck. Depending on the question, the state might be:
- the truck's current city;
- its exact geographic coordinates;
- its city and remaining fuel;
- its location, fuel, cargo, and driver status.
There is no universally correct state description independent of the modeling objective.
State Granularity
Granularity describes how finely a model distinguishes states.
A weather model might use two states,
\[ S_1=\{\text{dry},\text{wet}\}, \]or five states,
\[ S_2=\{\text{sunny},\text{cloudy},\text{rain},\text{snow},\text{storm}\}. \]The second state space contains more detail but also requires more information to estimate and analyze its transition behavior.
Aggregation of States
Several detailed states can sometimes be combined into one broader category.
For example,
\[ \{\text{light rain},\text{heavy rain},\text{storm}\} \]might be aggregated into a single state called
\[ \text{wet}. \]Aggregation can simplify a model, but it may discard distinctions that matter for prediction or decision-making.
A State Must Preserve Relevant Information
A state description that is too coarse can hide information needed to model future behavior.
Suppose a machine's chance of failing tomorrow depends not only on whether it is working today, but also on its age.
The state
\[ \text{working} \]may then be insufficient. A more informative state could be
\[ (\text{working},\text{age}). \]Good state design keeps the information relevant to future system evolution.
Augmenting the State
When the current state does not contain enough information, the state can be augmented by adding variables.
Suppose tomorrow's demand depends on both today's demand and yesterday's demand. If \(D_n\) alone is insufficient, define
\[ X_n=(D_n,D_{n-1}). \]The enlarged state records two consecutive demand levels.
State augmentation is a major modeling technique because a process with apparent memory can sometimes be represented more cleanly after enough relevant history is incorporated into the current state.
Observed State and Hidden State
Sometimes the true state of a system cannot be observed directly.
For example, the internal condition of a machine may be hidden, while sensors provide noisy measurements related to that condition.
We may distinguish:
- the underlying or hidden state;
- the observation generated from that state.
This distinction leads to more advanced models such as hidden-state and partially observed stochastic systems.
State Space and Physical Reality
A mathematical state space is a model, not necessarily an exact description of reality.
For example, a queue model may allow
\[ S=\{0,1,2,\ldots\} \]even though a real building cannot hold infinitely many customers.
The unbounded state space may still be a useful approximation when the actual physical capacity is so large that the upper limit rarely affects the behavior being studied.
State-Space Models and Assumptions
Choosing a state space embeds assumptions into the model.
If a reliability model uses only
\[ S=\{\text{working},\text{failed}\}, \]then degraded operating conditions are being ignored or grouped with one of those two categories.
If the model instead uses
\[ S=\{\text{healthy},\text{degraded},\text{critical},\text{failed}\}, \]it represents more stages of deterioration.
Example: Queue State Space
Let \(X_n\) be the number of customers in a system after step \(n\).
For unlimited capacity,
\[ S=\{0,1,2,\ldots\}. \]For a system that can hold at most 20 customers,
\[ \boxed{S=\{0,1,2,\ldots,20\}}. \]The same basic phenomenon can therefore lead to either a countably infinite or finite state space depending on the capacity assumption.
Example: Reliability State Space
Consider a system with two components, each of which may be working or failed.
Represent working by \(1\) and failed by \(0\). A state is then an ordered pair:
\[ X_n=(C_{1,n},C_{2,n}). \]The state space is
\[ \boxed{S=\{(0,0),(0,1),(1,0),(1,1)\}}. \]This state representation preserves which component is functioning, rather than recording only the number of working components.
Two Different State Spaces for the Same Reliability System
If the two components are interchangeable for the purpose of the model, we might record only the number of working components.
Then
\[ S=\{0,1,2\}. \]This is smaller than
\[ \{(0,0),(0,1),(1,0),(1,1)\}. \]The smaller state space is appropriate only if distinguishing the identities of the components is unnecessary for the questions being asked.
Example: Random Walk State Space
Consider the random walk
\[ X_{n+1}=X_n+\xi_{n+1}, \]where
\[ \xi_{n+1}\in\{-1,+1\}. \]If \(X_0=0\) and movement is unrestricted, a natural state space is
\[ \boxed{S=\mathbb{Z}}. \]At each step, the process moves to a neighboring integer.
Parity and Reachability in a Random Walk
Although the state space of the unrestricted random walk is \(\mathbb{Z}\), not every state can be occupied at every time.
Starting from \(X_0=0\), after one step the process must be at
\[ -1\quad\text{or}\quad1. \]After two steps it must be at an even integer:
\[ -2,0,2. \]Thus, the set of states reachable at a particular time can be smaller than the full state space.
Example: Position and Velocity
Suppose future motion depends on both current position and current velocity. Recording position alone may not be enough.
Define the state as
\[ X_n=(Q_n,V_n), \]where \(Q_n\) is position and \(V_n\) is velocity.
A natural state space may then be
\[ \boxed{S=\mathbb{R}^2}. \]This example illustrates why states often contain several variables: the goal is to capture the information needed to describe system evolution.
Finite-State Probability Vectors
When the state space is finite, the distribution of the current state can be stored in a probability vector.
For
\[ S=\{s_1,s_2,s_3\}, \]suppose
\[ P(X_n=s_1)=0.2, \qquad P(X_n=s_2)=0.5, \qquad P(X_n=s_3)=0.3. \]Then the state distribution can be written
\[ \boxed{\mathbf{p}^{(n)}=(0.2,0.5,0.3)}. \]Transition matrices will later show how such vectors evolve from one step to the next.
State Labels Must Match Probability Vectors
When probabilities are stored in a vector, the order of state labels matters.
If the state order is
\[ (\text{sunny},\text{cloudy},\text{rainy}), \]then
\[ (0.6,0.3,0.1) \]means
\[ P(\text{sunny})=0.6, \quad P(\text{cloudy})=0.3, \quad P(\text{rainy})=0.1. \]Reordering the states without reordering the probabilities changes the model.
Encoding a State Space
State spaces can be represented in many equivalent ways.
A three-state machine might be written as
\[ S=\{\text{idle},\text{running},\text{failed}\} \]or encoded numerically as
\[ S=\{0,1,2\}. \]The numerical encoding is useful for matrices and computation, while the descriptive labels may be easier to interpret.
Common Error: Confusing a State with the State Space
If the number of customers is currently \(4\), then
\[ X_n=4 \]is the current state.
The state space might be
\[ S=\{0,1,2,\ldots\}. \]A single realized value is not the same object as the complete set of allowed values.
Common Error: Confusing State Space with Sample Space
A sample point often contains enough information to determine an entire sample path, while a state describes the system at one indexed point.
For repeated coin tossing,
\[ \omega=(H,T,T,H,\ldots) \]may be one outcome in \(\Omega\), whereas
\[ S=\{H,T\} \]is the state space for the value recorded at each toss.
Common Error: Assuming Numerical Labels Are Measurements
If states are encoded as
\[ 0=\text{low},\qquad1=\text{medium},\qquad2=\text{high}, \]the labels help with storage and calculation. They do not automatically imply that the difference between low and medium equals the difference between medium and high.
The interpretation depends on what the states actually represent.
Common Error: Making the State Too Small
Suppose failure risk depends on both machine condition and age.
If the state records only
\[ \text{condition}, \]then two machines with the same condition but very different ages are treated as identical by the model.
If age materially affects future behavior, it should be included in the state.
Common Error: Making the State Unnecessarily Large
The opposite problem is to include variables that do not matter for the modeled behavior.
If a queue model depends only on the number of customers, recording each customer's name, clothing color, and arrival vehicle adds complexity without improving the stochastic description.
A strong state model keeps information that is relevant and removes information that is not.
Common Error: Ignoring Constraints
Suppose a storage system can hold at most 50 units. Writing
\[ S=\{0,1,2,\ldots\} \]allows states that violate the capacity rule.
A more faithful state space is
\[ \boxed{S=\{0,1,2,\ldots,50\}}. \]State-space constraints should reflect the assumptions of the model.
A Reliable Procedure for Defining a State Space
- Identify the system being modeled.
- Determine what information defines its condition at one step or time.
- Choose one variable or a vector of variables to represent that condition.
- List or describe every value those variables are allowed to take.
- Apply physical, logical, or operational constraints.
- Check whether the state contains enough information for the intended model.
- Remove unnecessary detail when a simpler state description preserves the needed behavior.
- Choose clear labels and keep their ordering consistent.
Example: Full State-Space Workflow
Suppose a parking facility has 30 spaces. Let \(X_n\) be the number of occupied spaces after event \(n\).
The state variable records one quantity: occupied spaces.
It cannot be negative, and it cannot exceed 30. Therefore,
\[ \boxed{S=\{0,1,2,\ldots,30\}}. \]If each event is either one arrival or one departure, then interior states can move to neighboring states. At \(0\), a departure cannot reduce occupancy further. At \(30\), an arrival cannot increase occupancy unless overflow is modeled.
The state space therefore captures both the possible values and the boundary conditions needed for later transition modeling.
Example: Expanding a State When One Variable Is Insufficient
Suppose the chance that a machine fails next period depends on whether it is working and on whether it was serviced during the current period.
A state containing only
\[ \{\text{working},\text{failed}\} \]may omit relevant information.
Define instead
\[ X_n=(C_n,M_n), \]where \(C_n\) is condition and \(M_n\) records maintenance status.
If
\[ C_n\in\{W,F\}, \qquad M_n\in\{0,1\}, \]then a preliminary product space is
\[ S=\{W,F\}\times\{0,1\}. \]Any logically impossible combinations can then be removed.
Practice 1: Identify the State Space
A traffic signal is modeled as red, yellow, or green. Write a natural state space.
Practice 2: Finite or Infinite?
A process records the number of phone calls currently waiting in an unlimited-capacity system. Is the natural state space finite, countably infinite, or continuous?
Practice 3: Continuous State Space
A sensor records a voltage that may take any value from \(0\) to \(5\) volts. Write a natural state space.
Practice 4: State or State Space?
A queue currently contains seven customers and may contain any nonnegative integer number of customers. Identify the current state and the state space.
Practice 5: Vector State
A model tracks the number of red and blue balls in a box. Each count may be \(0,1,2,\ldots\). Write a simple product state space.
Practice 6: Apply a Constraint
Repeat Practice 5 if the box can hold at most 12 balls total.
Practice 7: State Space Versus Sample Space
A fair die is rolled repeatedly, and \(X_n\) is the result of roll \(n\). What is the state space for \(X_n\)? Explain why an entire sequence of die rolls is not a single state.
Practice 8: Reachable States
A process starts at \(X_0=0\) and increases by exactly \(2\) at every step. List the first five reachable states, including the initial state.
Practice 9: Choose the Better State
A machine's chance of failure next month depends on both its current condition and its age. Which state description is more appropriate?
- condition only;
- the ordered pair (condition, age).
Explain why.
Practice 10: Probability Vector
The ordered state space is
\[ (A,B,C,D). \]At step \(n\), the probabilities are \(0.1\), \(0.4\), \(0.2\), and \(0.3\), respectively. Write the state-distribution vector and verify that it is a probability distribution.
Practice Answers
Practice 1
\[ \boxed{S=\{\text{red},\text{yellow},\text{green}\}}. \]Practice 2
The natural state space is
\[ \boxed{S=\{0,1,2,3,\ldots\}}, \]which is countably infinite.
Practice 3
\[ \boxed{S=[0,5]}. \]This is a continuous state space because every real value in the interval is permitted by the model.
Practice 4
The current state is
\[ \boxed{X_n=7}. \]The state space is
\[ \boxed{S=\{0,1,2,\ldots\}}. \]Practice 5
If \(R_n\) and \(B_n\) are the red and blue counts, then
\[ X_n=(R_n,B_n) \]with product state space
\[ \boxed{S=\mathbb{Z}_{\ge0}\times\mathbb{Z}_{\ge0}}. \]Practice 6
The capacity condition is
\[ r+b\le12. \]Therefore,
\[ \boxed{S=\{(r,b)\in\mathbb{Z}_{\ge0}^2:r+b\le12\}}. \]Practice 7
The state space is
\[ \boxed{S=\{1,2,3,4,5,6\}}. \]One state is the value observed at one indexed roll. An entire sequence such as \((2,6,1,4,\ldots)\) describes a sample path rather than one state.
Practice 8
Starting from \(0\) and adding \(2\) each time gives
\[ \boxed{0,2,4,6,8}. \]Practice 9
The better description is
\[ \boxed{(\text{condition},\text{age})}. \]Age affects the future failure probability, so omitting it would remove information relevant to the system's evolution.
Practice 10
The distribution vector is
\[ \boxed{\mathbf{p}^{(n)}=(0.1,0.4,0.2,0.3)}. \]Every entry is nonnegative and
\[ 0.1+0.4+0.2+0.3=1, \]so it is a valid probability distribution.
What to Remember
A state space is the set of all states allowed by a stochastic model:
\[ \boxed{X_n\in S}. \]- A state describes the system at one indexed point.
- The state space contains every state permitted by the model.
- State spaces may be finite, countably infinite, continuous, vector-valued, or constrained.
- The time index and the state space are separate parts of a stochastic process.
- The sample space \(\Omega\) contains complete random outcomes; the state space \(S\) contains process values.
- A sample path is an ordered progression of states through \(S\).
- Initial and later uncertainty can be represented by probability distributions over the states.
- Not every state must be reachable from every starting condition.
- Absorbing and boundary states have special transition behavior.
- A useful state contains enough information for the intended model without unnecessary detail.
- When necessary, the state can be augmented with additional variables or relevant history.
The central modeling principle is: define the state so that it captures the condition of the system in a form suitable for describing how that system can evolve.
Where We Go Next
A state space tells us where a stochastic process can be. The next question is how probabilities govern movement from the current state to the next one.
The next lesson, Markov Chains, introduces a fundamental class of stochastic processes in which the probability distribution of the next state is determined by the current state through specified transition probabilities.