A new method is introduced to create artificial time sequences that fulfil given constraints but are random otherwise. Constraints are usually derived from a measured signal for which surrogate data are to be generated. They are fulfilled by minimizing a suitable cost function using simulated annealing. A wide variety of structures can be imposed on the surrogate series, including multivariate, nonlinear, and nonstationary properties. When the linear correlation structure is to be preserved, the new approach avoids certain artifacts generated by Fourier-based randomization schemes. [S0031-9007(98) Randomization of data and Monte Carlo resampling of probability distributions is a common technique in statistics [1] . In the context of nonlinear time series analysis it has been discussed by several authors and is usually referred to as the method of surrogate data [2] . A null hypothesis for the nature of a time series can be tested by comparing the value of an observable g obtained using the data with values obtained using a collection of surrogate time series representing the null hypothesis. All but the simplest null assumptions allow for certain structures, for example, linear serial correlations. There are two distinct ways to implement such structures when creating surrogate series. Traditional bootstrap methods use explicit model equations that have to be extracted from the data. This typical realizations approach can be very powerful for the computation of confidence intervals, provided the model equations can be extracted successfully. As discussed in Ref. [3], the alternative approach of constrained realizations is more suitable for the purpose of hypothesis testing. It avoids the fitting of model equations by directly imposing the desired structures onto the randomized time series. However, the choice of possible null hypothesis has so far been limited by the difficulty of imposing arbitrary structures on otherwise random sequences. Algorithms exist mainly for the following cases. (1) The null hypothesis of independent random numbers from a fixed but unknown distribution can be tested against permutations without repetition of the data since these conserve the sample distribution exactly. This paper will introduce a general method for generating random time sequences subject to quite general constraints. Any null hypothesis that leads to a complete set of observables can thus be tested for. All of the above cases can be dealt with (often with higher accuracy), but also multivariate, nonstationary, nonlinear, or other constraints can be implemented. In all of the applications in this paper, the single time probability distribution will be one of the constraints, leading to the requirement that the randomized sequence is a permutation of a fixed collection of values. All other constraints, for example part or all of the lags of the autocorrelation function, will be formulated in terms of a cost function which is then minimized among all possible permutations by the method of simulated annealing. After giving the actual randomization scheme we will discuss some major applications. We will show that the algorithm yields a more accurate nonlinearity test and avoids known artifacts that are introduced by end effects with ordinary, Fourier-based surrogates [6, 7] . We will also give examples with a more general null hypothesis than that of a rescaled stationary linear stochastic process. For these examples, previous methods could not provide appropriate surrogates. The algorithm is conceptually very simple: (1) Specify constraints C i ͕͑x n ͖͒ 0 in terms of a cost function E͕͑x n ͖͒, constructed to have a global minimum when the constraint is fulfilled. (2) Minimize E͕͑x n ͖͒ among all permutations ͕x n ͖ of a time series ͕x n ͖ by simulated annealing. Configurations are updated by exchanging pairs in ͕x n ͖. Examples of its use will be given below. The simulated annealing method is particularly useful for combinatorial minimization with false minima. It goes back to Metropolis et al. [8], and is thoroughly discussed in the literature [9] . Essentially, the cost function is interpreted as an energy in a thermodynamic system. At some finite "temperature" T, system configurations are visited consecutively with a probability according to the Boltzmann distribution e 2E͞T of the canonical ensemble. This is achieved by accepting changes of the configuration with a probability p 1 if the energy is decreased, ͑DE , 0͒ 0031-9007͞98͞80(10)͞2105(4)$15.00
In close relation to the work of the manuscript, general property-based time series randomization with the Metropolis method was discussed in REF .
Constrained Randomization of Time Series Data
Physical Review Letters
Physics