1. Μπορούμε να χρωματίσουμε τις ακμές του πλήρους γραφήματος $K_N$ με δύο χρώματα έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που προκύπτει να είναι $\le \frac14 {N \choose 3}$ (δηλ. το πολύ το ένα τέταρτο όλων των τριγώνων). Σχετικά εδώ.
2. Για κάθε $N$ μοναδιαία διανύσματα $v_1, v_2, \ldots, v_N \in \RR^d$ (στην Ευκλείδια νόρμα) μπορούμε να επιλέξουμε πρόσημα $\epsilon_j = \pm1$ τέτοια ώστε να ισχύει $$ \Abs{\epsilon_1 v_1 + \cdots + \epsilon_N v_N} \le \sqrt{N}. $$ Δείτε [AS, §2.4, Balancing Vectors].
3. Για κάθε 3CNF, δηλ. για κάθε λογικό τύπο που είναι μια σύζευξη (ΚΑΙ) από διαζεύξεις (Ή) τριών μεταβλητών ή αρνήσεών τους, π.χ., κάτι της μορφής $$ (x_1 \lor x_2 \lor \overline{x_4}) \land (\overline{x_1} \lor x_5 \lor \overline{x_{10}}) \land \cdots \land (x_2 \lor x_3 \lor x_7), $$ μπορούμε να βρούμε μια ανάθεση τιμών Αληθής ή Ψευδής για τις λογικές μεταβλητές $x_j$ που καθιστά τουλάχιστον τα 7/8 από τα clauses (οι παρενθέσεις παραπάνω) αληθή.

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

4. Πώς μπορούμε γρήγορα να ελέγξουμε αν δύο πολυώνυμα $p(x)$ και $q(x)$ βαθμού $\le d$ είναι ίσα ή όχι; Τα πολυώνυμα αυτά μπορεί να μας δίνονται με πεπλεγμένο τρόπο, όχι δηλ. απαραίτητα στη συνηθισμένη μορφή $$ p(x) = p_d x^d + p_{d-1}x^{d-1}+\cdots+p_1 x + p_0 $$ έτσι ώστε πρακτικά το μόνο που μπορούμε να κάνουμε για καθένα από αυτά είναι να τα υπολογίζουμε σε κάποια σημεία και να ελέγχουμε αν βγάζουν το ίδιο αποτέλεσμα. Πόσοι έλεγχοι χρειάζονται να γίνουν; Διαβάστε από [MU, §1.1, Application: Verifying Polynomial Identities].
5. Υποθέστε ότι έχουμε δύο μεγάλες συμβολοσειρές αριθμών $a = a_0 a_1 a_2 \ldots, a_N$ και $b = b_0 b_1 b_2 \ldots b_N$ (φανταστείτε έναν μεγάλο αριθμό $N$) και θέλουμε να αποφασίσουμε αν οι δύο συμβολοσειρές είναι ίδιες. Η συμβολοσειρά $a$ βρίσκεται στον τοπικό μας υπολογιστή, αλλά η συμβολοσειρά $b$ σε έναν απομακρυσμένο υπολογιστή με αργή πρόσβαση. Θα μπορούσαμε να μεταφέρουμε το $b$ στον τοπικό μας υπολογιστή και να ελέγξουμε αν $a_n = b_j$ για $j=1, \ldots, N$, με κόστος $O(N)$ μονάδων επικοινωνίας (τις οποίες υποθέτουμε ότι είναι πολύ δαπανηρές και θα θέλαμε να ελαχιστοποιήσουμε). Αντί να μεταφέρουμε ολόκληρη τη συμβολοσειρά $b$, κάνουμε το εξής. Ορίζουμε τα δύο πολυώνυμα $a(x) = \sum_{j=0}^N a_j x^j$ και $b(x) = \sum_{j=0}^N b_j x^j$. Προφανώς, οι δύο συμβολοσειρές είναι πανομοιότυπες αν και μόνο αν τα δύο πολυώνυμα είναι πανομοιότυπα, ή αν το πολυώνυμο $P(x) = a(x)-b(x)$ βαθμού $\le N$ είναι ταυτοτικά 0. Έστω ο τυχαίος αριθμός $X$ ομοιόμορφα κατανεμημένος στο σύνολο $S = \Set{1, 2, \ldots, 2N}$. Εφόσον το $P$ έχει το πολύ $N$ ρίζες στο $S$, προκύπτει ότι $\Prob{P(X) = 0} \le \frac12$.

   Έτσι, ο αλγόριθμός μας για τον έλεγχο της ταυτότητας των δύο συμβολοσειρών είναι ο εξής. Για έναν μεγάλο αριθμό $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. Διαβάστε σχετικά με αυτό εδώ.

