Birthday buddies

Suppose you have $10$ balls and each person has to pick a different ball. The first can choose from $10$ . The second person only has $9$ to choose from. So the probability of $2$ people choosing different balls is: $10/10 \times 9/10 = 0.9$ . For three people $10/10 \times 9/10 \times 8/10 = 0.72$ . This can also be applied to the birthday problem. The probability that three people do no have the same birthday is $365/365 \times 364/365 \times 363/365 = 0.99$ Subtract that value from $1$ and you get the probability that they do have the same birthday which is around $0.01$ . What is required now is to write a python script to do similar a computations for us

def p( n, days ):
   Pn = 1.0
   days *= 1.0
   for i in range( n + 1 ):
      Pn *= (days - i) / days
      P = 1.0 - Pn
   return P

n = 0
while True:
    n += 1
    if round( p( n , 365 ) , 1) == 0.5: #Check if n is close to 0.5
        if round( p(n+1,365),1) != 0.5: #If it is check if n+1 is closer
            print n #If n+1 is not closer print n and stop the loop
            break

The probability of at least $2$ from $n$ people having the same birthday can be stated as:

$p(n) = 1 - \overline{p}(n)$

where $\overline{p}(n) = \frac{P^{365}_n}{365^n}$

So, the value of $n$ so that $p(n)$ is as close as possible to $\frac{1}{2},$

$\frac{P^{365}_n}{365^n} \approx \frac{1}{2}$

Hence, the closest is $p(n) = 0.507,$ for $n = 23.$

This is the Birthday Paradox .

We find $n$ where $p(n)=\dfrac{1}{2}$ , and then find the closest integer to $n$ . To do this, we calculate the probability that no two people have the same birthday. Note that for $2$ people, the probability of different birthdays is $\dfrac{365}{365}\cdot\dfrac{364}{365}=\dfrac{364}{365}$ . For $n$ people, there are $\displaystyle\binom{n}{2}$ pairs. The probability that no two pairs share the same birthday is therefore $\left(\dfrac{364}{365}\right)^{\binom{n}{2}}$ . Since the probability that at least one pair shares a birthday is $\dfrac{1}{2}$ , the probability that no pair shares a birthday is $1-\dfrac{1}{2}=\dfrac{1}{2}$ . So that means that $\left(\dfrac{364}{365}\right)^{\binom{n}{2}}=\dfrac{1}{2}$ . Setting this up in logarithm form we get that $\log_{\frac{364}{365}}{\dfrac{1}{2}}=\displaystyle\binom{n}{2}$ . Using a calculator to solve the log gives $\displaystyle\binom{n}{2}\approx 252.65$ . We round that to $253$ . The equation becomes $\displaystyle\binom{n}{2}=253$ . Writing the binomial in factorial form gives $\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)}{2}=253$ . Multiplying by $2$ and expanding gives the quadratic $n^2-n-506=0$ , and using the quadratic equation gives the solutions $n=-22,23$ . Discarding the extraneous negative solution we get that the answer is, almost perfectly, $23$ (remembering that we rounded off the decimal before doing the quadratic). Therefore the answer is $\boxed{23}$ .

I used iteration instead of recursion here.

Mathematically, the probability that $n$ people have distinct birthdays as described in the question is $\prod_{m = 1}^{n} (1 - \frac{m}{365})$ . Since as $n$ increases this product decreases, we only need to be concerned with 2 specific probabilities - just before and just after adding $1$ to $n$ will cause the probability to decrease beyond $0.5$ .

I wrote the following Java code to solve the problem:

public static void main(String[] args) {
    double x = 1;
    double v = 1;
    int c;
    for(c = 365; v > 0.5; c--) {
        x = v;
        v = x * c/365;
    }

    System.out.println(v + " at " + (365 - c) + " people");
    System.out.println(x + " at " + (365 - c + 1) + " people");

    if(Math.abs(0.5 - v) < Math.abs(0.5 - x)) {
        System.out.println(365 - c);
    } else {
        System.out.println(365 - c + 1);
    }
}

python...:)

My solution using Java:

