12.2 Μέση τιμή μιας ΤΜ

Ορισμός 12.6   (Μέση τιμή μιας τυχαίας μεταβλητής) Αν $X$ είναι μια ΤΜ με ακέραιες τιμές τότε ορίζουμε τη μέση τιμή της $X$ μέσω του τύπου

$${\bf E}{X} = \sum_{n=-\infty}^\infty n f_X(n),$$ (12.5)

αν η σειρά συγκλίνει απόλυτα, αν έχουμε δηλαδή

$$\sum_{n=-\infty}^\infty {\left\vert{n}\right\vert} f_X(n) < \infty.$$ (12.6)

Γενικότερα, αν $X:\Omega\to T \subseteq {\mathbb{R}}$ είναι οποιαδήποτε διακριτή ΤΜ, με $T$ αριθμήσιμο, τότε η μέση τιμής της ορίζεται από τον τύπο

$${\bf E}{X} = \sum_{t \in T} t\cdot {{\bf {Pr}}\left[{X = t}\right]},$$ (12.7)

και πάλι μόνο όταν

$$\sum_{t \in T} {\left\vert{t}\right\vert}\cdot {{\bf {Pr}}\left[{X = t}\right]}<\infty,$$ (12.8)

Παρατήρηση 12.8   Είναι προφανές ότι ο γενικότερος ορισμός (12.7) συμπίπτει με τον ειδικότερο, για την περίπτωση ακέραιας ΤΜ, ορισμό (12.5).

Είναι επίσης φανερό ότι αν τα ενδεχόμενα $A_s$.$s \in S$, με αριθμήσιμο σύνολο δεικτών $S$, αποτελούν διαμέριση του δειγματικού χώρου $\Omega$ και έχουν την ιδιότητα ότι η ΤΜ $X$ είναι σταθερή σε κάθε $A_s$ με τιμή $c_s$ τότε

$${\bf E}{X} = \sum_{s \in S} c_s {{\bf {Pr}}\left[{A_s}\right]}.$$

Παρατήρηση 12.9   Αν η ΤΜ $X$ παίρνει πεπερασμένες μόνο τιμές τότε η μέση τιμή της υπάρχει αφού η σειρά (12.5) δεν είναι παρά ένα πεπερασμένο άθροισμα. Για παράδειγμα, αν $X$ είναι το αποτέλεσμα ενός συνηθισμένου ζαριού, τότε $f_X(n) = \frac{1}{6}{\bf 1}\left(1\le n \le 6\right)$ και

$${\bf E}{X} = \frac{1}{6} 1 + \frac{1}{6} 2 + \cdots + \frac{1}{6} 6 = 3.5.$$

Γενικότερα, αν η ΤΜ $X$ είναι ομοιόμορφα κατανεμημένη στο ${\left\{{0,\ldots,m}\right\}}$ τότε ${\bf E}{X} = m/2$.

Παρατήρηση: Η μέση τιμή μιας ΤΜ $X$, αν υπάρχει, είναι ένας κυρτός συνδυασμός των τιμών της $X$. Κυρτός συνδυασμός κάποιων αριθμών (ή διανυσμάτων) $a_1, a_2, \ldots$ είναι μια ποσότητα της μορφής

$$\lambda_1 a_1 + \lambda_2 a_2 + \cdots,$$

όπου $\lambda_j \in [0,1]$ για κάθε $j$ και

$$\sum_{j=1}^\infty \lambda_j = 1.$$

Η διαφορά δηλ. από το συνηθισμένο γραμμικό συνδυασμό είναι ο περιορισμός στους συντελεστές ότι πρέπει να είναι μη αρνητικοί και το άθροισμά τους πρέπει να κάνει 1. Αφού λοιπόν ${\bf E}{X} = \sum_{j \in {\mathbb{Z}}} j {{\bf {Pr}}\left[{X=j}\right]}$ και οι συντελεστές μπροστά από τις δυνατές τιμες $j$ της ακέραιας ΤΜ $X$, δηλ. οι ποσότητες ${{\bf {Pr}}\left[{X=j}\right]}$, είναι μη αρνητικοί και έχουν άθροισμα 1, έπεται ότι όντως η μέση τιμή της $X$ είναι κυρτός συνδυασμός των δυνατών τιμών της $X$ (όλων των ακεραίων δηλ.).