6. Υποθέστε ότι κάποιος ισχυρίζεται ότι $A B = C$, για τρεις δοσμένους $N \times N$ πίνακες πραγματικών αριθμών. Θα θέλαμε να επαληθεύσουμε αυτόν τον ισχυρισμό, αλλά δεν έχουμε την πολυτέλεια να επανυπολογίσουμε το γινόμενο $A B$ από τους πίνακες $A, B$, διαδικασία που απαιτεί περίπου $N^3$ χρόνο. Ωστόσο, μπορούμε να το κάνουμε αυτό πολύ πιο γρήγορα, χρησιμοποιώντας μόνο μερικούς πολλαπλασιασμούς πίνακα-διανύσματος (χρόνου $O(N^2)$ ο καθένας) και με μια πολύ μικρή πιθανότητα αποτυχίας. Διαβάστε περισσότερα γι' αυτό εδώ. Ιδού ένα μικρό πρόγραμμα σε python που υλοποιεί αυτόν τον αλγόριθμο.
7. Ο νεαρός άνδρας με τις δύο φίλες. Δείτε το πρόβλημα όπως παρατίθεται εδώ:

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

   Διαβάστε τη λύση του γρίφου από το άρθρο της Wikipedia που συνδέεται από την ίδια σελίδα.

1. Κάτω από δύο κομμάτια χαρτί είναι γραμμένοι δύο διαφορετικοί πραγματικοί αριθμοί $a$ και $b$, άγνωστοι σε εμάς.

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

   Υπάρχει ένας εύκολος τρόπος να κερδίσουμε την καραμέλα με πιθανότητα $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.

2. Συζητήσαμε το Πρόβλημα του Monty Hall, ένα κλασικό παράδειγμα. Διαβάστε σχετικά με αυτό εδώ αλλά μη διαβάσετε πάρα πολλά. Σκεφτείτε τις τρεις στρατηγικές για τις οποίες μιλήσαμε:
   1. Επιλέξτε ένα κουτί τυχαία και παραμείνετε σε αυτό.
   2. Επιλέξτε ένα κουτί τυχαία και στη συνέχεια, αφού ένα άδειο κουτί βγει από τη μέση, επιλέξτε ξανά τυχαία ανάμεσα στα δύο εναπομείναντα.
   3. Επιλέξτε ένα κουτί τυχαία και στη συνέχεια αλλάζετε πάντα στο άλλο κλειστό κουτί.
   Πείστε τους εαυτούς σας ότι οι πιθανότητες νίκης με αυτές τις τρεις στρατηγικές είναι 1/3, 1/2 και 2/3 αντίστοιχα.
3. Ο παρουσιαστής αυτού του παιχνιδιού κρατάει (κρυμμένα) στα χέρια του δύο χρηματικά ποσά: ένα άγνωστο ποσό και το διπλάσιό του. Δεν γνωρίζουμε ποιο ποσό βρίσκεται σε ποιο χέρι. Αφού επιλέξουμε ένα χέρι τυχαία, ο παρουσιαστής ανοίγει το χέρι που επιλέξαμε και βλέπουμε 1 ευρώ. Στη συνέχεια μας δίνεται η επιλογή να αλλάξουμε την επιλογή μας πριν αποκαλυφθεί το περιεχόμενο του άλλου χεριού. Πρέπει να αλλάξουμε ή όχι;

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

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

4. Πώς να πείσετε τον φίλο σας που έχει αχρωματοψία ότι οι δύο, κατά τα άλλα πανομοιότυπες, μπάλες που κρατάτε στα χέρια σας είναι πράσινη και κόκκινη;

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

5. Ένα σύνολο $S$ σε μια προσθετική (αβελιανή) ομάδα λέγεται sum-free αν για κάθε $x, y, z \in S$ ισχύει $x+y \neq z$. Δείξαμε ένα θεώρημα του Erdős που λέει ότι σε κάθε πεπερασμένο σύνολο ακεραίων $A$ με $N$ στοιχεία μπορεί κανείς να βρει ένα υποσύνολό του, $B$, με $\ge N/3$ στοιχεία που να είναι sum-free. Μπορείτε να δείτε την απόδειξη του Erdős εδώ, ελαφρώς τροποποιημένη ώστε να μπορεί εύκολα να μετατραπεί σε γρήγορο αλγόριθμο. Η αρχική απόδειξη του Erdős υπάρχει στο [AS], παρ. 1.4.

