# The chance of finding a soulmate

Suppose there is a city with population $n$. Suppose also that, for each person, there's a chance $p$ that their soulmate is living in the same city.

In this city there's a club with $m$ members. What's the chance that there are no pairs of soulmates in this club?

Let's analyse a person who belongs to the club. They have a chance $1-p$ of having their soulmate in another city. If their soulmate lives in the city, then there's a chance $\frac{n-m}{n}$ of the soulmate not belonging to the club.

There are $m$ members in the club so the total chance of not having any pairs of soulmates is:

$$\left( 1-p + p\frac{n-m}{n}\right)^m=\left( 1 +p\frac{n-m-n}{n}\right)^m =\left( 1 -p\frac{m}{n}\right)^m$$

Here's my doubt

I assumed all events are independent, but clearly if $m-1$ persons don't have a soulmate in the club, then the last person can't have a soulmate in the club either. If we assume soulmate is a symmetric property, then what's the proper solution?

-
Would anyone mind terribly if I change all instances of "he" and "his" to "they" and "their" in this question? – Rahul Nov 18 '12 at 19:55
No, please change. – Ricbit Nov 18 '12 at 19:55

I think you're right about the independence problem.

Perhaps a better way to look at it would be to consider all $k$ people living in the world both inside and outside your city. Then, by your soulmate property, we can divide these $k$ people into pairs of soulmates.

If $n$ is the population of the city, then the probability of one soulmate living in the city is $n/k$. The probability that one soulmate belongs to the club is $(n/k)(m/n)=m/k$, because $m/n$ is the probability that a given city resident belongs to the club.

Then, the probability that both soulmates belong to the club is $(m/k)^2$, and the probability that the pair together don't belong is $1-(m/k)^2$. The probability that no pair belongs whatsoever is this probability raised to the power of the number of pairs, which is $k/2$; that is, $$\text{P[no pair belongs]} = \left( 1-\left(\frac{m}{k}\right)^2 \right)^{k/2}$$

We can put this answer in terms of your variables. You say that given one person, the probability that their soulmate lives in the city is $p$. But, if the events "soulmate 1 lives in the city" and "soulmate 2 lives in the city" are independent (that is, soulmates are not predestined to live in the same place), then the probability that anyone lives in the city is $p$. Then we have $$\text{population of city} = \text{total population} \times \text{probability of living in city} \implies n=kp$$and our answer is $$\text{P[no pair belongs]} = \left( 1-\left(\frac{pm}{n}\right)^2 \right)^{n/2p}$$ If there are 7 billion people in the world and our club has 1000 members, the outlook is unfortunately bleak: http://www.wolframalpha.com/input/?i=%281-%281000%2F7+billion%29%5E2%29%5E3.5+billion

-
Thanks for the answer! – Ricbit Nov 19 '12 at 0:59