Guess the birthday

I've come across the following little quiz game problem, which I've failed to solve.

Say we have $15$ people, each of them of different age, and you want to guess their actual birthday - not just their age.

You are allowed to guess as many times as you want, but the guessing goes as follows:

1. Choose $5$ random people from the group.
2. Each of them gives you four distinct possible dates, which they have chosen before the quiz started (so they will not change their options later in the game). One of these is correct.
3. When you have guessed on the date for all five, they will tell you how many correct guesses, you had. They will not tell you which guesses were correct.

Now the questions are:

1. What is the probability to guess one specific person's birthday in the first try?
2. How many times would you expect, you have to guess to get one person's birthday right?
3. How many times would you expect, you have to guess to get all $15$ people's birthday right?
4. What is the probability to get one person's birthday right in less than $200$ guesses?
5. What is the probability to get all the people's birthday right in less than $3000$ guesses?

The first question was rather easy to answer. When you pick randomly, you have to pick the person, whose birthday you would like to know, the probability of this is $\dfrac{1}{3}$, since we pick $\dfrac{1}{3}$ of the people in the group. To know one person's birthday for sure in the first try, you will have to answer his question correct. But as you will not know which question, you answered correct, when you ask, unless you answered all of them correct, you will have to answer correct, which has the probability $\left(\dfrac{1}{4}\right)^5 = \dfrac{1}{1024}$. So the answer to the first question is $\dfrac{1}{3072}$.

To solve the next questions, I've tried to assume that we only have $5$ people, and that they are always chosen. This gives me a strategy to find one specific person's birthday, since I can just alter my answers to his question, and after maximum four guesses, I've guessed his birthday. Unfortunately, I cannot be sure that he will come up every time, I ask. Actually, I cannot be sure that he will ever come up, but I "only" have to find the expected amount of guesses.

And this is where I got stuck. Any help in tackle this question will be so much appreciated! Hints or even solutions, anything. Thank you very much in advance!

-
It seems to be assumed that each person gives you 4 dates, one of which is correct. That should be edited into the statement of the question. –  Gerry Myerson Jun 20 '13 at 9:15
@GerryMyerson: Yes, that was assumed and now added :) –  Talouv Jun 20 '13 at 9:21
You get definite information not only by guessing five correct, but also by guessing five wrong. Later the game may develop into a variant of MasterMind(TM) –  Hagen von Eitzen Jun 20 '13 at 9:38
Are you assuming that the birthday's given by each person are plausible? I.e. one person does not give 1-1-1940, 1-1-1960, 1-1-1980 & 1-1-2000, one of which is obviously correct by looking at the person? –  Dale M Jun 20 '13 at 21:22
@DaleM Yes, we will assume that every birthday is playsible. –  Talouv Aug 18 '13 at 11:25

Alternative answer which more closely matches the question, I think.

The question as posed suggests that 5 random people (of the 15) are presented to you each round for questioning. I will assume that there is some way of identifying these people from round to round, i.e. if person 3 comes up in round 1 and then again in round 9 you know that it is the same person.

Let $B_{Pb}(g)$ be the probability that Birthday $b \in A,\dots,D$ is person $P\in 1,\dots,15$ Birthday after guess $g$. So $B_{Pb}(0)=0.25$ for all $b$ and $P$.

There are 2 algorithms that could be employed and I am unsure which is the more efficient. These are:

1. In each round, of the five persons presented, select the birthday that currently has the highest probability. This is the one I will analyse.
2. In each round, of the five persons presented, select the birthday that currently has the lowest probability, however, if there are 4 or 5 with 0 probability, select the highest probability of one person and the lowest (i.e. 0) for the others.

So, for each guess, we need to determine how $B_{Pb}(g)\implies B_{Pb}(g+1)$.

Let $G$ be the set of people that are questioned in guess $g$.

Clearly,

1. $B_{Pb}(g+1)=B_{Pb}(g)$ for $P\notin G$ and $\Bbb P(P\notin G)=\frac{2}{3}$.
2. $B_{Pb}(g+1)=B_{Pb}(g)$ if $B_{Pb}(g)=0$ or $B_{Pb}(g)=1$

For $P\in G$, $\Bbb P(P\in G)=\frac{1}{3}$, we will get a number $k \in 0,\dots,5$, indicating the number that we have got correct. This is a Poisson Binomial Distribution and

$$\Bbb P(K=k)=\sum_{A\in F_k}\prod_{i\in A}\max(B_{Pb})\prod_{i\notin A}(1-\max(B_{Pb}))$$

where $F_k$ is the set of all subsets of $k$ integers that can be selected from $\{1,2,3,4,5\}$ and $P\in G$.

Now:

