Pseudo-Random Monte-Carlo Methods

Article type: Research Article

Authors: Kramosil, Ivan

Affiliations: Institute of Information Theory and Automation, Czechoslovak Academy of Sciences

Abstract: In this paper we investigate the Monte-Carlo method for estimation of the unknown probability of a random event on the ground of relative frequencies and under the condition that random sampling is replaced by a deterministic side input producing binary sequences of high algorithmic complexity. It is proved that if this complexity exceeds a treshold value, the sequences may be used in the Monte-Carlo methods instead of random samples as the obtained estimates converge to the estimated probability when the length of these binary sequences increases.

Keywords: Monte-Carlo methods, random sampling, statistical estimates, pseudo-random numbers, universal Turing machine, binary strings, algorithmic complexity

DOI: 10.3233/FI-1982-53-405

Journal: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 301-312, 1982