Serendipity

The word serendipity comes from the Persian fairy tale of the Three Princes of Serendip

Problem

What is the probability of a seredipitous encounter with a friend? Imagine you are live in an area with a large general population (eg Stanford with 17,000 students). A small subset of the population are friends. What are the chances that you run into at least one friend if you see a handful of people from the population? Assume that seeing each person from the population is equally likely.

Total Population

Friends

People that you see

Answer

The probability that you see at least one friend is:

Terms

First lets define some useful terms:
$p$ = total population =
$s$ = people seen =
$f$ = num friends =

Approach

Since each way of seeing $s$ people is equally likely, we can use the "Equally Likely Events" probability calculation:

$P(E) = \frac{|E|}{|S|}$

Where $S$ is the sample set (all the ways of seing $s$ people) and $E$ is the event set (all the ways of seing $s$ people where at least one is a friend).

One way to approach this problem is to directly count all ways you see 1 or more friends. That is hard. You would have to count the ways you could see exactly one friend, then exactly two friends and so on. It is much easier to calculate the ways that you see zero friends. If we can calculate the probability of seeing zero friends our answer is just one minus that number.

Prob that you don't see friends

Let the sample space ($S$) be the set of ways that you could see $s$ people. The size of the sample space is: the total population choose the number of people seen.

The event space ($E$) is the set of ways that you could see no friends. The size of the event space is: the number of non friends (aka population - friends) choose the number of people seen.

Thus the probability of not seeing a friend is:

$\text{prob(not seen)} = \frac{ \left( {\begin{array}{*{20}c} p - f \\ s \\ \end{array}} \right) } { \left( {\begin{array}{*{20}c} p \\ s \\ \end{array}} \right) } $

Prob that you see friends

Now the probability that you see at least one friend is 1 minus the probability that you see no friends.

$\text{prob(seen)} = 1 - \frac{ \left( {\begin{array}{*{20}c} p - f \\ s \\ \end{array}} \right) } { \left( {\begin{array}{*{20}c} p \\ s \\ \end{array}} \right) } $

That is equal to