'Monte Carlo' Algorithms and Data Structures

Dated Nov 7, 2021; last modified on Mon, 05 Sep 2022

remarks that most algorithm researchers don’t use the terms “Monte Carlo” and “Las Vegas” to desribe such algorithms.

These algorithms are always fast (as opposed to having a small probability of being slow), but they return the wrong answer with some small probability.

Some MC algorithms have one-sided errors, e.g. a false-biased MC algorithm will always be correct when it returns false, but will be wrong with some bounded probability \(p\).

The error/success of some MC decision algorithms can be reduced/amplified by running the algorithm \(k\) times.

is more assertive in that it doesn’t say “some MC decision algorithms”. However, algorithms like membership testing via a Bloom Filter would not benefit from subsequent runs.

is interested in the sort of analysis that defines an error rate \(\delta\), and analyze the resources required to guarantee that the output is correct with probability \(1 - \delta\). “High probability” correctness is defined as \(\delta < 1/n^c\) for some constant \(c\).

Algorithms > Filtering and Streaming. Jeff Erickson. jeffe.cs.illinois.edu . Accessed Nov 7, 2021.

Monte Carlo Algorithm. en.wikipedia.org . Accessed Nov 7, 2021.

		Random Link ¯\_(ツ)_/¯
Nov 7, 2021	»	Bloom Filters 5 min; updated Sep 5, 2022 Bloom Filters In true fashion to Stigler’s Law of Eponymy (no scientific discovery is named after its original discoverer ), Ross Ashby (1960) did a probabilistic analysis of Calvin Mooers’s Zatocoding (1947) (coding system for library cards). This predates Burton Bloom’s work (1970). Motivation A Bloom filter for a set \(X: \{x_1, x_2, …, x_n\} \) from some universe \(\mathbb{U}\) allows one to test whether a given item \(x \in \mathbb{B}\) is an element of \(X\)....