Στην θεωρητική πληροφορική, ένας πιθανοτικός αλγόριθμος (ή τυχαιοποιημένος ή τυχαίος αλγόριθμος) είναι ένας αλγόριθμος που χρησιμοποιεί τυχαιότητα ως μέρος της λογικής του ή της διαδικασίας του. Ο αλγόριθμος παίρνει ομοιόμορφα τυχαία bits ως βοηθητική είσοδο τα οποία χρησιμοποιεί για να καθοδηγήσει την εκτέλεσή του, με στόχο να επιτύχει καλή απόδοση στη "μέση περίπτωση" (όπως αυτή ορίζεται σε σχέση με τα τυχαία bits). Επομένως είτε ο χρόνος εκτέλεσης είτε η έξοδος (ή και τα δύο) είναι τυχαίες μεταβλητές.

Οι πιθανοτικοί αλγόριθμοι διακρίνονται σε αυτούς που πάντοτε τερματίζουν με τη σωστή απάντηση, αλλά όπου ο αναμενόμενος χρόνος εκτέλεσης είναι πεπερασμένος (αλγόριθμοι Λας Βέγκας, για παράδειγμα ο αλγόριθμος ταξινόμησης Quicksort^[1]) και αλγόριθμους που με κάποια πιθανότητα μπορεί να δώσουν ένα λανθασμένο αποτέλεσμα (αλγόριθμοι Monte Carlo, για παράδειγμα ο αλγόριθμος Monte Carlo για το πρόβλημα του ελάχιστου συνόλου ανάδρασης κορυφών^[2]) ή να αποτύχουν να παράγουν αποτέλεσμα είτε σηματοδοτώντας μια αποτυχία είτε αποτυγχάνοντας να τερματίσουν. Σε ορισμένες περιπτώσεις, οι πιθανοτικοί αλγόριθμοι είναι το μόνο πρακτικό μέσο επίλυσης ενός προβλήματος.^[3]

Είναι κοινή πρακτική, οι πιθανοτικοί αλγόριθμοι προσεγγίζονται χρησιμοποιώντας μια γεννήτρια ψευδοτυχαίων αριθμών στη θέση μιας πραγματικής πηγής τυχαίων bits. Μια τέτοια υλοποίηση μπορεί να αποκλίνει από την αναμενόμενη θεωρητική συμπεριφορά και τις μαθηματικές εγγυήσεις που μπορεί να εξαρτώνται από την ύπαρξη μιας ιδανικής πραγματικής γεννήτριας τυχαίων αριθμών.

Ως παράδειγμα, θα δούμε το πρόβλημα της εύρεσης ενός στοιχείου 'a' σε έναν πίνακα n στοιχείων.

Είσοδος : Ένας πίνακας ${\displaystyle n\geq 2}$ στοιχείων, στον οποίο τα μισά είναι a και τα άλλα μισά είναι b.

Έξοδος: Βρείτε ένα a στον πίνακα.

Δίνουμε δύο εκδοχές του αλγορίθμου, έναν αλγόριθμο Λας Βέγκας και έναν αλγόριθμο Μόντε Κάρλο .

Ξεκινάμε με τον αλγόριθμο Λας Βέγκας:

findingA_LV(array A, n)
begin
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
  until A[j] = 'a'
end

Αυτός ο αλγόριθμος πετυχαίνει με πιθανότητα 1. Ο αριθμός των επαναλήψεων δεν είναι σταθερός και μπορεί να είναι αυθαίρετα μεγάλος, αλλά η αναμενόμενη τιμή των επαναλήψεων είναι

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

Επειδή είναι σταθερά, ο αναμενόμενος χρόνος εκτέλεσης για πολλές κλήσεις είναι ${\displaystyle \Theta (1)}$.

Συνεχίζουμε με τον αλγόριθμο Μόντε Κάρλο:

findingA_MC(array A, n, k)
begin
  i := 0
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
    i := i + 1
  until i = k or A[j] = 'a'
end

