1
$\begingroup$

The famous birthday problem runs as follows: in a set of $n$ randomly chosen people, what is the probability that some pair of them share a birthday? The following question is an extension of that famous problem.

Given a set of $n$ randomly chosen people, there is a probability that $k$ people in the set share a birthday with someone else in the set. For a given $n$, what is the most likely $k$? Also, for a given $n$, what is the most likely configuration of birthday sharing, i.e. how many pairs, triplets, etc.?

Note: I am assuming that there are 366 birthdays in a year and that each birthday is equally likely.

$\endgroup$
  • $\begingroup$ note a group is a mathematical object in math not the same as a set. $\endgroup$ – user451844 Jul 26 '17 at 19:17
  • $\begingroup$ @RoddyMacPhee Should have spotted the mismatched mathematical terminology. Edited the question. Thanks :D $\endgroup$ – Sherlock9 Jul 26 '17 at 19:19
  • $\begingroup$ the reason the original problem is so low is because of how many ways there are to choose pairs of people in 23 people there's 253 ways to choose pairs. In general there's $${n!\over k!(n-k)!} = \binom nk$$ ways to choose k people out of n. $\endgroup$ – user451844 Jul 26 '17 at 19:23
  • $\begingroup$ see youtube.com/watch?v=a2ey9a70yY0 to help you out. $\endgroup$ – user451844 Jul 26 '17 at 20:13
  • $\begingroup$ This paper (and references) can be relevant: arxiv.org/pdf/0901.3493.pdf $\endgroup$ – leonbloy Jul 30 '17 at 1:44
3
$\begingroup$

Here are some ideas that may help to get started, presenting an exact formula for eventual verification of results by probabilistic methods, which the reader is invited to contribute. Supposing we have $m$ possible birthdays and $n$ people we get the marked species

$$\mathfrak{S}_{=m}(\mathfrak{P}_{=0}(\mathcal{Z}) + \mathfrak{P}_{=1}(\mathcal{Z}) + \mathfrak{P}_{\ge 2}(\mathcal{U}\mathcal{Z}))$$

with generating function

$$G(z, u) = (\exp(uz)-uz+z)^m.$$

With this generating function we count the number of configurations of $n$ samples from $m$ birthdays where $k$ of them are sharing with someone else in the configuration. Extracting coefficients we find

$$n! [z^n] [u^k] (\exp(uz)-uz+z)^m \\ = n! [z^n] [u^k] \sum_{q=0}^m {m\choose q} \exp(quz) z^{m-q} (1-u)^{m-q} \\ = n! [u^k] \sum_{q=\max(0, m-n)}^m {m\choose q} [z^{n+q-m}] \exp(quz) (1-u)^{m-q} \\ = n! [u^k] \sum_{q=\max(0, m-n)}^m {m\choose q} \frac{q^{n+q-m} u^{n+q-m}}{(n+q-m)!} (1-u)^{m-q} \\ = n! \sum_{q=\max(0, m-n)}^m {m\choose q} \frac{q^{n+q-m}}{(n+q-m)!} [u^{k-n+m-q}] (1-u)^{m-q} \\ = n! (-1)^{k-n+m} \sum_{q=\max(0, m-n)}^m {m\choose q} \frac{q^{n+q-m}}{(n+q-m)!} (-1)^q {m-q\choose m-q-(n-k)} \\ = n! (-1)^{k-n+m} \sum_{q=\max(0, m-n)}^m {m\choose q} \frac{q^{n+q-m}}{(n+q-m)!} (-1)^q {m-q\choose n-k}.$$

Now observe that

$${m\choose q} {m-q\choose n-k} = \frac{m!}{q! (n-k)! (m-q-(n-k))!} \\ = {m\choose n-k} {m-(n-k)\choose q}$$

and we get

$$n! (-1)^{k-n+m} {m\choose n-k} \sum_{q=\max(0, m-n)}^m \frac{q^{n+q-m}}{(n+q-m)!} (-1)^q {m-(n-k)\choose q}.$$

We can re-write this one more time to get a binomial coefficient to enforce the lower limit, using

$$\frac{q^{n+q-m}}{(n+q-m)!} {m-(n-k)\choose q} = \frac{q^{n+q-m}}{q!} {k\choose n+q-m} \frac{(m-(n-k))!}{k!}$$

to get

