Library

PFA · Stochastic

Try until it works: amplification

Each a is an attempt that succeeds with probability 1/2, and success is permanent. After n attempts the chance of at least one success is 1 − 2⁻ⁿ, which passes the cut-point 0.9 at n = 4. Repetition turns a coin flip into near-certainty — the idea behind every randomised algorithm’s error bound.

tryingsuccessaaa
The machine as drawn — 2 states, 3 transitions.

The author’s examples, run

aaaa → acceptaaaaa → acceptaaaaaa → acceptaaaaaaaaaaaa → acceptaaa → rejectε → rejectaa → rejecta → reject