Exercise 4.11Z: C Program "acf2"

C program $2$ for ACF–calculation

You can see on the right the C program "acf2" for calculating the discrete ACF values $\varphi_x(k)$ with index $k = 0$, ... , $l$.

In contrast to the program "acf1" from Exercise 4.11, here the algorithm described in the theory part is applied directly. It should be noted:

Let the long value passed to the program be $l=10$.
The calculated ACF values $\varphi_x(0)$, ... , $\varphi_x(10)$ are returned to the main program with the float field $\rm ACF[ \ ]$. In lines 7 and 8, this field is prefilled with zeros.
The random variable $x( \ )$ is defined as a float function in line 4, as is an auxiliary field ${\rm H}[10000 ]$, into which the $N = 10000$ samples $x_\nu$ are entered (lines 9 and 10).
The names of the control variables in line 6 are adapted to the given algorithm.
The actual ACF calculation is done from line 11. This program part is marked red in the program code.

Hints:

This exercise belongs to the chapter Auto-Correlation Function.
In particular, reference is made to the pages
- Numerical ACF determination,
- Accuracy of the numerical ACF calculation.

Questions

$S_{k=0} \ = \ $

$S_{k=10} \ = \ $

	The calculation time increases linearly with $l + 1$, i.e. with the number of ACF values to be calculated.
	The calculation time increases quadratically with the number $N$ of samples considered.
	The calculation becomes more accurate as $N$ increases.
	If a float variable is represented with $\rm 4 \ bytes$, "acf2" needs at least $4 \cdot N$ bytes of memory.

	The stronger the internal statistical bindings of the process are, the more inexact is the ACF result for a given $N$.
	The stronger the internal statistical bindings of the process are, the more accurate is the ACF result for a given $N$.
	If the process has statistical bindings, the errors of the numerical ACF calculation are also correlated. Example: If the value $\varphi_x(k=5)$ is too large, it is very likely that $\varphi_x(k=4)$ and $\varphi_x(k=6)$ will also be too large.

Solution

(1) To calculate the ACF value $\varphi_x(0)$ you have to average over $\underline{N =10000}$ summands, for $\varphi_x(10)$ only over $\underline{N = 9990}$.

(2) Correct are the proposed solutions 1, 3 and 4:

The computation time increases approximately linearly with $N$ and $l + 1$ as can be seen from the ACF calculation highlighted in red.
In contrast, the computation time for the other parts of the program can be neglected.
Naturally, the calculation also becomes more accurate with increasing $N$.
This goes here – in contrast to the program "acf1" of Exercise 4.11 – however at the expense of the necessary memory requirement.
Since each float variable takes up exactly four bytes, the auxiliary field ${\rm H}[10000 ]$ alone requires a memory of 40 kByte.

(3) Correct are the suggested solutions 1 and 3:

The stronger the statistical bindings within the random process, the less accurate is the ACF calculation for a given $N$.
This fact can be illustrated for example by the power calculation $($ACF value at $k=0)$ :
- If all $N$ samples are statistically independent, then all contributions provide the maximum information about the ACF value $\varphi_x(k=0)$.
- However, if there are statistical bindings between $x_\nu$ and $x_{\nu+1}$, but not between $x_\nu$ and $x_{\nu+2}$, only half of all samples provide the full information about $\varphi_x(k=0)$ and the others provide only limited information.
This loss of information based on correlations can only be compensated in this example by doubling $N$ .
The last statement is also true, as explained in detail on the page "Accuracy of the numerical ACF calculation" in the theory section.