Page 119 - A First Course In Stochastic Models

COMPUTATION OF THE EQUILIBRIUM PROBABILITIES 111

infinite state space I = {1, 2, . . . } and one-step transition probabilities p ij satisfying
(3.4.3). Then a truncation integer N must be used.

3.4.2 Geometric Tail Approach for an Infinite State Space
Many applications of Markov chains involve an infinite state space. What one
usually does to solve numerically the infinite set of equilibrium equations is to
approximate the infinite-state Markov model by a truncated model with finitely
many states so that the probability mass of the deleted states is very small. Indeed,
for a finite-state truncation with a sufficiently large number of states, the differ-
ence between the two models will be negligible from a computational point of
view. However, such a truncation often leads to a finite but very large system of
linear equations whose numerical solution will be quite time-consuming, although
an arsenal of good methods is available to solve the equilibrium equations of
a finite Markov chain. Moreover, it is somewhat disconcerting that we need a
brute-force approximation to solve the infinite-state model numerically. Usually
we introduce infinite-state models to obtain mathematical simplification, and now
in its numerical analysis using a brute-force truncation we are proceeding in the
reverse direction. Fortunately, many applications allow for a much simpler and
more satisfactory approach to solving the infinite set of state equations. Under
rather general conditions the state probabilities exhibit a geometric tail behaviour
that can be exploited to reduce the infinite system of state equations to a finite set
of linear equations. The geometric tail approach results in a finite system of linear
equations whose size is usually much smaller than the size of the finite system
obtained from a brute-force truncation. It is a robust approach that is easy to use
by practitioners.
Consider a discrete-time Markov chain whose state space is one-dimensional and
is given by
I = {0, 1, . . . }.
Let us assume that the equilibrium probabilities π j , j ∈ I, exhibit the geometric
tail behaviour
j
π j ∼ γ η as j → ∞ (3.4.5)
for some constants γ > 0 and 0 < η < 1. Here f (x) ∼ g(x) as x → ∞ means
that lim x→∞ f (x)/g(x) = 1. Below we will discuss conditions under which (3.4.5)
holds. First we demonstrate how the geometric tail behaviour can be exploited to
reduce the infinite system of state equations to a finite system of linear equations.
It will be seen below that the decay factor η in (3.4.5) can usually be computed
beforehand by solving a non-linear equation in a single variable. Solving a non-
linear equation in a single variable is standard fare in numerical analysis. In most
applications it is not possible to compute the constant γ beforehand. Fortunately,
we do not need the constant γ in our approach. The asymptotic expansion is only
used by