Αν βρεθεί ένα 'a', ο αλγόριθμος πετυχαίνει, διαφορετικά ο αλγόριθμος αποτυγχάνει. Αφού σε κάθε επανάληψη ο αλγόριθμος πετυχαίνει με πιθανότητα ${\displaystyle 1/2}$, και οι επαναλήψεις είναι ανεξάρτητες, μετά από k επαναλήψεις, η πιθανότητα να βρεθεί ένα ' a ' είναι:

Δεν είναι εγγυημένο ότι ο αλγόριθμος θα πετύχει κάθε φορά, αλλά είναι εγγυημένο ότι ο χρόνος εκτέλεσης είναι πεπερασμένος, καθώς ο αριθμός των επαναλήψεων είναι πάντα μικρότερος ή ίσος του k. Θεωρώντας το k ως σταθερά, ο χρόνος εκτέλεσης (αναμενόμενος και απόλυτος) είναι ${\displaystyle \Theta (1)}$ .

Οι πιθανοτικοί αλγόριθμοι είναι ιδιαίτερα χρήσιμοι όταν υπάρχει ένας κακόβουλος "αντίπαλος" που προσπαθεί σκόπιμα να δώσει μία είσοδο στον αλγόριθμο ώστε να καθυστερήσει τον αλγόριθμο (βλ . χειρότερη περίπτωση πολυπλοκότητα και ανταγωνιστική ανάλυση (αλγόριθμοι)) όπως στο δίλημμα του φυλακισμένου. Αυτός είναι και ο λόγος που η τυχαιότητα είναι πανταχού παρούσα στην κρυπτογραφία. Σε κρυπτογραφικές εφαρμογές, δεν μπορούν να χρησιμοποιηθούν ψευδοτυχαίοι αριθμοί, αφού ο αντίπαλος μπορεί να τους προβλέψει, καθιστώντας τον αλγόριθμο ντετερμινιστικό. Επομένως, απαιτείται είτε μια πηγή "πραγματικά" τυχαίων αριθμών είτε μια κρυπτογραφικά ασφαλής γεννήτρια ψευδοτυχαίων αριθμών . Ένας άλλος τομέας στον οποίο η τυχαιότητα είναι εγγενής είναι ο κβαντικός υπολογισμός .

