On the Monte Carlo simulation of physical systems (Q1182572)

A pseudorandom number generator can be modeled as a dynamical system \(T\), \[ P_ k=T\circ T\circ\dots\circ T\circ P_ 0\equiv T^ kP_ 0, \] where \(P_ k(X_ 1^{(k)},X_ 2^{(k)},\dots,X_ d^{(k)})\) is a random point in the \(d\)-dimensional space \(\Pi^ d\). For example, if \(A\) is a \(d\times d\) integer matrix with determinant equal to one (so \(A^{- 1}\) is integer too) then \[ X_ i^{(k)}=\sum^ d_{j=1}A_{ij}X_ j^{(k-1)}\mod 1,\tag{*} \] is an example of such a dynamical system. The error due to using a pseudorandom generator (instead of a true one) can be estimated by the discrepancy \(D_ N\) defined by \textit{S. M. Ermakov} and \textit{G. A. Mikhailov} [A course in statistical modeling (1976; Zbl 0462.65005)] and recast, using a result of \textit{I. M. Sobol'} [The Monte Carlo method (1972; Zbl 0235.62003)] as satisfying \[ \left| {1\over N}\sum^{N-1}_ 0f(P_ k)-\int_{\Pi^ d}f(P)dP\right| \leq C{D_ N(T)\over N}, \] where \(C\) is a constant, for any \(C^ 1\) function \(f\). In this one wants a pseudorandom sequence entailing the slowest growth for \(D_ N\). But \(D_ N\) will grow slowest for a dynamical system \(T\) with maximal mixing or relaxation character. It is known that Kolmogorov \(K\)-systems relax with exponential rate and hence are good candidates for pseudorandom generators. The dynamical system (*) above is a \(K\)-system if and only if all the eigenvalues \(\lambda_{ij}\) of \(A\) are in modulus different from unity. The Sinai-Arov formula for the entropy of a dynamical system gives \(h(T)=\sum_{|\lambda_ k|>1}\ln|\lambda_ k|\) and its relaxation time is \(\tau\leq(\ln(1/\delta V^ d_ 0)/h(T))\) where \(\delta V^ d_ 0\ll 1/K\) is a small volume of \(\Pi^ d\).