$$\bbox[5px,border:2px solid #00A000]{ m! (-1)^{k-n+m} {n\choose k} \sum_{q=1}^m \frac{q^{n+q-m}}{q!} (-1)^q {k\choose n+q-m}.}$$

Working with the month of the birthday as opposed to the day in the year we get twelve possibilities and the following sequence of the most likely $k$ when querying $n$ people starting at $n=1$ and ranging to $n=36$:

$$0, 0, 0, 0, 2, 2, 2, 4, 4, 6, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, \\ 17, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, \ldots $$

What we see here that for $n\ge m$ the behavior appears to be dominated by a linear term. Same for e.g. $32$ different birthdays ranging from $n=1$ to $n=72$:

$$0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 8, 8, 8, 10, 10, \\ 12, 12, 14, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, \\ 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, \\ 47, 49, 50, 51, 52, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 65, \ldots $$

Looking at the intial and the terminal segments of these data we see that with $n$ small compared to $m$ the largest group of people is the group of singletons not sharing with anyone else, which is as we would expect. On the other hand with $n$ large compared to $m$ almost all elements are sharing with someone else, e.g. of $72$ birthdays the most likely case is that $65$ of them are sharing, leaving $7$ singletons. The following plot shows the fraction of values that are sharing for twelve birthdays.

Twelve birthdays

This plot shows the same statistic for $366$ birthdays with $n=1$ to $n=320$ people.

Three-hundred and sixty six birthdays

The Maple code for anyone wanting to work with these statistics is as follows. The enumeration routine can be optimized but it yields confirmation results in a sufficient number of cases and we have the closed form, of course.

with(plots);

ENUM :=
proc(n, m)
option remember;
local ind, gf, d, mset, sh;

    gf := 0;

    for ind from m^n to 2*m^n-1 do
        d := convert(ind, base, m);
        mset := convert(d[1..n], `multiset`);

        sh := add(`if`(p[2] < 2, 0, p[2]), p in mset);
        gf := gf + u^sh;
    od;

    gf;
end;

ENUMCF := (n, m, k) -> coeff(ENUM(n, m), u, k);

XCF :=
(n, m, k) -> n!*(-1)^(k-n+m)
*add(binomial(m, q)*q^(n+q-m)/(n+q-m)!*(-1)^q
     *binomial(m-q, n-k), q=max(0, m-n)..m);

XCF2 :=
(n, m, k) -> n!*(-1)^(k-n+m)*binomial(m, n-k)
*add(q^(n+q-m)/(n+q-m)!*(-1)^q*binomial(m-(n-k), q),
     q=max(0, m-n)..m);

XCF3 :=
(n, m, k) -> m!*(-1)^(k-n+m)*binomial(n,k)
*add(q^(n+q-m)/q!*(-1)^q*binomial(k, n+q-m), q=1..m);

MXK :=
(n, m) ->
sort([seq([k, XCF3(n, m, k)], k=0..n)],
    (p1, p2) -> p1[2] < p2[2])[n+1][1];

PL := (n, m) ->
pointplot([seq([k, XCF3(n, m, k)], k=0..n)], `connect`);

PLMX := (n1, n2, m) ->
pointplot([seq([n, MXK(n, m)/n], n=n1..n2)], `connect`);

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Letting $m=$ number of days, $n=$ number of people, $k=$ number of people with shared birthdays. Then $j=n-k=$ number of "singletons".

The problem is equivalent to the following urn-and-balls problem: place randomly $n$ balls uniformly inside $m$ urns, find $P(j)$ , distribution of the number of single occupancy urns (singletons).

A simple (perhaps too simple) Poissonization approximation gives

$$E[j]\approx n\, e^{-n/m} \tag{1}$$

We can expect that asymptotically $j$ tends to a normal, so that the most probable value is near the mean. A graph for the average fraction of shared birthdays ($1-E[j]/n$), under the above approximation and for $m=366$ is shown below. It agrees quite well with the graph from Marko Riedel's answer.

enter image description here

This paper studies some asymptotic approximations in more detail.


Edit Actually, there's no need to do a Poissonization approximation to compute the mean. The probability of a given urn of being a singleton is $ \frac{n}{m} (1-\frac{1}{m})^{n-1} $, hence

$$ E(j)=n \left(1-\frac{1}{m}\right)^{n-1} \tag{2}$$

Obviously, $(1)$ and $(2)$ are asympotically equivalent for large $m,n$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.