Στο παραπάνω παράδειγμα, ο αλγόριθμος Λας Βέγκας δίνει πάντα τη σωστή απάντηση, αλλά ο χρόνος εκτέλεσης του είναι μια τυχαία μεταβλητή. Ο αλγόριθμος Monte Carlo (που σχετίζεται με τη μέθοδο προσομοίωσης Monte Carlo) εγγυάται ότι θα τερματίσει σε ένα πεπερασμένο χρονικό διάστημα, το μήκος του οποίου φράζεται από μία συνάρτηση του μεγέθους της εισόδου και της παραμέτρου k, αλλά επιτρέπει μια μικρή πιθανότητα σφάλματος. Παρατηρήστε ότι οποιοσδήποτε αλγόριθμος Λας Βέγκας μπορεί να μετατραπεί σε αλγόριθμο Μόντε Κάρλο (μέσω της ανισότητας Μάρκοφ), βάζοντάς του να επιστρέψει μία αυθαίρετη (πιθανώς λανθασμένη απάντηση) εάν αποτύχει να ολοκληρωθεί εντός του καθορισμένου χρόνου. Αντίθετα, εάν έχουμε έναν αποδοτικό αλγόριθμο για να ελέγξουμε εάν μια απάντηση είναι σωστή (στο παραπάνω παράδειγμα αυτό ήταν απλά `A[j] = a'), τότε ένας αλγόριθμος Monte Carlo μπορεί να μετατραπεί σε αλγόριθμο Λας Βέγκας εκτελώντας τον αλγόριθμο Monte Carlo επανειλημμένα μέχρι να λάβουμε μια σωστή απάντηση.

Η θεωρία της υπολογιστικής πολυπλοκότητας μοντελοποιεί πιθανοτικούς αλγόριθμους με τις πιθανοτικές μηχανές Turing. Στον τομέα έχουν μελετηθεί και οι αλγόριθμοι Λας Βέγκας και Μόντε Κάρλο, και επίσης έχουν διατυπωθεί αρκετές άλλες κλάσεις πολυπλοκότητας σχετικές με την τυχαιότητα. Η πιο βασική πιθανοτική κλάση πολυπλοκότητας είναι η RP, η οποία περιλαμβάνει προβλήματα απόφασης για τα οποία υπάρχει ένας αποδοτικός (που τρέχει σε πολυωνυμικό χρόνο) πιθανοτικός αλγόριθμος (ή ισοδύναμα μία πιθανοτική μηχανή Turing) που αναγνωρίζει τις περιπτώσεις ΟΧΙ με απόλυτη βεβαιότητα και αναγνωρίζει τις περιπτώσεις ΝΑΙ με πιθανότητα τουλάχιστον 1/2. Το συμπλήρωμα της κλάσης RP είναι η κλάση co-RP. Τα προβλήματα που έχουν (πιθανώς μη τερματιζόμενους) αλγόριθμους με πολυωνυμικό αναμενόμενο χρόνο εκτέλεσης και των οποίων η έξοδος είναι πάντα σωστή ανήκουν στην κλάση ZPP .

Η κλάση των προβλημάτων για τα οποία οι αλγόριθμοι έχουν πιθανότητα σφάλματος και στις ΝΑΙ και στις ΟΧΙ περιπτώσεις ονομάζεται BPP. Αυτή η κλάση είναι η αντίστοιχη πιθανοτική κλάση του P, δηλ το BPP αντιπροσωπεύει την κατηγορία των αποδοτικών πιθανοτικών αλγορίθμων.

Ο αλγόριθμος Quicksort για την ταξινόμηση ανακαλύφθηκε από τον Τόνι Χορ το 1959, και στη συνέχεια δημοσιεύτηκε το 1961.^[4] Την ίδια χρονιά, ο Χορ δημοσίευσε τον αλγόριθμο Quickselect^[5] που βρίσκει το διάμεσο στοιχείο μιας λίστας σε γραμμικό αναμενόμενο χρόνο. Το πρόβλημα του αν υπήρχε ντετερμινιστικός αλγόριθμος γραμμικού χρόνου παρέμεινε ανοιχτό μέχρι το 1973.^[6]

Το 1917, ο Henry Cabourn Pocklington εισήγαγε έναν πιθανοτικό αλγόριθμο γνωστό ως αλγόριθμος Pocklington για την αποτελεσματική εύρεση τετραγωνικών ριζών modulo πρώτων αριθμών.^[7] Το 1970, οElwyn Berlekamp εισήγαγε έναν τυχαιοποιημένο αλγόριθμο για τον αποτελεσματικό υπολογισμό των ριζών ενός πολυωνύμου σε ένα πεπερασμένο πεδίο.^[8] Το 1977, ο Robert M. Solovay και ο Volker Strassen ανακάλυψαν έναν αλγόριθμο για να ελέγχει αν ένας αριθμός είναι πρώτος σε πολυωνυμικό χρόνο. Λίγο αργότερα, ο Michael O. Rabin έδειξε ότι ο αλγόριθμος ελέγχου πρώτων του Miller (του 1976) μπορεί επίσης να μετατραπεί σε έναν πολυωνυμικό πιθανοτικό αλγόριθμο. Εκείνη την εποχή, δεν ήταν γνωστός κάποιος ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου για τον έλεγχο πρώτων αριθμών.

Μία από τις πρώτες πιθανοτικές δομές δεδομένων είναι ο πίνακας κατακερματισμού, ο οποίος εισήχθη το 1953 από τον Hans Peter Luhn στην IBM.^[9] Ο πίνακας κατακερματισμού του Luhn χρησιμοποιούσε μία αλυσίδα για την επίλυση συγκρούσεων και ήταν επίσης μια από τις πρώτες εφαρμογές συνδεδεμένων λιστών.^[9] Στη συνέχεια, το 1954, οι Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester και Arthur Samuel της IBM Research εισήγαγαν τη γραμμική εξέταση^[9], αν και ο Andrey Ershov ανεξάρτητα είχε την ίδια ιδέα το 1957.^[9] Το 1962, ο Donald Knuth πραγματοποίησε την πρώτη σωστή ανάλυση γραμμικής εξέτασης,^[9] αν και το σημείωμα που είχε την ανάλυσή του δεν δημοσιεύτηκε μέχρι αργότερα.^[10] Η πρώτη δημοσιευμένη ανάλυση ήταν από τον Konheim και τον Weiss το 1966.^[11]

Οι πρώτες αναλύσεις των πινάκων κατακερματισμού υπέθεταν ότι είτε υπάρχει πρόσβαση σε μια πλήρως τυχαία συνάρτηση κατακερματισμού είτε ότι τα κλειδιά ήταν τυχαία.^[9] Το 1979, οι Carter και Wegman εισήγαγαν τις καθολικές συναρτήσεις κατακερματισμού^[12] και έδειξαν ότι μπορούν να χρησιμοποιηθούν για την υλοποίηση αλυσιδωτών πινάκων κατακερματισμού με σταθερό αναμενόμενο χρόνο ανά πράξη.

Το 1970, ο Burton Howard Bloom εισήγαγε τα φίλτρα Bloom, μία δομή δεδομένων που δίνει προσεγγιστικές απαντήσεις για το αν ένα στοιχείο x ανήκει σε ένα σύνολο S. ^[13] Το 1989, ο Raimund Seidel και η Cecilia R. Aragon εισήγαγαν ένα πιθανοτικό και ισορροπημένο δυαδικό δέντρο αναζήτησης γνωστό ως treap.^[14] Την ίδια χρονιά, ο William Pugh παρουσίασε ένα άλλο τυχαιοποιημένο δέντρο αναζήτησης γνωστό ως λίστα παράλειψης.^[15]

Πριν γίνουν διαδεδομένοι οι πιθανοτικοί αλγόριθμοι στην επιστήμη των υπολογιστών, ο Πολ Έρντος έκανε δημοφιλή τη χρήση πιθανοτικών μεθόδων ως μια μαθηματική τεχνική για την απόδειξη ύπαρξης μαθηματικών αντικειμένων. Αυτή η τεχνική έχει γίνει γνωστή ως πιθανοτική μέθοδος.^[16] Ο Erdős έκανε την πρώτη του εφαρμογή της πιθανοτικής μεθόδου το 1947, όταν χρησιμοποίησε μια απλή πιθανοτική κατασκευή για να αποδείξει την ύπαρξη γράφων Ramsey. ^[17] Επίσης χρησιμοποίησε έναν πολύ πιο περίπλοκο πιθανοτικό αλγόριθμο το 1959 για να διαπιστώσει την ύπαρξη γράφων με υψηλή περιφέρεια και χρωματικό αριθμό.^[18][16]

Η γρήγορη ταξινόμηση είναι ένας γνωστός, ευρέως χρησιμοποιούμενος αλγόριθμος ο οποίος κάνει χρήση της τυχαιότητας. Πολλές ντετερμινιστικές εκδοχές αυτού του αλγορίθμου (π.χ. που διαλέγουμε πάντα το πρώτο στοιχείο ως άξονα) χρειάζονται Θ(n²) χρόνο για να ταξινομήσουν n αριθμούς για μία κατηγορία καλά διατυπωμένων εισόδων (π.χ. τους ήδη ταξινομημένους πίνακες). Ωστόσο, εάν ο αλγόριθμος επιλέγει τον άξονα ομοιόμορφα στην τύχη (από τα υπολειπόμενα στοιχεία), τότε με μεγάλη πιθανότητα τελειώνει σε O(n log n) χρόνο ανεξάρτητα από τα χαρακτηριστικά της εισόδου.

Στην υπολογιστική γεωμετρία, μια κλασσική τεχνική για την κατασκευή μιας γεωμετρικής δομής όπως το κυρτό περίβλημα ή η τριγωνοποίηση Delaunay είναι πρώτα να πάρουμε μία τυχαία μετάθεση των σημείων εισόδου και στη συνέχεια να τα εισάγουμε στην υπάρχουσα δομή το ένα μετά το άλλο. Η τυχαιότητα της σειράς που τα εισάγουμε διασφαλίζει ότι ο αναμενόμενος συνολικός αριθμός αλλαγών στη δομή είναι μικρός και έτσι ο αναμενόμενος χρόνος εκτέλεσης του αλγορίθμου είναι μικρός. Αυτή η τεχνική είναι γνωστή ως τυχαιοποιημένη σταδιακή κατασκευή.^[19]

Είσοδος: Ένας γράφος G(V, E).

Έξοδος: Μία τομή που χωρίζει τις κορυφές στα σύνολα L και R, και έχει τον ελάχιστο αριθμό ακμών μεταξύ των L και R.

Η συστολή δύο κορυφών u και v σε έναν (πολυ-)γράφο δίνει μία νέα κορυφή u' με ακμές που είναι η ένωση των ακμών που προσπίπτουν είτε στον u είτε στον v, εξαιρουμένων των ακμών μεταξύ των u και v. Το Σχήμα 1 δίνει ένα παράδειγμα συστολής των Α και Β. Μετά τη συστολή, ο γράφος που προκύπτει μπορεί να έχει παράλληλες ακμές, αλλά δεν περιέχει βρόχους.

Ο απλός αλγόριθμος του Karger^[20]:

begin 
   i := 1 
   repeat 
      repeat 
         Διαλέγουμε μία τυχαία ακμή (u,v) ∈ E στον G
         Διαγράφουμε τις κορυφές u και v
         Προσθέτουμε τη συστολή τους u΄
      until να μείνουν ακριβώς δύο κουρφές
      Λαμβάνουμε την αντίστοιχη τομή Cᵢ
      i := i + 1
   until i = m 
   Τυπώνουμε την ελάχιστη τομή από τις C₁, C₂, ..., Cₘ.
end

Ο αλγόριθμος επαναλαμβάνει τον εσωτερικό βρόχο ${\displaystyle m}$ φορές, που βρίσκει μία τομή ${\displaystyle C_{i}}$. Ο χρόνος εκτέλεσης του εσωτερικού βρόχου είναι ${\displaystyle O(n)}$, όπου n το πλήθος των κορυφών του γράφου. Μετά από m εκτελέσεις του εξωτερικού βρόχου, κρατάμε την ελάχιστη τομή μεταξύ όλων των αποτελεσμάτων. Το Σχήμα 2 δίνει ένα παράδειγμα μιας εκτέλεσης του αλγορίθμου, στο τέλος της οποίας λαμβάνουμε μια τομή ή μεγέθους 3.

Η πιθανότητα να πετύχει ο αλγόριθμος είναι 1 μείον την πιθανότητα να αποτύχουν όλες οι προσπάθειες. Επειδή κάθε επανάληψη είναι ανεξάρτητη, η πιθανότητα να αποτύχουν όλες οι προσπάθειες είναι$${\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}$$Από το Λήμμα 1, η πιθανότητα να έχουμε C_i = C είναι η πιθανότητα να μην επιλέξαμε καμία ακμή του C κατά την επανάληψη i . Θεωρήστε τον εσωτερικό βρόχο και έστω G_j ο γράφος μετά από j συστολές ακμών για j ∈ {0, 1, …, n − 3} . Τότε ο G_j έχει n − j κορυφές. Χρησιμοποιούμε τον κανόνα της αλυσίδας για την κατά συνθήκη πιθανότητα. Η πιθανότητα η ακμή που επιλέχθηκε στην επανάληψη j να μην είναι στο C, δεδομένου ότι δεν έχουμε επιλέξει καμία ακμή του C προηγουμένως, είναι ${\displaystyle 1-{\tfrac {k}{|E(G_{j})|}}}$ . Παρατηρήστε ότι ο G_j εξακολουθεί να έχει ελάχιστη τομή μεγέθους k, επομένως από το Λήμμα 2, εξακολουθεί να έχει τουλάχιστον ${\displaystyle {\tfrac {(n-j)k}{2}}}$ ακμές.

Επομένως, ${\displaystyle 1-{\tfrac {k}{|E(G_{j})|}}\geq 1-{\tfrac {2}{n-j}}={\tfrac {n-j-2}{n-j}}}$ .

Συνεπώς, χρησιμοποιώντας τον κανόνα της αλυσίδας, η πιθανότητα να βρεθεί η ελάχιστη τομή C είναι$${\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}$$Μετά την απλοποίηση λαμβάνουμε ότι ${\displaystyle \Pr[C_{i}=C]\geq {\tfrac {2}{n(n-1)}}}$ . Έτσι η πιθανότητα να πετύχει ο αλγόριθμος είναι τουλάχιστον ${\displaystyle 1-\left(1-{\tfrac {2}{n(n-1)}}\right)^{m}}$ . Θέτοντας ${\displaystyle m={\tfrac {n(n-1)}{2}}\ln n}$, η πιθανότητα είναι τουλάχιστον ${\displaystyle 1-{\tfrac {1}{n}}}$ . Καταλήγουμε ότι ο αλγόριθμος βρίσκει την ελάχιστη τομή με πιθανότητα τουλάχιστον ${\displaystyle 1-{\tfrac {1}{n}}}$, σε χρόνο ${\displaystyle O(mn)=O(n^{3}\log n)}$ .

Η τυχαιότητα μπορεί να θεωρηθεί ως ένας πόρος, όπως είναι ο χώρος και ο χρόνος. Η αποτυχαιοποίηση είναι η διαδικασία αφαίρεσης της τυχαιότητας (ή χρήσης όσο το δυνατόν λιγότερης από αυτήν) από έναν πιθανοτικό αλγόριθμο. Δεν είναι προς το παρόν γνωστό εάν όλοι οι αλγόριθμοι μπορούν να αποτυχαιοποιηθούν χωρίς να αυξηθεί σημαντικά ο χρόνος εκτέλεσης τους. Για παράδειγμα, στην θεωρία πολυπλοκότητας, είναι άγνωστο εάν P = BPP, δηλαδή, δεν γνωρίζουμε εάν μπορούμε να πάρουμε έναν αυθαίρετο τυχαιοποιημένο αλγόριθμο που εκτελείται σε πολυωνυμικό χρόνο με μικρή πιθανότητα σφάλματος και να τον αποτυχαιοποιήσουμε ώστε να εκτελείται σε πολυωνυμικό χρόνο χωρίς τη χρήση τυχαιότητας.

Υπάρχουν κάποιες γενικές μέθοδοι που μπορούν να χρησιμοποιηθούν για την αποτυχαιοποίηση συγκεκριμένων τυχαιοποιημένων αλγορίθμων:

• η μέθοδος της κατά συνθήκη πιθανότητας και η γενίκευσή της, με τους απαισιόδοξους εκτιμητές
• η θεωρία ασυμφωνίας (η οποία χρησιμοποιείται κυρίως για την αποτυχαιοποίηση γεωμετρικών αλγορίθμων)
• η εκμετάλλευση περιορισμένης ανεξαρτησίας μεταξύ των τυχαίων μεταβλητών που χρησιμοποιούνται από τον αλγόριθμο, όπως η ανεξαρτησία ανά δύο που χρησιμοποιείται στον καθολικό κατακερματισμό
• η χρήση γράφων επεκτατών για την ενίσχυση μιας μικρής ποσότητας αρχικής τυχαιότητας (αυτή η τελευταία προσέγγιση αναφέρεται επίσης ως δημιουργία ψευδοτυχαίων bits από μια τυχαία πηγή και οδηγεί στο σχετικό θέμα της ψευδοτυχαιότητας)
• αλλαγή του τυχαιοποιημένου αλγόριθμου για χρήση μιας συνάρτησης κατακερματισμού ως πηγή τυχαιότητας για τις εργασίες του αλγορίθμου και, στη συνέχεια, αποτυχαιοποίηση του αλγορίθμου με ωμή βία όλων των πιθανών παραμέτρων (seeds) της συνάρτησης κατακερματισμού. Αυτή η τεχνική χρησιμοποιείται συνήθως για την εξαντλητική αναζήτηση ενός δειγματοληπτικού χώρου και κάνει τον αλγόριθμο ντετερμινιστικό (π.χ. πιθανοτικοί αλγόριθμοι γράφων)

Για τις μηχανές Turing, είναι ανοιχτό πρόβλημα εάν η δυνατότητα να κάνουμε τυχαίες επιλογές επιτρέπει την επίλυση ορισμένων προβλημάτων σε πολυωνυμικό χρόνο που δεν μπορούν να λυθούν σε πολυωνυμικό χρόνο χωρίς αυτήν τη δυνατότητα. Το πρόβλημα συνοψίζεται στο αν P = BPP. Ωστόσο, σε άλλα πλαίσια, υπάρχουν συγκεκριμένα παραδείγματα προβλημάτων όπου η τυχαιοποίηση προσφέρει αυστηρά καλύτερα αποτελέσματα.

• Με βάση το αρχικό παράδειγμα: δοσμένης μιας εκθετικά μεγάλης συμβολοσειράς 2^k χαρακτήρων, όπου οι μισοί χαρακτήρες είναι a και οι άλλοι μισοί είναι b, μια μηχανή τυχαίας πρόσβασης χρειάζεται 2^k−1 προσβάσεις στον πίνακα στη χειρότερη περίπτωση για να βρει την θέση ενός a. Εάν επιπλέον έχει τη δυνατότητα να κάνει τυχαίες επιλογές, τότε μπορεί να λύσει αυτό το πρόβλημα σε έναν αναμενόμενο πολυωνυμικό αριθμό προσβάσεων.
• Στην πολυπλοκότητα της επικοινωνίας, η ισότητα δύο συμβολοσειρών μπορεί να επαληθευτεί σε κάποια αξιοπιστία χρησιμοποιώντας ${\displaystyle \log n}$ bits επικοινωνίας με ένα πρωτόκολλο που κάνει χρήση τυχαιότητας. Από την άλλη οποιοδήποτε ντετερμινιστικό πρωτόκολλο απαιτεί ${\displaystyle \Theta (n)}$ bits αν υπάρχει ένας δυνατός αντίπαλος.^[21]
• Ο όγκος ενός κυρτού σώματος μπορεί να εκτιμηθεί με έναν τυχαιοποιημένο αλγόριθμο με αυθαίρετη ακρίβεια σε πολυωνυμικό χρόνο.^[22] Οι Bárány και Füredi έδειξαν ότι κανένας ντετερμινιστικός αλγόριθμος δεν μπορεί να κάνει το ίδιο. ^[23] Αυτό ισχύει άνευ όρων, δηλαδή χωρίς να βασιζόμαστε σε οποιεσδήποτε θεωρητικές υποθέσεις πολυπλοκότητας, υποθέτοντας ότι το κυρτό σώμα μπορεί να διερευνηθεί μόνο ως μαύρο κουτί.
• Στην θεωρία πολυπλοκότητας, η κλάση IP αποτελείται από όλες τις γλώσσες που μπορούν να γίνουν αποδεκτές (με μεγάλη πιθανότητα) από μια αλληλεπίδραση πολυωνυμικού μήκους μεταξύ ενός πανίσχυρου αποδείκτη και ενός επαληθευτή που εφαρμόζει έναν αλγόριθμο BPP. Ισχύει ότι IP = PSPACE.^[24] Ωστόσο, εάν απαιτείται ο επαληθευτής να είναι ντετερμινιστικός, τότε ισχύει ότι IP = NP .
• Σε ένα δίκτυο χημικών αντιδράσεων (ένα πεπερασμένο σύνολο αντιδράσεων όπως A+B → 2C + D που λειτουργούν σε έναν πεπερασμένο αριθμό μορίων), η ικανότητα να φθάσουμε ποτέ σε μια κατάσταση από μια αρχική κατάσταση είναι αποφασίσιμη, ενώ προσεγγίζεται ακόμη και η πιθανότητα. Η επίτευξη μιας δεδομένης κατάστασης στόχου (χρησιμοποιώντας την τυπική πιθανότητα που βασίζεται στη συγκέντρωση για την οποία θα συμβεί η επόμενη αντίδραση) δεν μπορεί να αποφασιστεί. Πιο συγκεκριμένα, μια περιορισμένη μηχανή Turing μπορεί να προσομοιωθεί ώστε με μεγάλη πιθανότητα να λειτουργεί σωστά πάντοτε, μόνο εάν χρησιμοποιηθεί ένα τυχαίο δίκτυο χημικής αντίδρασης. Με ένα απλό μη ντετερμινιστικό δίκτυο χημικών αντιδράσεων (οποιαδήποτε πιθανή αντίδραση μπορεί να συμβεί στη συνέχεια), η υπολογιστική ισχύς περιορίζεται σε πρωταρχικές αναδρομικές συναρτήσεις . ^[25]

• Σωτήρης Ε. Νικολετσέας· Παύλο Γ. Σπυράκης (2003). Στοιχεία της πιθανοτικής μεθόδου: Μαθηματικές θεμελειώσεις της επιστήμης των υπολογιστών (PDF). Αθήνα: Gutenberg. 
• Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης (2015). «Κεφάλαιο 13: Τυχαίοι Αλγόριθμοι». Σχεδίαση και ανάλυση αλγορίθμων. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. 
• Παγουρτζής, Αριστείδης· Ζάχος, Ευστάθιος (2015). «Κεφάλαιο 4: Αλγόριθμοι στην Κρυπτογραφία». Υπολογιστική κρυπτογραφία. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-960-603-276-9. 
• Δραζιώτης, Κ. (2022). «Κεφάλαιο 9: Τεστ Πιστοποίησης πρώτων αριθμών». Εισαγωγή στην Κρυπτογραφία. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-618-85820-5-7. 

• Mitzenmacher, Michael· Upfal, Eli (2017). Probability and computing: randomization and probabilistic techniques in algorithms and data analysis (2nd έκδοση). Cambridge: Cambridge university press. ISBN 978-1107154889. 
• Motwani, Rajeev· Raghavan, Prabhakar. Randomized algorithms (9th printing έκδοση). Cambridge New York Melbourne: Cambridge University Press. ISBN 978-0521474658. 
• Alon, Noga· Spencer, Joel H. (2015). The probabilistic method (4η έκδοση). Hoboken, New Jersey: Wiley. ISBN 978-1-119-06195-3. 
• Dubhashi, Devdatt· Panconesi, Alessandro (2012). Concentration of measure for the analysis of randomized algorithms. Cambridge New York Melbourne: Cambridge University Press. ISBN 978-1107606609. 
• Mulmuley, Ketan (1993). Computational geometry: an introduction through randomized algorithms (Transferred to digital print on demand έκδοση). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0133363630. 
• Cormen, Thomas H.· =Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. «Probabilistic analysis and randomized algorithms». Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 978-0262033848. 
• Kleinberg, Jon· Tardos, Éva (2014). «Chapter 12: Randomized algorithms». Algorithm design (1η έκδοση). Harlow: Pearson. ISBN 978-1-292-02394-6. 

• Karger, David R. (1994). Random sampling in cut, flow, and network design problems, σελ. 648–657. doi:10.1145/195058.195422. 
• Kannan, Ravindran; Vempala, Santosh (1 Μαΐου 2017). «Randomized algorithms in numerical linear algebra». Acta Numerica 26: 95–135. doi:10.1017/S0962492917000058. 
• Bentley, Jon Louis; Lueker, George S. (1982). «Probabilistic Analysis of Algorithms». Applied Probability-Computer Science: The Interface Volume 1: 137–162. doi:10.1007/978-1-4612-5791-2_5. 

• Πιθανοτική ανάλυση αλγορίθμων
• Αλγόριθμος Atlantic City
• Αλγόριθμος Μόντε Κάρλο
• Αλγόριθμος Λας Βέγκας
• Bogosort
• Αρχή της αναβαλλόμενης απόφασης
• HyperLogLog
• Count-min sketch
• Αλγόριθμος του Karger