Μιλήσαμε για το παρακάτω πρόβλημα: ας πούμε ότι περνάνε από μπροστά μας $N$ αντικείμενα (δεν ξέρουμε το $N$) και θέλουμε να κρατήσουμε $k$ από αυτά. Ο χώρος που έχουμε διαθέσιμο για αποθήκευση είναι ακριβώς $k$. Θέλουμε επίσης τα $k$ αυτά από τα $N$ που θα κρατήσουμε να είναι επιλεγμένα τυχαία από τα $N$ αντικείμενα, με όλα τα $N$ αντικείμενα να είναι εξίσου πιθανόν να επιλεγούν.
Αν γνωρίζαμε εξ αρχής το $N$ θα ήταν εύκολο: παίρνουμε από πριν μια τυχαία μετάθεση του συνόλου $\{1, 2, \ldots, N\}$ και αποφασίζουμε να κρατήσουμε αυτά τα αντικείμενα (τα αντικείμενα είναι οι αριθμοί 1, 2, ..., N) που είναι στις πρώτες $k$ θέσεις της μετάθεσης. Προφανώς κάθε αντικείμενο έχει ίδια πιθανότητα με κάθε άλλο να επιλεγεί με αυτό τον τρόπο.
Όμως δεν ξέρουμε το $N$. Έτσι κάνουμε το εξής. Ας πούμε ότι σε κάθε ένα από τα αντικείμενά μας αντιστοιχίζουμε ένα τυχαίο αριθμό, ομοιόμορφο στο $[0, 1]$, ανεξάρτητα για κάθε αντικείμενο. Αν κρατήσουμε τα αντικείμενα με τους $k$ μικρότερους αριθμούς τότε θα έχουμε και πάλι λύσει το πρόβλημά μας αφού, και πάλι, κάθε αντικείμενο θα έχει την ίδια πιθανότητα να επιλεγεί, για λόγους συμμετρίας. Δε χρειάζεται να επιλέξουμε τους αριθμούς αυτούς από την αρχή. Αρκεί να επιλέγουμε ένα τέτοιο τυχαίο αριθμό (tag) για κάθε αντικείμενο την ώρα που περνάει από μπροστά μας. Αν το tag του νέου αντικειμένου που μας ήρθε είναι μεγαλύτερο από τα tags των $k$ αντικειμένων που έχουμε κρατήσει μέχρι στιγμής τότε δεν το κρατάμε αφού σε καμία περίπτωση στο τέλος της διαδικασίας δεν πρόκειται να είναι ανάμεσα στα $k$ αντικείμενα με τα μικρότερα tags. Αν έχουμε κρατήσει λιγότερα από $k$ αντικείμενα (αυτό συμβαίνει βέβαια μόνο στα πρώτα $k-1$ βήματα της διαδικασίας) τότε το κρατάμε σίγουρα. Αν, τέλος, το tag του νέου αντικειμένου είναι μικρότερο από το μέγιστο από τα tags που έχουμε κρατήσει, τότε το κρατάμε και διώχνουμε το αντικείμενο με το μέγιστο tag από αυτά που κρατάμε.
Η διαδικασία αυτή υλοποιείται παρακάτω, όπου φαίνεται και ένα παράδειγμα τρεξίματός της με $N=1000$, $k=10$.
import numpy as np
N = 1000 # Πόσα αντικείμενα θα περάσουν (τα 0 έως N-1)
k = 10 # Πόσα αντικείμενα κρατώ από τα N
L = [] # Ποια αντικείμενα έχω κρατήσει μέχρι στιγμής
T = [] # Οι ετικέτες (tags) των αντικειμένων στην L. Το T[i] είναι η ετικέτα του αντικειμένου στο L[i].
for i in range(N): # Για κάθε ένα από τα $N$ αντικείμενα
if len(L)<k: # Δεν έχει γεμίσει ακόμη η λίστα που κρατώ, άρα κρατάω σίγουρα το νέο αντικείμενο.
L.append(i) # το βάζω στη λίστα L
T.append(np.random.uniform()) # του δίνω ένα random tag
continue
x = np.random.uniform() # Το tag για το νέο στοιχείο. Η λίστα μου είναι γεμάτη (k αντικείμενα).
if x > max(T): # Αν το νέο tag είναι μεγαλύτερο από όλα τα tags που έχω ήδη τότε το πετάω.
continue # κοίτα το επόμενο i
# από δω και κάτω το x είναι μικρότερο από max(T),
# άρα πρέπει να το κρατήσω και να διώξω αυτό με max(T)
for j in range(len(T)): # ψάχνω να βρω πού είναι το αντικείμενο με το μέγιστο tag
if T[j] == max(T): # το βρήκα
L[j] = i # βάζω στη θέση του το νέο αντικείμενο
T[j] = x # με το νέο tag
break # δεν ψάχνω άλλο για το μέγιστο tag αφού το βρήκα
# Τυπώνω ποια κράτησα και ποια είναι τα tags τους.
print(L)
print(T)
Παραπέμπουμε εδώ για το πρόβλημα που συζητήσαμε.
Αν υποθέσουμε ότι ο υπολογιστής μας μάς παρέχει ένα τρόπο για να παράγουμε τυχαίους αριθμούς $X$ με ομοιόμορφη κατανομή στο $[0, 1]$ αλλά εμείς θα θέλαμε δείγματα μιας τυχαίας μεταβλητής $Y$ με δεδομένη συνάρτηση κατανομής $F_Y(t) = {\mathbb P}[Y \le t]$ (μια γνωστή συνάρτηση), πώς μπορούμε τότε να το πετύχουμε αυτό;
Διαβάστε εδώ (inversion method) για ένα απλό τρόπο να μετασχηματίσουμε το $X$ σε $Y$ με την απαιτούμενη κατανομή.