1. For $k=5$, then we have identified the birthdays for all $P\in G$, and $$B_{Pb}(g+1)=\begin{cases} 1&\text{for the selected birthday}\\ 0&\text{otherwise}\\ \end{cases}$$
2. For $k=0$, then we have eliminated $\max(B_{Pb})$ as the birthday for all $P\in G$, and $$B_{Pb}(g+1)=\begin{cases} 1&\text{for the selected birthday}\\ \frac{B_{Pb}}{1-\max(B_{Pb})}&\text{otherwise}\\ \end{cases}$$
3. For the other cases, you can refine your estimates of the probabilities using Beyesian inference. I will return to this another time as I have to go to the pub to watch football. Go New South Wales!
-
Those two answers, you've posted are great. Thanks a lot. I've been reading the answers some times now, and it looks like this is one that matches my question the most. –  Talouv Aug 18 '13 at 11:34

A definite answer is very hard to give because there is a lot of convoluted strategy involved. A rough information theoretical approximation is as follows. We have to guess 30 bits of information and the first round gives us about $1.94$ bits, so we might know all after about 16 rounds. However, on the one hand we can increase the expected information gain (though hardly ever to the maximum of $2.58$ bits), on the other hand the information to be gained about five selected people may be less due to knowledge gained in previous rounds.

You can work with a lower bound by assuming the trivial strategy that makes random guesses in each round and only making use of rounds where you guess all correct. As a slight improvement, you may choose to always repeat the known correct giuess for people already solved. However we ignore the fact that all-wrong-guesses can be used to strike away one bad for each of the five people and other advantages. Under this strategy, let $X_n$ be the number of solved people after $b$ rounds. So $X_0=0$ and otherwise \begin{align}P(X_{n+1}=k)=&\frac1{1024}\cdot \frac{20-k\choose 5}{15\choose 5}P(X_n=k-5) \\&+ \frac1{256}\cdot \frac{{19-k\choose 4}{k-4\choose 1}}{15\choose 5}P(X_n=k-4)\\&+ \frac1{64}\cdot \frac{{18-k\choose 3}{k-3\choose 2}}{15\choose 5}P(X_n=k-3)\\ &+\frac1{16}\cdot \frac{{17-k\choose 2}{k-2\choose 3}}{15\choose 5}P(X_n=k-2)\\ &+\frac1{4}\cdot \frac{{16-k\choose 1}{k-1\choose 4}}{15\choose 5}P(X_n=k-1)\\ &+\frac{{k\choose 5}}{15\choose 5}P(X_n=k)\\\end{align} (especially, $P(X_n=1)=\ldots=P(X_n=4)=0$) You can use this recursion to estmiate the expected number of rounds until you know all birthdays: $$E(all)=\sum_{n=0}^\infty P(X_n<15)$$

-
That's a nice strategy. I must admit, I didn't expect to get a definite answer, but more some hints to attack it. Thanks a lot! –  Talouv Aug 18 '13 at 11:29

I offer an alternative strategy and some thoughts on how you might obtain the answers you seek.

Let $B_{Pb}$ be the probability that $b\in 1\dots4$ is the correct birthday for person $P\in 1 \dots 15$. Initially all $B_{Pb}=0.25$.

Select birthday 1 for each of persons 1 to 5. Let $k_1$ be the number we get correct which comes from a Binomial Distribution with $n=5, k_1\in0\dots5, p=0.25$. We then know:

$$B_{Pb}=\begin{cases} {k_1\over5}, &b=1\\ {\left(1-{k_1\over5}\right)\over3},&b\in2\dots4 \end{cases}$$

If $k=5$ $[p={5\choose5}0.25^50.75^0]$, then these 5 are done and you move onto the next 5.

Otherwise, hold persons $2\dots5$ constant and select birthday $2$ for person $1$. There are 3 possible outcomes for $k_2$:

$$\begin{cases} k_2=k_1-1\left[p={k_1\over5}\right],&\implies B_{Pb}=\begin{cases} 1, &P=1,b=1\\ 0,&P=1,b\in2\dots4\\ {(k_1-1)\over4},&P\in2\dots5,b=1\\ {1-{(k_1-1)\over4}\over3},&P\in2\dots5,b\in2\dots4\\ \end{cases}\\ k_2=k_1\left[p={2\left(1-{k_1\over5}\right)\over3}\right],&\implies B_{Pb}=\begin{cases} 0, &P=1,b\in 1,2\\ 0.5,&P=1,b\in3,4\\ {k_1\over4},&P\in2\dots5,b\in2\dots4\\ 1-{k_1\over4}\over 3,&P\in2\dots5,b=1\\ \end{cases}\\ k_2=k_1+1\left[p={\left(1-{k_1\over5}\right)\over3}\right],&\implies B_{Pb}=\begin{cases} 1, &P=1,b=2\\ 0,&P=1,b\in1,3,4\\ {k_1\over4},&P\in2\dots5,b\in2\dots4\\ 1-{k_1\over4}\over 3,&P\in2\dots5,b=1\\ \end{cases}\\ \end{cases}$$

So at this point, you either know Person 1's birthday or will do so with your next guess. So the answer to Question 2 is:

$$0.25^51+\sum_{k_1=0}^4{5\choose k_1}0.25^{k_1}0.75^{5-k_1}\left[2\left({2k_1+5\over15}\right)+3\left(10-2k_1\over15\right)\right]$$

Given that you can get any given persons birthday in at most 3 guesses it will take at most 45 to get them all.

-