Άσκηση 12.15   Αν $m \le a_j \le M$ για κάθε $j$ και $x=\sum_{j=1}^\infty \lambda_j a_j$ είναι ένας κυρτός συνδυασμός των $a_j$ (δηλ. $\forall j \lambda_j \in [0,1]$ και $\sum\lambda_j=1$) τότε δείξτε ότι

$$m \le x \le M.$$

Συμπεράνετε ότι αν μια ακέραια ΤΜ $X$ ικανοποιεί πάντα $m\le X \le M$ τότε ισχύει και

$$m \le {\bf E}{X} \le M.$$

Γιατί υπάρχει πάντα η μέση τιμή της $X$ υπό αυτές τις υποθέσεις;

Παρατήρηση 12.10   Ο λόγος που απαιτούμε να ισχύει η (12.6) ή (12.8) για να μιλήσουμε για τη σειρά (12.5) ή (12.7) είναι ότι αν δεν ισχύει η (12.6) ή (12.8) τότε το άθροισμα της σειράς (12.5) ή (12.7) εξαρτάται από την οριακή διαδικασία με την οποία το ορίζουμε, ή, με άλλα λόγια, από τη σειρά με την οποία αθροίζουμε τους όρους της (12.5) ή της (12.7).

Αν η ΤΜ $X$ είναι πάντα μη αρνητική και η σειρά (12.6) ή (12.8) αποκλίνουν (ισούνται με $+\infty$), τότε θα θεωρούμε ${\bf E}{X} = \infty$.

Άσκηση 12.16   Αν $A \subseteq \Omega$ είναι ένα ενδεχόμενο και $X(\omega) = {\bf 1}\left(\omega \in A\right)$ υπολογίστε τη ${\bf E}{X}$.

Άσκηση 12.17   Αν η $X$ ακολουθεί κατανομή Poisson (δείτε (12.4)) με παράμετρο $\lambda$ δείξτε ότι ${\bf E}{X} = \lambda$.

Άσκηση 12.18   Δείξτε ότι αν η σταθερά $C>0$ οριστεί κατάλληλα τότε η συνάρτηση $f(n) = \frac{C}{n^2} {\bf 1}\left(n \ge 1\right)$ είναι πυκνότητα πιθανότητας και ότι οποιαδήποτε ΤΜ με πυκνότητα $f_X \equiv f$ δεν έχει μέση τιμή ${\bf E}{X}$.

Άσκηση 12.19   Αν η πυκνότητα της $X$ είναι συμμετρική ως πρός το σημείο $x \in {\mathbb{R}}$, αν δηλ. ισχύει

$$f(n) = f(2x-n), \forall n \in {\mathbb{Z}},$$

τότε, αν υπάρχει η ${\bf E}{X}$ έχουμε ${\bf E}{X} = x$.

Παράδειγμα 12.15   Αν $T \in {\left\{{1,2,\ldots}\right\}}$ είναι ο χρόνος εμφάνισης της πρώτης κορώνας σε μια άπειρη ακολουθία ρίψεως ενός νομίσματος που έρχεται κορώνα με πιθανότητα $p$, η πυκνότητα της $T$ δίνεται από τον τύπο

$$f_T(n) = p(1-p)^{n-1} {\bf 1}\left(n \ge 1\right),$$

οπότε

$${\bf E}{T} = \sum_{n=1}^\infty p (1-p)^{n-1} n.$$

Πραγωγίζοντας τη σειρά $\sum_{n=0}^\infty x^n = (1-x)^{-1}$ κατά όρους παίρνουμε

$$\sum_{n=1}^\infty n x^{n-1} = \frac{1}{(1-x)^2}.$$

