Randomized Algorithm

A Randomized Algorithm is an Algorithm that uses a Random Function in its logic.

• AKA: Probabilistic Algorithm.
• Context:
  • It can solve a Randomization Task.
• Example(s):
  • a Monte Carlo Algorithm.
• See: Non-Deterministic Algorithm.

---

---

References

2009

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Randomized_algorithm
  • A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.
  • In both cases, random performance and random output, the term "algorithm" for a procedure is somewhat questionable, as it is no longer formally effective. However, in some cases, probabilistic algorithms are the only practical means of solving a problem.
  • In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

2005

• (Klinberg & Tardos, 2005) ⇒ Jon Kleinberg, and Éva Tardos. (2005). "Algorithm Design." Addison-Wesley. ISBN:0-321-29535-8
  • Chapter 13: Randomized Algorithms http://www.aw-bc.com/info/kleinberg/assets/downloads/ch13.pdf

1995

• (Motwani & Raghavan, 1995) ⇒ Rajeev Motwani, and Prabhakar Raghavan. (1995). "Randomized Algorithms." Cambridge University Press. ISBN:0521474655

---