Σήμερα ασχοληθήκαμε αρχικά με το λεγόμενο Erdős similarity problem (εικασία: αν $A \subseteq \RR$ άπειρο σύνολο τότε υπάρχει μετρήσιμο σύνολο $E \subseteq \RR$ με θετικό μέτρο τέτοιο ώστε για κάθε $x, t \in \RR$ το σύνολο $x+tA$ δεν περιέχεται στο $E$. Συγκεκριμένα αποδείξαμε μια ευκολότερη παραλλαγή αυτής της εικασίας: πάντα υπάρχει μετρήσιμο $E \subseteq [0, 1]$ με μέτρο όσο θέλουμε κοντά στο 1 που να μην περιέχει σχεδόν όλα τα "αντίγραφα" $x+tA$. Δηλ. το σύνολο $\Set{(x, t):\ x+tA \subseteq E}$ έχει διδιάστατο μέτρο Lebesgue ίσο με το 0. Το σύνολο $E$ το κατασκευάσαμε με πιθανοθεωρητικό τρόπο. Μπορείτε να διαβάσετε την απόδειξη εδώ.

Έπειτα αρχίσαμε να περιγράφουμε την απόδειξη του θεωρήματος προσέγγισης από πολυώνυμα του Weierstrass που οφείλεται στον Bernstein. Μπορείτε να δείτε την πλήρη απόδειξη εδώ, σελ. 18. Θα την τελειώσουμε την επόμενη φορά.

Αρχικά τελειώσαμε την απόδειξη του θεωρήματος προσέγγισης του Weierstrass που οφείλεται στον Bernstein (εδώ, σελ. 18). Έπειτα δείξαμε ένα βελτιωμένο άνω φράγμα για το πλήθος $k$ αριθμών από το $\Set{1, 2, \ldots, n}$ που μπορούμε να επιλέξουμε έτσι ώστε όλα τα αθροίσματα που μπορούμε να δημιουργήσουμε επιλέγοντας (μέχρι μια φορά) κάποιους από αυτούς να είναι διαφορετικά. Δείτε αυτό το φράγμα στο [AS], παρ. 4.6.

Έπειτα δείξαμε ότι αν το γράφημα $G$ έχει $n$ κορυφές και $nd/2$ ακμές, τότε περιέχει ένα ανεξάρτητο σύνολο μεγέθους $\ge n/(2d)$.

Απόδειξη: Θεωρήστε ένα τυχαίο υποσύνολο $S$ των κορυφών, κρατώντας κάθε κορυφή με πιθανότητα $p$. Έστω $X$ το μέγεθός του και $Y$ ο αριθμός των ακμών του $G$ που περιορίζονται στο $S$. Προκύπτει ότι $$ \Mean{Y} = \frac{nd}{2}p^2. $$ Εφόσον $\Mean{X} = pn$, έχουμε $\Mean{X-Y}=np-\frac{nd}{2}p^2$. Επιλέγοντας $p=1/d$ για να μεγιστοποιήσουμε αυτή την τιμή, παίρνουμε $\Mean{X-Y}=n/(2d)$. Διαγράφοντας μία κορυφή από κάθε ακμή, απομένει ένα ανεξάρτητο σύνολο μεγέθους $\ge n/(2d)$.

Αναφέραμε την ανισότητα Chernoff: αν $X_1, \ldots, X_n$ είναι ανεξάρτητες τυχαίες μεταβλητές που παίρνουν μόνο τις τιμές 0 ή 1 και $X = X_1+\cdots+X_n$ έχει μέση τιμή $\mu = \Mean{X}$ τότε για κάθε $\epsilon \gt 0$ έχουμε την ανισότητα απόκλισης $$ \Prob{\Abs{X-\mu} \le \epsilon\mu} \le 2 e^{-c_\epsilon \mu}, $$ όπου $c_\epsilon = \min\Set{\epsilon^2/2, -\log(e^\epsilon(1+\epsilon)^{-(1+\epsilon)}}$.

Χρησιμοποιήσαμε έπειτα την ανισότητα αυτή για να δείξουμε ότι ένα τυχαίο σύνολο φυσικών αριθμών $E$ το οποίο δημιουργούμε κρατώντας κάθε αριθμό $n \in \NN$ μέσα στο σύνολο $E$ με πιθανότητα $p$, ανεξάρτητα για όλα τα $n\in\NN$, έχει σχεδόν σίγουρα πυκνότητα $$ \lim_{n\to\infty} \frac1n \Abs{E\cap\Set{1, 2, \ldots, n}} = p. $$

Σήμερα είδαμε μερικά άρθρα από αυτό το άρθρο. Συγκεκριμένα είδαμε την απόδειξη ενός θεωρήματος του Uchiyama για τριγωνομετρικά πολυώνυμα (παρ. 2.3) και την απόδειξη ενός θεωρήματος του Erdős για ασυμπτωτικές προσθετικές βάσεις τάξης 2 με μικρή συνάρτηση αναπαράστασης (παρ. 3.2). Βασιστήκαμε στο θεώρημα του Chernoff (Θεώρημα 3.1) ενώ αναφέραμε επίσης και το σχετικό Θεώρημα 3.2, το οποίο θα χρησιμοποιήσουμε την επόμενη φορά στην απόδειξη του θεωρήματος Salem-Zygmund για τριγωνομετρικά πολυώνυμα (παρ. 3.4).