Εφαρμόζοντας αυτό τον τύπο για $x=1-p$ παίρνουμε

$${\bf E}{T} = p \frac{1}{p^2} = \frac{1}{p}.$$

Ο μέσος χρόνος εμφάνισης δηλ. της πρώτης κορώνας είναι αντιστρόφως ανάλογος της πιθανότητας εμφάνισης κορώνας σε μια ρίψη του νομίσματος.

Η πιο σημαντική ιδιότητα της μέσης τιμής είναι η γραμμικότητά της. Είναι σκόπιμο να τονιστεί εδώ πως, αντίθετα με το Θεώρημα 12.4 παρακάτω, το Θεώρημα 12.2 δεν απαιτεί ανεξαρτησία των ΤΜ. Εκεί έγκειται και η μεγάλη χρησιμότητά του.

Θεώρημα 12.2   Αν οι διακριτές ΤΜ $X$ και $Y$ έχουν μέση τιμή και $\lambda,\mu \in {\mathbb{R}}$ είναι σταθερές, τότε η ΤΜ $Z = \lambda X + \mu Y$ έχει μέση τιμή και ${\bf E}{Z} = \lambda {\bf E}{X} + \mu {\bf E}{Y}$.

Απόδειξη. Έστω $X:\Omega\to T_1$ και $Y:\Omega \to T_2$, όπου τα σύνολα $T_1, T_2$ είναι αριθμήσιμα. Ορίζουμε τα ενδεχόμενα

$$A_t = {\left\{{X = s}\right\}}, (s \in T_1),$$

$$B_t = {\left\{{Y=t}\right\}} (t \in T_2),$$

και

$$C_{s,t} = {\left\{{X=s, Y=t}\right\}}, (s \in T_1, t \in T_2).$$

Έχουμε

$${\bf E}{X} = \sum_{s \in T_1} s {{\bf {Pr}}\left[{A_s}\right]} = \sum_{s\in T_1} s \sum_{t \in T_2} {{\bf {Pr}}\left[{C_{s,t}}\right]},$$

και

$${\bf E}{Y} = \sum_{t \in T_2} s {{\bf {Pr}}\left[{B_t}\right]} = \sum_{t\in T_2} t \sum_{s \in T_1} {{\bf {Pr}}\left[{C_{s,t}}\right]},$$

οπότε

$$\lambda {\bf E}{X} + \mu {\bf E}{Y} = \sum_{s \in T_1, t \in T_2} {{\bf {Pr}}\left[{C_{s,t}}\right]} (\lambda s+ \mu t) = {\bf E}{Z},$$

αφού τα ενδεχόμενα $C_{s,t}$, $s \in T_1, t \in T_2$, αποτελούν διαμέριση του $\Omega$ στα οποία η ΤΜ $Z$ είναι σταθερή (δείτε Παρατήρηση 12.8). $\qedsymbol$

Παράδειγμα 12.16   Στο Παράδειγμα 12.14 μπορούμε να υπολογίσουμε τη ${\bf E}{X+Y}$ χωρίς να χρησιμοποιήσουμε καθόλου τη συνάρτηση πυκνότητας της $X+Y$ που υπολογίσαμε εκεί. Για την $X$ έχουμε από την Άσκηση 12.19 ότι ${\bf E}{X} = m/2$ αφού η ομοιόμορφη κατανομή στο ${\left\{{0,\ldots,m}\right\}}$ είναι συμμετρική γύρω από το σημείο $m/2$. Τέλος ${\bf E}{X+Y} = {\bf E}{X}+{\bf E}{Y}=2{\bf E}{X}=2\frac{m}{2}=m$.

Παράδειγμα 12.17   Έστω ότι η $X$ ακολουθεί τη διωνυμική κατανομή (δείτε Παράδειγμα 12.12) με παραμέτρους $p$ και $N$, ότι έχουμε δηλαδή

$$f_X(k) = {N \choose k} p^k (1-p){N-k} {\bf 1}\left(0 \le k \le N\right).$$

