## P 1 y26

and c(lh = 2cos[j(l - })]r(l - f) does not depend on f. Here T is Euler's gamma-function.61

The case of approximately constant power spectrum is called white noise, since in this case all the frequencies carry the same energy (as in white light which is mixture of the colors of the rainbow corresponding to all different frequencies). The case Sif) - 1 If1 is nicknamed "brown" noise since it describes Brownian motion and the case Sif) - 1// is called 1//-noise or "red" noise. The case Sif) - l/f^, with 0 < /? < 1 corresponds to long range power-law correlations in the signal and is often called fractal noise. The power spectrum of the fractal noise looks like a straight line with slope —/? on a log-log plot.

In case of long range anti-correlations (as in the anti-ferromagnetic Ising model, Fig. 6) the correlation function oscillates with certain angular frequency (Oq. In this case, the behavior of the correlation function can be modeled as C'(r) ~ |/j~rcos(ft)br). Analogous calculations61 lead to Sica) = - + |fflb + 0j\~^)/2. This expression is analytical at ft) = 0, but it has power law singularities at ft) = ±03^. Thus in case of anti-correlations, the graph of power spectrum does not look like a straight line on a simple log-log plot. One must plot InP(w) versus ln|ffib -fi)| in order to see a straight line with the slope

If the correlation function decays for r —» °° faster than r ', its Fourier transform must be a continuous function limited for* 00 and, therefore, cannot have singularity at any f. The log-log graph of such a function plotted against f-fo has zero slope in the limit ln|/-/j| —> ± so one can conclude that P = 0 if y> 1. If y = 1, the Fourier transform may have logarithmic singularities, which also corresponds to zero slope p = 0.

### Discrete Fourier Transform

In reality, however, we never deal with infinitely long time series. Usually we have a system of N equidistant measurements. In this case, a sequence of Admeasurements s(k), k = 0,1 ,...N-1, can be regarded as vector s of the TV-dimensional space. Accordingly, one can define a discrete Fourier transform,62'63 of this vector not as an integral but as a sum s = Fs= N^s{k)e2^'N, (27)

which can also be regarded as a vector in jV-dimensional space with components s (q), q = 0,1 ,...N — 1. The fractional quantity/* = qlN plays the role of frequency. As one can see, the discrete Fourier transform can be expressed in a matrix form s = Fs, where F is the matrix with elements fkq = expilTCikql N). Analogously, vector s can be restored by applying an inverse Fourier transform:

If one assumes that the sequence s(k) is periodic, i.e., s(k + N) = s(k), then the square of the discrete Fourier transform is proportional to the discrete Fourier transform of the correlation function as in case of the continuum Fourier transform.62'63 Indeed, | i(/)|2 = FXf=01'(*M*+ r).

It is natural to define the discrete power spectrum S(f) to be exactly equal to the Fourier transform of the correlation function. Since the correlation function is defined as C(r) = l/Nlk:0 s(k)s(k + r) - (s)2, which involves division by N and subtraction of the average value, S(f) = \ s (f)\2IN(or f> 0 and 5(0) = 0, because s (0) = N(s(k)).

The correlation function can be thus obtained as an inverse discrete Fourier transform of a power spectrum. Since frequencies -q/Nand \-qlNare equivalent (due to 2n- periodicity of sines and cosines) and, for real signal, s (-/) and s if) are complex conjugates, the values S(ql N) and 5(1 — q/N) are equal to each other, so we can compute power spectra only up to the highest frequency q/N = 1/2.

If A^ is a natural power of two, N = 2", the discrete Fourier transform can be computed by a very efficient algorithm known as the Fast Fourier Transform (FFT).62,63 The amount of operations in this algorithm grows linearly with N. This makes FFT a standard tool to analyze correlation properties of the time series.

Since the sequences we study are formed by random variables, the power spectra of such sequences are random variables themselves. Before proceeding further, it is important to calculate the power spectrum of a completely uncorrelated sequence of length N. As we have seen in section "Correlation Function", C\0) > 0 has the meaning of the average square amplitude (variance) of the original signal, while for r > 0, the values of C(r) are Gaussian random variables with zero mean and standard deviation equal to Analogous conclusions can be made for S(f). According to the central limit theorem,21 the sum of TV random uncorrelated variables s{k)exp(2inkf) converges to a Gaussian distribution with mean equal to the sum of means and variance equal to the sum of variances of individual terms. Thus, we can conclude (after some algebra) that all S(f) are identically distributed independent random variables with an exponential probability density P(S(f)) = l/[C(0)]exp[-5(/)/C(0)]. So the power spectrum of an uncorrected sequence has an extremely noisy graph. To reduce the noise one can average power spectra for many sequences, and the average value of the power spectrum will converge to a horizontal line (S(f)) = C(0) which is called the white noise level. An equivalent method is to average the values S(f) for k neighboring frequencies f,f+ 1 IN,f+ 2/N,...,f+k/N. Note that (S(f)) is equal to the Fourier transform of (C(r)), direcdy computed using Eq.(27), since as we see above, (C(r)) = 0 for r ^ 0.

In the following, we will illustrate the usage of FFT computing power spectrum for a one-and two-dimensional Ising models near critical points.

Figure 7 shows the power spectrum for the one-dimensional Ising model consisting of L = 216 spins for T= 0.5 = 27.3), T= 0.6 (§ = 14.01), T= 1.0 (§ = 3.67). The power spectrum of the entire system for N= L is very noisy so we show the running averages of the original data using window of 32 adjacent frequencies (gray fluctuating curves). The averages of 32 power spectra computed for 32 non-overlapping windows each of size N= 211 produce a very similar Figure7. A) Power Spectrum of the one-dimensional Ising model with L = 216 spins for 7"= 0.5 (¿J = 27.3), T= 0.6 (4= 14.0), and T= 1.0 = 3.67). Smooth lines show analytical result Eq. (29). B) Inverse power spectrum of the same data plotted versus f2. The slopes at f2 = 0 are proportional to the values of the correlation length.

Figure7. A) Power Spectrum of the one-dimensional Ising model with L = 216 spins for 7"= 0.5 (¿J = 27.3), T= 0.6 (4= 14.0), and T= 1.0 = 3.67). Smooth lines show analytical result Eq. (29). B) Inverse power spectrum of the same data plotted versus f2. The slopes at f2 = 0 are proportional to the values of the correlation length.

graph (not shown). The smooth bold lines represent exact discrete Fourier transform of the correlation function computed using Eqs. (4), (17) and (27)

0 0