A fenti definíció egy i input esetén nem írja le mi a gép futása. A futáshoz tudnunk kell az új, véletlen biteket tartalmazó szalag r tartalmát. Ekkor számol ki T gépünk egy egyértelmúen definiált T(i,r) eredményt. A futás és az eredmény egy valószínűségi változó. Beszélhetünk az elfogadás és elvetés pelfogad és pelvet valószínűségéről (pelfogad+pelvet=1).
Mikor mondjuk, hogy egy i inputot elfogad gépünk? Mikor mondjuk, hogy T az L nyelvet fogadta el? Több lehetőség is van erre a definícióra.
I. definíció: Ha i az L nyelv eleme, akkor elvárjuk, hogy pelfogad> 1/2 teljesüljön. Ha i nem az L nyelv eleme, akkor elvárjuk, hogy algoritmusunk elvesse. Ha ráadásul eljárásunk polinomiális, akkor azt mondjuk, hogy az L nyelv az RP nyelvosztály eleme.
I.' definíció: Ha i nem az L nyelv eleme, akkor elvárjuk, hogy pelvet> 1/2 teljesüljön. Ha i az L nyelv eleme, akkor elvárjuk, hogy algoritmusunk elfogadja. Ha ráadásul eljárásunk polinomiális, akkor azt mondjuk, hogy az L nyelv az coRP nyelvosztály eleme.
II. definíció: Ha i az L nyelv eleme, akkor elvárjuk, hogy pelfogad> 2/3 teljesüljön. Ha i nem az L nyelv eleme, akkor elvárjuk, hogy pelvet> 2/3 teljesüljön. Ha ráadásul eljárásunk polinomiális, akkor azt mondjuk, hogy az L nyelv az BPP nyelvosztály eleme.
A véletlen számokat használó algoritmusok nagyon fontosak a gyakorlatban és elméletben. Standard referencia Rajeev Motwani és Prabhakar Raghavan Randomized Algorithms könyve A legtöbb egyetem külön kurzust szentel ennek a témakörnek. Néhány kurzus honlapját mellékelem. Ez a lista egy gyors keresés eredménye és nem elbírált válogatás: