Ας πάρουμε μια τυχαία ανάθεση λογικών τιμών στις μεταβλητές μας. Η πιθανότητα ότι μια από τις παρενθέσεις μας ικανοποιείται εύκολα βλέπουμε ότι είναι 7/8. Αν γράψουμε λοιπόν $X$ για το πλήθος των παρενθέσεων που ικανοποιούνται με μια τυχαία ανάθεση τότε προκύπτει από τη γραμμικότητα της μέσης τιμής ότι $\Mean{X} = \frac78 N$, όπου $N$ το πλήθος των παρενθέσεων. Άρα υπάρχει λογική ανάθεση τ.ώ. το πλήθος των αληθών παρενθέσεων να είναι $\ge \frac78 N$. (Επίσης υπάρχει και ανάθεση όπου το πλήθος των αληθών παρενθέσεων να είναι $\le \frac78 N$.)

Έτσι, ο αλγόριθμός μας για τον έλεγχο της ταυτότητας των δύο συμβολοσειρών είναι ο εξής. Για έναν μεγάλο αριθμό $k$, αφήνουμε τον απομακρυσμένο υπολογιστή να υπολογίσει τους αριθμούς $b(X_1), b(X_2), \ldots, b(X_k)$, όπου τα $X_j$ παράγονται από εμάς (τοπικά) επιλεγμένα ανεξάρτητα και ομοιόμορφα από το $S$. Στη συνέχεια, ο απομακρυσμένος υπολογιστής μας στέλνει αυτές τις τιμές και ελέγχουμε αν $a(X_j) = b(X_j)$, για $j=1, \ldots, k$. Εάν οι δύο συμβολοσειρές είναι διαφορετικές, το πολυώνυμο $P(x)$ δεν είναι ταυτοτικά μηδέν, επομένως η πιθανότητα να συμβεί αυτό είναι το πολύ $1/2^k$. Επιλέγουμε τον αριθμό $k$ αρκετά μεγάλο ώστε να μπορούμε να ανεχτούμε την πιθανότητα αποτυχίας $1/2^k$ (για παράδειγμα, επιλέγοντας το $k$ περίπου 300 εγγυόμαστε πιθανότητα αποτυχίας $10^{-100}$). Ας επισημάνουμε ότι οι δύο πλευρές μπορεί να χρειαστεί ακόμα να εκτελέσουν εργασία $O(N)$ για να αξιολογήσουν τα δύο πολυώνυμα, αλλά το αργό μέρος, η επικοινωνία, είναι μόνο $O(k)$.

Ως επίδειξη της αρχής του ελέγχου ταυτοτήτων με πιθανότητα σφάλματος, εξοικονομώντας έτσι επικοινωνία, αναφέραμε το καθιερωμένο πρόγραμμα rsync. Διαβάστε σχετικά με αυτό εδώ.

Ένας νεαρός άνδρας μένει στο Μανχάταν κοντά σε έναν σταθμό του μετρό. Έχει δύο κοπέλες, μία στο Μπρούκλιν και μία στο Μπρονξ. Για να επισκεφθεί την κοπέλα στο Μπρούκλιν, παίρνει το τρένο από την πλευρά της αποβάθρας που πηγαίνει προς το κέντρο (downtown). Για να επισκεφθεί την κοπέλα στο Μπρονξ, παίρνει το τρένο από την πλευρά της ίδιας αποβάθρας που πηγαίνει προς τα προάστια (uptown). Επειδή του αρέσουν και οι δύο κοπέλες εξίσου, παίρνει απλώς το πρώτο τρένο που θα έρθει. Με αυτόν τον τρόπο, αφήνει την τύχη να καθορίσει αν θα πάει στο Μπρονξ ή στο Μπρούκλιν. Ο νεαρός άνδρας φτάνει στην αποβάθρα του μετρό σε μια τυχαία στιγμή κάθε Σάββατο απόγευμα. Τα τρένα για το Μπρούκλιν και το Μπρονξ φτάνουν στον σταθμό με την ίδια συχνότητα — κάθε 10 λεπτά. Κι όμως, για κάποιον αδιόρατο λόγο, καταλήγει να περνά τον περισσότερο χρόνο του με την κοπέλα στο Μπρούκλιν: στην πραγματικότητα, κατά μέσο όρο πηγαίνει εκεί 9 στις 10 φορές. Μπορείτε να σκεφτείτε έναν βάσιμο λόγο για τον οποίο οι πιθανότητες ευνοούν τόσο πολύ το Μπρούκλιν;

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

Υπάρχει ένας εύκολος τρόπος να κερδίσουμε την καραμέλα με πιθανότητα $1/2$. Απλώς λέμε πάντα "μεγαλύτερος". Ή λέμε πάντα "μικρότερος". Ή ρίχνουμε ένα δίκαιο νόμισμα και λέμε "μεγαλύτερος" ή "μικρότερος" ανάλογα με το αποτέλεσμα, κορώνα ή γράμματα. (Με αυτόν τον τρόπο δεν λαμβάνουμε καν υπόψη τον αριθμό που είδαμε γραμμένο κάτω από το κομμάτι χαρτί που επιλέξαμε.)

Υπάρχει τρόπος να παίξουμε αυτό το παιχνίδι έτσι ώστε η πιθανότητα να πάρουμε την καραμέλα να είναι μεγαλύτερη από $1/2$;

Η αναπάντεχη απάντηση είναι ναι (αλλά δεν μπορούμε να εγγυηθούμε πόσο μεγαλύτερη από 1/2 είναι αυτή η πιθανότητα νίκης).

Μπορούμε να το κάνουμε ως εξής: Έστω $X$ ο αριθμός που είδαμε αφού επιλέξαμε ένα κομμάτι χαρτί (άρα το $X$ είναι μια τυχαία μεταβλητή που παίρνει τις δύο τιμές $a$ και $b$ με ίση πιθανότητα). Έστω επίσης $Y$ μια τυχαία μεταβλητή της οποίας η πυκνότητα στον πραγματικό άξονα είναι παντού αυστηρά θετική. Για παράδειγμα, μπορούμε να θεωρήσουμε ότι το $Y$ ακολουθεί την τυπική κανονική κατανομή $\mathcal{N}(0, 1)$. Εκτελούμε το πείραμα που παράγει το $Y$ και στη συνέχεια λέμε "μεγαλύτερος" αν $X \ge Y$ ή "μικρότερος" αν $X \lt Y$. Μπορεί κανείς εύκολα να ελέγξει ότι η πιθανότητα επιτυχίας είναι αυστηρά μεγαλύτερη από 1/2.

1. Επιλέξτε ένα κουτί τυχαία και παραμείνετε σε αυτό.
2. Επιλέξτε ένα κουτί τυχαία και στη συνέχεια, αφού ένα άδειο κουτί βγει από τη μέση, επιλέξτε ξανά τυχαία ανάμεσα στα δύο εναπομείναντα.
3. Επιλέξτε ένα κουτί τυχαία και στη συνέχεια αλλάζετε πάντα στο άλλο κλειστό κουτί.

Ο λάθος τρόπος σκέψης για αυτό το ζήτημα είναι ο εξής: εφόσον βλέπουμε 1 ευρώ στο ανοιχτό χέρι, τότε τα περιεχόμενα του άλλου χεριού είναι είτε 1/2 ευρώ είτε 2 ευρώ, με κάθε περίπτωση να έχει πιθανότητα 1/2. Επομένως, αν αλλάξουμε στο άλλο χέρι, το αναμενόμενο κέρδος θα είναι $\frac12 \cdot \frac12 + \frac12\cdot 2 = \frac54$ το οποίο είναι $\gt 1$, συνεπώς θα έπρεπε να αλλάξουμε.

Στην πραγματικότητα δεν έχει καμία διαφορά αν αλλάξουμε ή όχι (στατιστικά -- φυσικά μπορεί να έχει σημασία σε μια συγκεκριμένη περίπτωση του παιχνιδιού). Πού βρίσκεται, λοιπόν, το σφάλμα στον παραπάνω υπολογισμό;

Διαβάστε σχετικά εδώ.