Απόδειξη

Έστω  ένα σύνολο τυχαίων μεταβλητών οι οποίες παίρνουν τιμές στο σύνολο {1...Β} .  Υπό την προϋπόθεση ότι οι μεταβλητές αυτές είναι τυχαία κατανεμημένες, τότε για: 

ισχύει 

Δηλαδή η πιθανότητα, δύο από τις n επιλεχθείσες μεταβλητές, να έχουν την ίδια τιμή είναι μεγαλύτερη του 1/2.

Απόδειξη

Έστω Ρ η πιθανότητα εύρεσης δύο ισότιμων μεταβλητών σε ένα σύνολο n τυχαία επιλεχθέντων. Τότε η πιθανότητα αυτή μπορεί να εκφραστεί ως 1 - Ρ', όπου Ρ' είναι η πιθανότητα όλες οι μεταβλητές να έχουν διαφορετική τιμή (δεν υπάρχει σύγκρουση).

Έστω αρχικά ότι επιλέγουμε τη μεταβλητή  τότε η πιθανότητα Ρ' είναι 1 αφού η τιμή της  δεν είναι δυνατόν να έχει επιλεχθεί ξανά. Έστω στη συνέχεια ότι επιλέγουμε μία νέα τιμή και την αντιστοιχούμε στην . Η πιθανότητα Ρ' παίρνει πλέον την τιμή , αφού υπάρχουν Β-1 / Β που δεν συμπίπτουν με την  συνεχίζοντας την τυχαία αντιστοίχηση τιμών η πιθανότητα Ρ' διαμορφώνεται ως: , άρα η Ρ θα πάρει την τιμή:

απ' όπου αποδεικνύεται ότι ισχύει  (βλ. ανάπτυξη σειράς Taylor της ) :

Στην τελευταία σχέση εκτελώντας την αντικατάσταση  θα πάρουμε τελικά:

 Εφαρμόζοντας τα παραπάνω στην περίπτωση των γενεθλίων, για Β = 365 θα χρειαστούμε n = 1.2 sqr(365) = 23 άτομα προκειμένου να βρούμε 2 από αυτά τα οποία θα έχουν την ίδια ημερομηνία γέννησης. 

Ο γενικός τύπος επίλυσης 

n = roundup( sqrt(-2 * ln(1 - probability_of_match)) * sqrt(total_items) ) // items needed for match