= Randomized algorithm
{wiki}
A randomized algorithm makes some choices using random bits.
For a fixed <input>, the random <bits> can change the path taken by a <randomized algorithm>, its <output>, or its running time. Specify the distribution of those choices and which guarantee is required: <one-sided error> permits mistakes of only one kind, whereas <ZPP> requires a correct answer and bounds the expected running time. <Polynomial identity testing> makes this distinction concrete: choosing different <field> elements changes whether a nonidentity is detected.
A <uniform distribution on a finite set> must be implemented faithfully. To choose uniformly from $\{0,1,2,3,4\}$ using fair <independent> <bits>, read three <bits> as a number from zero to seven, discard five through seven, and repeat until a permitted value appears. Each retained value has the same chance. Taking the three-bit number modulo five instead would give zero, one and two twice as many preimages as three and four, invalidating a calculation that assumes equal chances.
Back to article page
