Randomized Algorithm

Updated 13 Aug 2026

•
Definition
- •
  an algorithm that, in addition to its normal input $M$ , takes an implicit random input $R$ (freshly sampled, uniform, on every run) — so running it twice on the same $M$ can produce different outputs
- •
  $y \leftarrow A(m;r)$ where $r \xleftarrow{R} \{ 0, 1 \}^n$ , thus $y \xleftarrow{R} A(m)$
•
Distinguish from
- •
  a deterministic algorithm, which always produces the same output for the same input
•
Key idea
- •
  a randomized algorithm effectively defines a random variable — a distribution over its possible outputs, for each fixed input $M$
•
Example
- •
  probabilistic encryption: $E(k, m; R)$ defines a distribution over ciphertexts, for a fixed key and message, as $R$ varies
•
Related
- •
  Computational Cipher
- •
  Random Variable

Linked references 1