Η $X$ μπορεί να υλοποιηθεί ως το πλήθος των κορωνών σε $N$ ανεξάρτητες ρίψεις ενός νομίσματος που φέρενι κορώνα με πιθανότητα $p$. Άρα, αν συμβολίσουμε $X_j = {\bf 1}($ φέρνουμε κορώνα στη $j$ ρίψη) έχουμε

$$X = X_1 + \cdots + X_N,$$

Άρα ${\bf E}{X} = {\bf E}{X_1}+\cdots+{\bf E}{X_N} = N {\bf E}{X_1} = Np$.

Παράδειγμα 12.18   Σ' ένα δωμάτιο μπαίνουν $N$ άτομα και αφήνουν τα καπέλα τους στον προθάλαμο, όπου όμως παίζουν κάποια παιδιά και ανακατεύουν τα καπέλα. Φεύγοντας τα $N$ άτομα παίρνουν από ένα καπέλο στην τύχη. Ποιος είναι ο μέσος αριθμός των ατόμων που παίρνουν το δικό τους καπέλο;

Η ΤΜ που μας ενδιαφέρει είναι η $X$, ο αριθμός των ατόμων, που παίρνουν το δικό τους καπέλο. Ας είναι $X_j$, $j=1,\ldots,N$, οι ΤΜ $X_j = {\bf 1}($ το άτομο $j$ παίρνει το δικό του καπέλο). (Οι ΤΜ $X_j$ δεν είναι ανεξάρτητες. Γιατί;) Είναι φανερό ότι

$$X = X_1 + X_2 + \cdots + X_N.$$

Άρα, από το Θεώρημα 12.2 έχουμε ${\bf E}{X} = \sum_{j=1}^N {\bf E}{X_j}$. Επίσης, λόγω της συμμετρίας, έχουμε ότι οι $X_j$ είναι ισόνομες, άρα ${\bf E}{X} = N {\bf E}{X_1}$. Τέλος ${\bf E}{X_1} = {\bf Pr}[$ ο 1 παίρνει το καπέλο του $] = 1/n$, επίσης λόγω της συμμετρίας. Άρα ${\bf E}{X} = 1$. Είναι εντυπωσιακό ότι το ${\bf E}{X}$ δεν εξαρτάται από το $N$.

Το «σπάσιμο» της ΤΜ $X$ σαν άθροισμα άλλων απλουστέρων, και μάλιστα δεικτριών, ΤΜ είναι ένα πολύ χρήσιμο εργαλείο στη λύση προβλημάτων.

Το παρακάτω είναι εξαιρετικά χρήσιμο σε υπολογισμούς.

Θεώρημα 12.3   Αν $X$ είναι μια διακριτή ΤΜ (όχι αναγκαστικά αριθμητική) και $f$ μια αριθμητική συνάρτηση ορισμένη στο πεδίο τιμών $T$ της $X$ τότε η ΤΜ $f(X)$ έχει μέση τιμή αν

$$\sum_{t\in T} {\left\vert{f(t)}\right\vert} {{\bf {Pr}}\left[{X=t}\right]} < \infty,$$

και αυτή τότε ισούται με

$${\bf E}{f(X)} = \sum_{t\in T} f(t) {{\bf {Pr}}\left[{X=t}\right]}.$$

Απόδειξη. Η απόδειξη είναι άμεση αν εφαρμόσουμε την Παρατήρηση 12.8 στη διαμέριση $\Omega = \bigcup_{t \in T} {\left\{{X=t}\right\}}$. $\qedsymbol$

Παρατήρηση 12.11   Μετά το Θεώρημα 12.3 είναι φανερό πως η συνθήκες (12.6) και (12.8) δεν είναι τίποτε άλλο από τη συνθήκη ${\bf E}{{\left\vert{X}\right\vert}} < \infty$ (η μέση τιμή μιας μη αρνητικής ΤΜ υπάρχει πάντα και είναι πεπερασμένος αριθμός ή $+\infty$).

