O'Reilly logo

Stochastic Simulation by Brian D. Ripley

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 (X1,..., Xn) is rearranged into increasing order as X(1) < ··· < 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 U1, …, Un ~ U(0, 1). Define Image U(k) = U(k + 1) × (Uk)1/k, k = n − 1, n − 2, …, 1. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required