Page 309 -

308 L.R Izquierdo et al.

seem to get us close to the exact probability distribution. The standard error, which
is inversely proportional to the square root of the sample size (i.e. the number of
runs), is naturally much lower in these latter cases.
When, like in this example, the space of all possible outcomes in the distribution
under analysis is finite (the number of walkers in a house must be an integer between
0 and 100), one can go further and calculate confidence intervals for the obtained
frequencies. This is easily conducted when one realises that the exact probability
distribution is a multinomial. Genz and Kwong (2000) show how to calculate these
confidence intervals.
To conclude this section, let us emphasise that all that has been written here
applies to any statistic obtained from any computer model. In particular, the statistic
may refer to predefined regimes (e.g. ‘number of time-steps between 0 and 100
where there are more than 20 walkers in a house’) or to various time-steps (e.g.
‘total number of walkers in a house in odd time-steps in between time-steps 50 and
200’). These statistics, like any other one, follow a specific probability distribution
that can be approximated to any degree of accuracy by running the computer model.

13.7 Mathematical Analysis: Time-Homogenous Markov
Chains

The whole range of mathematical techniques that can be used to analyse formal
systems is too broad to be reviewed here. Instead, we focus on one specific technique
that seems to us particularly useful to analyse social simulation models: Markov
chain analysis. Besides, there are multiple synergies to be exploited by using
Markov chain analysis and computer simulation together, as we will see in the next
section.
Our first objective is to learn how to represent a particular computer model as
a time-homogeneous Markov chain. This alternative representation of the model
will allow us to use several simple mathematical results that will prove useful
to understand the dynamics of the model. We therefore start by describing time-
homogeneous Markov chains.

13.7.1 What Is a Time-Homogeneous Markov Chain?

Consider a system that in time-step n Df1, 2, 3, ::: g may be in one of a finite
number of possible states S Dfs 1 , s 2 , ::: , s M g.The set S is called the state space;
in this chapter, we only consider finite state spaces. 10 Let the sequence of random
variables X n 2 S represent the state of the system in time-step n. As an example,
X 3 D s 9 means that at time n D 3, the system is in state s 9 . The system starts at a

10 The term ‘Markov chain’ allows for countably infinite state spaces too (Karr 1990).