Since my birthday was a couple weeks ago, I thought I’d start this blog with a proof and a Java implementation of an alternate version of the birthday problem.

The Problem

An alternate version of the birthday problem is stated as follows:

Given a planet with \(x\) days, find the probability that a \(y\)-group will celebrate a birthday every day.

Proof

Consider the following sets:

  • Let \(\Omega\) be the set of birthdays of a \(y\)-group on a planet with \(x\) days.
  • Let \(A\) be the subset of \(\Omega\) where a birthday is celebrated every day. (This is the set for which we want to compute the probability.)
  • Let \(S_n\) be the subset of \(\Omega\) such that there are no birthdays on the \(n^{\mathrm{th}}\) day.
  • Let \(T_m\) be defined as the set of \(m\)-wise intersection of \(S\)-sets.

With the above sets, we can form \(A^c\) as follows:

\[\begin{align*} A^c = S_1 \cup S_2 \cup \cdots \cup S_x ~. \end{align*}\]

By the Principle of Inclusion-Exclusion,

\[\begin{align} | A^c | &= | S_1 \cup S_2 \cup \cdots \cup S_x | \\ &= |T_1| - |T_2| + |T_3| - \cdots \pm |T_x| \\ &= \sum_{i=1}^x (-1)^{i+1} T_i ~. \end{align}\]

Since each \(T_m\) excludes \(m\) birthdays,

\[\begin{align} |T_m| &= {x \choose x-m} (x-m)^y \\ &= {x \choose m} (x-m)^y \label{cardoft}~. \end{align}\]

Combining equations the last equation of each of the last two groups,

\[\begin{align} |A^c| = \sum_{i=1}^x (-1)^{i+1} {x \choose i} (x-i)^y~. \end{align}\]

This gives the following probability of \(A^c\),

\[\begin{align} P(A^c) &= \frac{\sum_{i=1}^x (-1)^{i+1} {x \choose i} (x-i)^y}{x^y}~. \end{align}\]

Thus,

\[\begin{align} P(A) = \frac{x^y - \sum_{i=1}^x (-1)^{i+1} {x \choose i} (x-i)^y}{x^y}~. \end{align}\]

Java Implementation

Now that we know the formula, let’s write some Java to compute it. Let’s begin by computing that binomial coefficient \({x \choose i}\) (a classic example of recursion):

public static long choose(int n, int k){
	if (k==n || k==0){
	//We know these
	return 1;
	} else {
	//Compute it recursively
	return choose(n-1,k-1) + choose(n-1,k);
	}
}

Now that we know how to compute the binomial coefficient, we can compute the actual probability:

public static double birthday(int x, int y){
	//Declare variables
	double inex, omega, binom, dayex, complement, probability;

	//Computations
	omega = Math.pow(x,y);
	complement = 0;
	for (int i = 1; i <= x; i++){
		inex = Math.pow(-1, i+1);
		binom = choose(x, i);
		dayex = Math.pow(x-i, y);
		complement = complement + (inex * binom * dayex);
	}
	probability = (omega - complement)/omega;

	//Output the probability
	return(probability);
}

That’s really all there is to it. The full version is available as a gist.