class Main{
    public static void main(String[] args){
        double min = 1;
        int res = 0;
        for(int n=1; n<=999; n++){
            double diff = Math.abs(calc(n)-0.5);
            if(diff<min){
                min = diff;
                res = n;
            }
        }
        System.out.println(res);
    }

    public static double calc(int n){
        double result = 1.0;
        for(int i=0; i<n; i++){
            result = result*(365-i)/365;
        }
        return result;
    }
}

$p(n)=\frac{1}{2}\to1-p(n)=\frac{1}{2}$ $q(n):=1-p(n)=\frac{_{365}P_n}{365^n}=q(n-1)\frac{366-n}{365}$ which $~\frac{1}{2}$ at $n=23$

Let us define $q(n)$ to be the probability that out of $n$ people, no two share a common birthdate. It can be seen that $q(n) = \prod_{k=0}^{n-1} \frac{365-k}{365}$ . In addition, one notices that $p(n) = 1 - q(n)$ .

We write a simple function to compute $q(n)$ :

double q(int n)
{
    if(n <= 1) return 0.0; // Less than two people
    if(n > 365) return 1.0; // Guaranteed due to pigeonhole principle.

    double prob = 1.0;
    for(int i = 0; i <= n-1; i++)
        prob *= (365.0-i)/365.0;

    return prob;
}

With this function, we can iterate on values of $n$ from $1$ to $365$ and note the value of $n$ where $|\frac{1}{2} - (1-q(n))|$ is minimized.

Long live C

#include <stdio.h>
#include <math.h>

int main() {

  double p = 1;
  int n, i;

  n = 1;
  while (p >= 0.5) {
    n++;
    for(i = 365, p = 1; i > 365 - n; p *= i--);
    p /= pow(365,n);
  };

  printf("The probability is as close to 1/2 for %d people\n", n);

  return 0;

}

The chance that at least 2 people share a birthday is the same as 1 - (probability no people share a birthday).

def birthday(n): prod = 1 for i in range(1,n): prod *= fractions.Fraction(365-i,365) return 1 - (prod.numerator / prod.denominator)

This is equivalent to $1 - \frac {\frac {364!}{(365-n)!}}{365^{(n-1)}}$

The probability that two or more share a birthday is also the same as the 1 - p(no one shares a birthday). To find the value of n which makes 1 - p(no one shares a birthday) as close to 1/2 as possible, we can use this python script:

def birthday(p, numerator, count):
if p < 1/2.0:
    return count
p = p * numerator/365.0
return birthday(n, numerator - 1, count + 1)

p(no one shares the same birthday) = everybody having different birthdays. The probability of that is 365/365 * 364/365 * 363/365 * .... This is because after person 1, person 2 can have a birthday on 364 days (1 is already taken), person 3 can then have a birthday on 363 days (2 are already taken), and so on.

1 - p(n) is the probability that no two or more people have birthday the same day. So the question is the same as finding n for which the probability that no two or more people have birthday the same day is 1/2;

The last line of output indicates the number of people

Here is my C code:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    double porcentagem = 1; /* 1 - p(n) */
    double dif = 0.5;   /* difference between 1 - p(n) found and desired */
    double last = 0.5;  /* last difference computed */

    int i; /* number of people */

    for (i = 2; porcentagem > 0.5; i++) {
        porcentagem = porcentagem * (365 - i + 1)/365.0;
        last = abs(0.5 - porcentagem);
        printf("porcentagem = %lf, i = %d\n", porcentagem, i);
        if (last > dif) {
            break;
        } else {
            dif = last;
        }

    }

    return 0;
}

Let $A$ be the event that of $n$ people in a room, at least two of them share a birthday. Let $A^c$ denote the complementary event: all people in the room have distinct birthdays. Then $Pr(A) = 1 - P(A^c) = 1 - prod_{i = 0}^n \frac{365 - n}{365}$ Computing this for $n \in \{1, \ldots, 365\}$ shows $n=23$ gives the probability closest to 0.5.

def f(n) :
    s = 1
    for i in range(n) :
        s *= 1 - i/365.
    return s

# Dichotomy
left, right = 1, 365
step = 2
while step >= 1 :
    step = (right - left) / 2
    if f(int(left + step)) > 0.5:
      left += step
    else :
      right -= step