Άσκηση 12.20   Όταν αγοράζετε ένα συγκεκριμένο προϊόν υπάρχει πάντα μέσα στη συσκευασία ένα παιχνίδι-έκπληξη. Υπάρχουν $c$ διαφορετικά τέτοια παιχνίδια που μπορεί να βρείτε μέσα στη συσκευασία και όλα αυτά τα παιχνίδια είναι εξίσου πιθανό να εμφανιστούν. Αγοράζετε ένα τέτοιο προϊόν κάθε μέρα. Ποιος είναι ο μέσος αριθμός ημερών που περνάει από τότε που θα βρείτε το $j$-οστό νέο παιχνίδι μέχρι να βρείτε το $(j+1)$-οστό νέο παιχνίδι; Ποιος είναι ο μέσος αριθμός ημερών που περνάει έως ότου βρείτε και τα $c$ διαφορετικά παιχνίδια;

Θεώρημα 12.4   Αν οι ΤΜ $X$ και $Y$ είναι ανεξάρτητες και έχουν μέσες τιμές τότε και η $XY$ έχει μέση τιμή και ${\bf E}{XY} = {\bf E}{X} {\bf E}{Y}$.

Απόδειξη. Έστω $X:\Omega\to T_1$ και $Y:\Omega \to T_2$, όπου τα σύνολα $T_1, T_2$ είναι αριθμήσιμα. Όπως και στην απόδειξη του Θεωρήματος 12.2 ορίζουμε τα ενδεχόμενα

$$C_{s,t} = {\left\{{X=s, Y=t}\right\}}, (s \in T_1, t \in T_2).$$

Έχουμε

$${\bf E}{{\left\vert{XY}\right\vert}} = \sum_{s \in T_1, t \in T_2} {\left\vert{st}\right\vert} {{\bf {Pr}}\left[{C_{s,t}}\right]}$$

$$= \sum_{s \in T_1, t \in T_2} {\left\vert{st}\right\vert} {{\bf {Pr}}\left[{X=s}\right]} {{\bf {Pr}}\left[{Y=t}\right]} \dagger$$

