Ich rechne mal überschlagsweise mit der Binomialverteilung.
Der Mann hat also 4000 Bekannte unter 1000000 Leuten. Das sind 4/1000. Das Gegenereignis von mind. ein gemeinsamer Freund ist, die Frau hat alles Freunde, die der Mann nicht hat. Also kann ich die Wahrscheinlichkeit berechnen über
P = 1 - (996/1000)^2000 = 0.9996698761
Die Wahrscheinlichkeit ist also recht hoch, dass sie mind. einen gemeinsamen Freund haben.
Überlege dir jetzt wie sich diese Wahrscheinlichkeit verändert wenn man nicht mit der Bionomialverteilung sondern mit der Hypergeometrischen Verteilung rechnen würde.