POINTLESS is a BBC game show. Each night, four teams compete. If a team does not win, it comes back for a second night; but not a third night. Each night has 1, 2, 3 or 4 new teams. There are never 0 new teams because the previous night's winner does not come back.
1. What is the chance that all 4 teams are new?
2. If I replace 4 by $n$, what is the chance that all $n$ teams are new?
My Try
There are $n$ states, given by the number of new teams.
They form a linear Markov chain, with two states adjacent if they add up to either $n$ or $n+1$. If it weren't for the winner, new teams would become old; and old teams replaced by new, so they add to $n$; if a new team won, there is an extra new team.
All the nights with $n$ new teams are preceded by nights with 1 new team, but only one-in-$n$ of the nights with $1$ new team are followed by a night with $n$ new teams - when the single new team wins. So $1$ new team must happen $n$ times as often as $n$ new teams.
Similar arguments at each transition show that states $n,1,n-1,2,n-2,3,...$ appear with relative frequency $$1:n:n(n-1):{n\choose2}(n-1):{n\choose2}{n-1\choose2}:...$$
So state $m$ appears with relative frequency ${n\choose m}{n-1\choose n-m}$. The sum from $1$ to $n$ is clearly ${2n-1\choose n}$.
Comment: Is there a simpler reason that $2n-1\choose n$ appears?
Question 1: What if an old team is $k$ times as likely to win as a new team?
Question 2: What if teams stayed for up to three nights unless they won?
- 50,853
-
What is the probability that a losing team comes back for the second night? – Win Vineeth Feb 14 '16 at 04:35
-
Sorry, all losing teams come back for a second night. – Empy2 Feb 14 '16 at 04:38
-
Does each contesting team (old or new) on any night have equal chance of winning ? – true blue anil Feb 14 '16 at 04:52
-
1I don't know; for these purposes, say they have equal chances of winning. – Empy2 Feb 14 '16 at 04:53
-
When is this due? – Did Feb 14 '16 at 08:31
-
@Did the answer is one in ${2n-1\choose n}$, and the chance of $m$ new teams is ${n\choose m}{n-1\choose m-1}$ in ${2n-1\choose n}$. I thought it was a nice puzzle that I thought up, but if you are going to close it... – Empy2 Feb 14 '16 at 09:23
-
I think all that can be said is to identify the scenario in which all teams are new. Supplying the "probability" of this is not possible without some assumptions (as in every night each team has an equal chance of winning independent of their previous experience). – hardmath Feb 14 '16 at 13:16
2 Answers
Answering my own question:
When old teams are $k$ times more likely to win, the relative likelihood of $m$ new teams is
$$k{n-1\choose m-1}{n-1\choose m}+{n-1\choose m-1}^2$$
except for $k=0$. (When $k=0$, the number of new teams alternates each night.) The denominator of these likelihoods is $k{2n-2\choose n}+{2n-2\choose n-1}$.
For example, with 4 teams, likelihoods are $$\frac{3k+1}{15k+20},\frac{9k+9}{15k+20},\frac{3k+9}{15k+20},\frac1{15k+20}$$
The results for $3$-night teams are not so neat. With two teams, one is new; likelihoods for the age of the other team are $2/7,4/7,1/7$. With 4 teams, there are ten age possibilities, with relative likelihoods $$9, 352, 188, 740, 1848, 274, 144, 1096, 752, 36$$
- 50,853
We can use a markov chain to compute the long range probabilities.
Let A = 4 new, B = 3 new, C = 2 new, D = 1 new
The transition matrix is
$\;\;\;\; A\quad B\quad C\;\quad D$
$A\;\frac04\quad\frac04\;\quad\frac04\quad\;\frac44$
$B\;\frac04\quad\frac04\;\quad\frac34\quad\;\frac14$
$C\;\frac04\quad\frac24\;\quad\frac24\quad\;\frac04$
$D\;\frac14\quad\frac34\;\quad\frac04\quad\;\frac04$
The long range corresponding probabilities, $a,b,c,d$ can be worked out from
a = d/4,
b = c/2 + 3d/4,
c = 3b/4 + c/2,
d = a+b/4,
a+b+c+d = 1,
which yields $a = \frac1{35}$, but please check the numericals !
You can work out similarly for any other number of competitors after forming the appropriate transition matrix.
- 41,295