if f(left) + f(right) < 1 :
    print(left)
else :
    print(right)

First, we write a function that determines p(n) using a simple complimentary method. Then, we use this to find the desired n.

def birthdays(n):
    prob = 1
    for i in range(n):
        prob *= (365-i)/365
    return 1-prob

min(enumerate([abs(birthdays(i)-0.5) for i in range(365)]),key = lambda x: x[1])

My key technique was to find a formula for the probability and then check when the difference between that probability and $1/2$ was least. The formula I found was $p(n) = 1 - \dfrac{364 \cdot 363 \cdots (366-n)}{365^{n-1}},$ which can be verified by considering the complement of $p(n)$ (the probability that nobody shares a birthday).

def birthdays():
    """Finds when the probability that people share a birthday is about 1/2"""

    closestN = 0
    smallestDifference = 1

    for n in range(2, 366):
        probability = 1
        # complementary probability

        for multIndex in range(364, 365-n, -1):
            probability *= (multIndex/365)
            # multiplies by the probability that each person doesn't share a birthday

        probability = 1 - probability
        # takes the complement

        difference = abs(probability - 0.5)

        if difference < smallestDifference:
            closestN = n
            smallestDifference = difference

        else:
            if probability > 0.5:
                break
                # if the difference is getting larger, then we can stop looking

    return closestN

Given that this is a well-known problem and there is no fun in solving it analytically, why not do the simulation and get the answer? Take N people and assign birthdays randomly to them. Repeat this T times and check how many times (S) a birthday match occurs. Increase N till S becomes >=T/2.

# include <cstdio>
# include <cstdlib>

int ar[367];
const int T=1000000;

int main()
{
  //Once you reach 366 people, you will definitely have a match
  for(int i=2;i<=366;i++)
  {
    //Number of scenarios with a birthday match
    int cnt=0;
    for(int t=0;t<T;t++)
    {
      //Start simulating a scenario
      for(int j=0;j<i;j++)
      {
        //Assign a birthday randomly
        ar[j]=rand()%365;

        //Check if someone assigned till now has the same birthday
        for(int k=0;k<j;k++)
        {
          if(ar[j]==ar[k])
          {
            //This is a birthday-match scenario
            cnt++;
            goto BPP;
          }
        }
      }
BPP:;
    }
    if(2*cnt>=T)
    {
      //Probability >1/2
      printf("%d\n",i);
      break;
    }
  }
  return 0;
}

The trick here is to instead compute the probability $p'(n)$ that the room is full of people with distinct birthdays. Since $p(n) + p'(n) = 1$ , we know $p(n) - \frac{1}{2} = \frac{1}{2} - p'(n)$ so $p(n)$ and $p'(n)$ are equidistant from $\frac{1}{2}$ . Thus, we wish to find the value n minimizing the new function p'(n).

We come up with a formula for $p'(n)$ inductively. If $n$ is equal to $0$ or $1$ , then we have just one person in the room so there (trivially) cannot be two people sharing a birthday, so $p'(n) = 1$ . If the room has more than one person, say $k$ , and everyone in the room has some unique birthday, then bringing one new person into the room decreases $p'$ by the probability that this new person has a unique birthday. Since there are 365 days in the year and $k$ of them are already taken by the room's current inhabitants, the probability that this { $k+1$ }th person has a unique birthday is $\frac{365-k}{365}$ .

Therefore, we have the recurrence relation

$p'(0) = p'(1) = 1$ , $p'(k+1) = p'(k) \cdot \frac{365-k}{365}$ .

This can either be implemented as a recursive function, or it can be rewritten as $p'(n) = \frac{P(365,n)}{365^n}$ , where $P(a,b)$ = $a \cdot (a-1) \cdot \ldots \cdot (a-b+1) = \frac{a!}{b!}$ .

Finally, to solve the problem, we plug in values one-by-one into our implementation of p'(), until we find the unique local minimum of $|p'(n) - 1/2|$ on the domain of integers in $\{0,1,2,\ldots,365\}$ , which happens at $n=23$ .