Stochastic Simulation

CHAPTER 4

Stochastic Models

In Chapter 3 we were concerned almost exclusively with generating independent samples from specified distributions. In the simplest case this univariate distribution is the model, but often the stochastic model will utilize several dependent random variables. Constructing realizations with structured dependence has attracted much less attention. Many stochastic models can be simulated in the “obvious” way from their definitions, for example renewal processes. Nevertheless some tricks can be helpful and are presented below.

4.1.   ORDER STATISTICS

Order statistics present perhaps the simplest form of dependence. An independent sample (X₁,..., X_n) is rearranged into increasing order as X₍₁₎ < ··· < X_(n). The obvious way to do this is to sort the sample after generation. The fastest general-purpose sorting algorithms need O(n ln n) time to sort n items (Knuth, 1973b), so there will be a value of n for which the cost of sorting will dominate the cost of sampling. Typically this occurs for n in the range 100–10,000.

The alternative is to generate the sample in order. By taking X_(i) = F⁻(U_(i)) we can reduce the problem to that of generating an ordered sample of random numbers, although in practice forming F⁻ may be very slow. Two methods have been suggested.

1.   Sequential. Let U₁, …, U_n ~ U(0, 1). Define U_(k) = U_{(k + 1)} × (U_k)^1/k, k = n − 1, n − 2, …, 1. ...