$$= \sum_{s \in T_1} {\left\vert{s}\right\vert} {{\bf {Pr}}\left[{X=s... ...cdot \sum_{t \in T_2} {\left\vert{t}\right\vert} {{\bf {Pr}}\left[{Y=t}\right]}$$

$$= {\bf E}{{\left\vert{X}\right\vert}} {\bf E}{{\left\vert{Y}\right\vert}} < \infty$$

($\dagger$: από ανεξαρτησία των $X, Y$), οπότε έχουμε δείξει ότι η $XY$ έχει μέση τιμή. Ομοίως

$${\bf E}{XY} = \sum_{s \in T_1, t \in T_2} st {{\bf {Pr}}\left[{C_{s,t}}\right]}$$

$$= \sum_{s \in T_1, t \in T_2} st {{\bf {Pr}}\left[{X=s}\right]} {{\bf {Pr}}\left[{Y=t}\right]} \ddagger$$

$$= \sum_{s \in T_1} s {{\bf {Pr}}\left[{X=s}\right]} \cdot \sum_{t \in T_2} t {{\bf {Pr}}\left[{Y=t}\right]}$$

$$= {\bf E}{X} {\bf E}{Y}$$

($\ddagger$: από ανεξαρτησία των $X, Y$). $\qedsymbol$

Παρατήρηση 12.12   Ομοίως προκύπτει ότι αν οι $X_1, \ldots, X_N$ είναι ένα ανεξάρτητο σύνολο από ΤΜ τότε ${\bf E}{X_1\cdots X_N} = {\bf E}{X_1}\cdots{\bf E}{X_N}$.

Παρατήρηση 12.13   Η συνθήκη «$X, Y$ ανεξάρτητες» δε μπορεί να παραλειφθεί στο Θεώρημα 12.4. Ας είναι, για παράδειγμα, $A$ και $B$ δύο ξένα μεταξύ τους ενδεχόμενα με θετική πιθανότητα το καθένα, και $X={\bf 1}_A$, $Y={\bf 1}_B$ οι αντίστοιχες δείκτριες ΤΜ (δείτε το Παράδειγμα 12.8). Έχουμε τότε $XY={\bf 1}_{A\cap B}={\bf 1}_\emptyset$ άρα ${\bf E}{XY}=0$ ενώ ${\bf E}{X}={{\bf {Pr}}\left[{A}\right]}>0$ και ${\bf E}{Y}={{\bf {Pr}}\left[{B}\right]}>0$.

Παράδειγμα 12.19   Ένα σωμάτιο εκτελεί ένα «τυχαίο περίπατο» ως εξής: τη χρονική στιγμή 0 βρίσκεται στη θέση 0 του άξονα των ακεραίων αριθμών. Σε κάθε ακέραια χρονική στιγμή ρίχνει ένα τίμιο νόμισμα και αν έρθει κορώνα μετακινείται μια μονάδα αριστερά, αλλιώς πάει μια μονάδα δεξιά. Αν λοιπόν γράψουμε $X_j$ για τη μετακίνηση του σωματίου κατά τη χρονική στιγμή $j$ έχουμε $X_j \in {\left\{{-1, +1}\right\}}$ και ${{\bf {Pr}}\left[{X_j = -1}\right]} = {{\bf {Pr}}\left[{X_j = +1}\right]} = 1/2$, άρα ${\bf E}{X_j} = \frac{1}{2}(-1)+\frac{1}{2}1 = 0$. Η θέση του σωματιδίου τη χρονική στιγμή $n$, έστω $S_n$, μπορεί να γραφεί ως

$$S_n = X_1+\cdots+X_n,$$

οπότε, από τη γραμμικότητα της μέσης τιμής έχουμε επίσης ${\bf E}{S_n} = 0$ για κάθε $n$.

Ας υπολογίσουμε τέλος τη «μέση τετραγωνική απόσταση» του σωματιδίου από το 0 τη χρονική στιγμή $n$. Αυτή είναι η ποσότητα $\sqrt{{\bf E}{S_n^2}}$ και έχουμε

$$S_n^2 = (X_1+\cdots+X_n)^2 = \sum_{j=1}^n X_j^2 + 2\sum_{i<j} X_i X_j,$$

όπου το δεύτερο άθροισμα είναι για όλους τους δείκτες $i,j=1,\ldots,n$, με $i<j$. Επειδή $X_i$ και $X_j$ είναι ανεξάρτητες αν $i \neq j$ και ${\bf E}{X_i} = 0$ έχουμε ότι οι μέσες τιμές όλων των προσθετέων στο δεύτερο άθροισμα είναι 0. Τέλος έχουμε ${\bf E}{X_j^2}=1$ αφού $X_j^2 = 1$ πάντα. Άρα ${\bf E}{S_n^2} = n$ και η μέση τετραγωνική απόσταση από το 0 είναι $\sqrt{n}$.

Άσκηση 12.21   Έχουμε $n$ παίκτες που ρίχνουν από ένα ζάρι ο καθένας. Αν $X$ είναι το πλήθος των ζευγών που φέρνουν τον ίδιο αριθμό να βρεθεί η ${\bf E}{X}$.

Άσκηση 12.22   Έχουμε $n$ ζευγάρια και από αυτά τα $2n$ άτομα ένα τυχαίο υποσύνολο μεγέθους $m$ πεθαίνει. Να βρεθεί ο μέσος αριθμών των ζευγαριών που έχουν απομείνει.

Άσκηση 12.23   Έχουμε δύο κουτιά που στην αρχή περιέχουν $n$ κόκκινους βώλους το πρώτο και $n$ μπλε βώλους το δεύτερο. Σε κάθε χρονική στιγμή βάζουμε από ένα χέρι σε κάθε κουτί, πιάνουμε από ένα βώλο και τους εναλλάσσουμε. Να βρεθεί ο μέσος αριθμός κόκκινων βώλων στο πρώτο κουτί μετά από $k$ τέτοιες εναλλαγές.

Υπόδειξη: Ένας κόκκινος βώλος είναι στο πρώτο κουτί μετά από $k$ βήματα αν και μόνο αν έχει επιλεγεί για εναλλαγή ένα άρτιο αριθμό φορών.

Άσκηση 12.24   Η ακέραια ΤΜ $X$ έχει πυκνότητα $f_X(n)$. Εκτελούμε το πείραμα που δίνει τιμή στη $X$ αλλά δε βλέπουμε την τιμή αυτή. Πρέπει να τη μαντέψουμε. Αν η τιμή που θα πούμε, έστω ο ακέραιος $t$, είναι μικρότερη από τη $X$ τότε πληρώνουμε $b\cdot y$ ευρώ, όπου $y={\left\vert{X-t}\right\vert}$. Αν είναι μεγαλύτερη τότε πληρώνουμε $a\cdot y$. Οι αριθμοί $a, b$ όπως και η συνάρτηση $f_X(n)$ μας είναι γνωστοί. Πώς πρέπει να επιλέξουμε το $t$ ώστε να έχουμε το μικρότερο δυνατό μέσο κόστος;

Σχήμα 12.3: Ο Paul Erdos.

Άσκηση 12.25   Ο Paul Erds (ουγγρικά: Erdos Pál) υπήρξε από τους πρωτεργάτες και ο κυριότερος προπαγανδιστής της λεγόμενης «<πιθανοθεωρητικής μεθόδου» (probabilistic method) στα μαθηματικά και ιδιαίτερα σε αυτό που σήμερα ονομάζεται «διακριτά μαθηματικά» (θεωρία αριθμών, συνδυαστική, θεωρητική επιστήμη υπολογιστών). Η πρωσοποποίηση της ιδιορρυθμίας, ο Erds έζησε μια ζωή γεμάτη μαθηματικά και μόνο, τα οποία σημάδεψε με δεκάδες σημαντικά αποτελέσματα και εκατοντάδες συνεργασίες σε όλο τον κόσμο.

Χαρακτηριστικό μιας πιθανοθεωρητικής απόδειξης (ειδική περίπτωση μιας υπαρξιακής απόδειξης) είναι ότι δείχνουμε την ύπαρξη ενός αντικειμένου με κάποιες επιθυμητές ιδιότητες χωρίς να «κατασκευάσουμε» ένα τέτοιο αντικείμενο, τουλάχιστον όχι με την κλασική έννοια του όρου κατασκευή. Αντίθετα δείχνουμε ότι ένα κατάλληλο στατιστικό πείραμα έχει θετική (και συνήθως μεγάλη) πιθανότητα να παραγάγει ένα τέτοιο αντικείμενο.

Υποθέστε ότι έχετε ένα πλήρες γράφημα με $n$ κορυφές ($n$ σημεία δηλ. που όλα ενώνονται με όλα τα άλλα, με πλήθος ακμών ${n \choose 2}$) και ότι κάθε ακμή του μπορεί να βαφεί κόκκινη ή μπλε. Δείξτε ότι μπορείτε να επιλέξετε τα χρώματα των ακμών έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που σχηματίζονται να είναι το πολύ $\frac{1}{4} {n \choose 3}$.

Σχήμα 12.4: Για την Άσκηση 12.26.

Άσκηση 12.26   Έχουμε 1000 κουτιά στη σειρά (στις θέσεις 1, 2, 3, ..., 1000).

Δείξτε ότι μπορούμε να τα βάψουμε με δύο χρώματα, π.χ. κόκκινα ή μπλε, με τέτοιο τρόπο ώστε να μην υπάρχει αριθμητική πρόοδος μήκους 20 από κουτιά που να είναι όλα το ίδιο χρώμα. (Δείτε το Σχήμα 12.4.)