scientific article; zbMATH DE number 3878357
[For the entire collection see Zbl 0531.00015.] The unknown measure of a measurable subset of the unit real interval is estimated using an appropriate Monte-Carlo method. The random sample is simulated by a binary sequence of high algorithmic complexity and the tested set is supposed to be effectively decidable by a Turing machine. Under such conditions, if the algorithmic complexity of the pseudo-random input in question exceeds a threshold value, then the described Monte- Carlo method yields the correct value of the estimated measure. Moreover, if the computational complexity of the indicator (characteristic function) of the tested set is uniformly bounded, then the mentioned threshold value can be effectively computed.
- An analysis of Monte Carlo algorithms for counting problems
- scientific article; zbMATH DE number 2186130 (Why is no real title available?)
- Probabilistic-algebraic algorithms of Monte Carlo methods
- scientific article; zbMATH DE number 3866254 (Why is no real title available?)
- scientific article; zbMATH DE number 4160064 (Why is no real title available?)
- scientific article; zbMATH DE number 4011516 (Why is no real title available?)
- Monte-Carlo approximation algorithms for enumeration problems
- Monte Carlo Simulation of Infinite Series
- Monte Carlo computability
- Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
- An Optimal Algorithm for Monte Carlo Estimation
- On the Power of Restricted Monte Carlo Algorithms
- Complexity of Multilevel Monte Carlo Tau-Leaping
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3343437)