Birthday Problem

You have N people at a dinner party.  How likely is it that two guests have the same birthday?

The first insight is that the probability $A$ of having a birthday pair is one, less the probability $B$ of having $N$ totally unique birthdays. That is, $A=1-B$.  Let's work $B$, it makes for easy counting.

We're looking for a probability, which in this case is a ratio between two things.  The first thing we want to know is, how many ways are there for $N$ people to have birthdays (any birthdays at all)?  That's easy: $365^N$.  The other thing we want to know is, how many ways are there for N people to NOT share a birthday?  That is, how many ways can we have $N$ unique birthdays?  Well, for more than 365 people we must have at least one pair, but for less than this a little reflection reveals the answer to be $365 * 364 * 363 * 362 * ... * (365-N)$.  In other words, let one person have any birthday, the next can have almost any birthday, the next one less, etc... The ratio of these is the probability we're after.

$$ P(N) = \frac{365 * 364 * 363 * ... * (365-N)} {365^N} =  \frac{365!}{365^N (365-N)!} $$

Here's a plot of P(N) for up to 100 people.  You can see the probability of unique birthdays is very high for small numbers of people, but crosses the "even odds" plane at 23 people.

Amort

Ever thought about what the actual formula is for your loan payment schedule? Spreadsheet functions and financial calculators make it easy to avoid the details, but let's dig into it anyway. The formula

\[ A = P \left( \frac{r  }{1-(1+r)^{-N}} \right) \]

looks sorta complicated.

Let $A$ be the monthly payment we're after, and $P$ is the initial principle. The monthly interest rate is $r$.  That is, the loan grows by a factor of $(1+r)$ every month. We want to set up the payments so that after N months, the loan is paid and we're done.

So how do we do this? Every month the balance on the loan will be different, let's use $\alpha_m$ for the balance at month $m$. We know two things right away:

\[ \alpha_{0} = P \tag{initial balance} \]
\[ \alpha_{N} = 0 \tag{ending balance}\]

So we have

\[ 0 = \alpha_N  = (1+r) \alpha_{N-1} - A \]

The last balance, $0$, is the penultimate balance increased by the interest and reduced by the monthly payment $A$. Let's rewrite in terms of $A$:

\[ A = (1+r) (\alpha_{N-1}) \]

\[ A = (1+r)( (1+r) \alpha_{N-2} - A ) \]

 \[ A (1  + (1+r))  = (1+r)^2 \alpha_{N-2} \]

 \[ A (1  + (1+r))  = (1+r)^2 ((1+r) \alpha_{N-3}  -A)\]
 
  \[ A (1  + (1+r) + (1+r)^2)  = (1+r)^3 \alpha_{N-3} \]

We can take this all the way to N, where the form for $A$ will be:

\[ A \left(  \sum_{n=0}^{N-1}  (1+r)^n \right) = (1+r)^N \alpha_0 \]

 The sum on the left is a geometric series that we know how to evaluate:

\[ A \left(  \frac{1- (1+r)^N}{1-(1+r)} \right) = (1+r)^N P  \]

Finally,

\[ A = \frac{rP(1+r)^N } {(1+r)^N -1}= P \left( \frac{r} {1-(1+r)^{-N}} \right)  \]