I’ve been watching episodes (via YouTube) of the British game show The Chase, which is a lot of fun for a trivia nerd like myself. In it, four players compete against a trivia champion (the “chaser”) to try to earn money. However, the way that the money is “earned” is kind of interesting in its own right, and I’ve been trying to figure out the probabilities and best strategies for it. Here’s what happens:
Each player in turn plays a game against the chaser. This game is played on a linear track with nine spaces; let’s number the spaces from 0 to 8. The chaser starts on space 0; the player has the choice of starting on space 2, 3, or 4. The player and the chaser are then asked a trivia question. If the player gets it right, they advance one space; if the chaser gets it right, they advance one space. The player and chaser effectively move at the same time. If the player gets to space 8, they are “home” and get to keep the money.[sup]1[/sup] If the chaser lands on the same space as the player, the player is “out” and gets nothing.
Now, all other things being equal, the player would want to start on space #4, except for one thing: if the player starts on space 3, they get more money if they win. If they start on space 2, they get a huge amount of money if they win. The player is told exactly how much they will win if they start at a given spot on the track, so there’s a risk/reward thing going on here. Let’s assume that the player answers questions correct with probability p, and the chaser answers questions correctly with probability q. My question is: for a given set of money values and probabilities, where should I start to make my expected winnings the greatest? Or, which is effectively the same question, for a given set of correct-answer probabilities, what is the player’s overall probability of winning the game when starting on space 2, space 3, or space 4?
[sup]1[/sup]Well, not exactly, but let’s pretend this is how it works.
They move at the same time if both players get the question right - each advances one space simultaneously. Of course, if only one of the players gets it right, only one of them moves.
I don’t think you can really calculate any probabilities unless you have an idea of how likely a contestant is to get a question right, which is, of course, what makes the game interesting.
Agreed. So let’s say that the player answers questions correct with probability p, and the chaser answers questions correctly with probability q (as stated in my original post.) Or are you saying that there’s unlikely to be a closed-form answer in terms of p and q?
I don’t think that you’re going to get a simple closed-form expression for the expected value of each starting point, but it’s pretty simple to write a program that will work it out numerically.
In brief, you’re going to be looking at a Markov chain with state space S = {(i, j) : 1 < i < 8, 1 < j < 8}. If the first coordinate represents the player’s position and the second represents the chaser’s position, it’s pretty easy to work out the transition matrix explicitly. There are absorbing states at pairs of the form (i, i) for 1 < i < 7 and (8, j) for 1 < j < 7; the first collection has a payoff of zero, and the second collection has a payoff of whatever the prize is. It’s pretty elementary to figure out the probability of absorption into each set of states, and from there you can calculate the expectation in a straightforward manner.
If no one else feels like taking a crack at this, I can write it up tonight.
Addressed in the OP:
Of course, this isn’t exactly how it works, but as a first-order approximation, it’s reasonable.
(I’m also assuming that the player’s and chaser’s answers to each question are independent of everything else, but I think that’s pretty reasonable as a simplification.)
There’s a small error here. The state space should be S = {(i, j) : 1 < i < 7, i < j < 8} by virtue of the fact that the chaser can’t be ahead of the player or reach space 8.
Yeah. The two-dimensional recurrence relation that septimus uses is what I’ve been hoping to perhaps find a closed-form solution for, but it’s not obvious to me how to do so…
Yes, with the specialization to 8. I was hoping to find a nice “closed form” (a subjective term, of course) description of the result for arbitrarily sized boards, with arbitrary starting points.
If we assume (worst case) that the chaser is omniscient (q=1), every time you miss a question the chaser gains on you. Then–with a head start at position x–you have to answer (8-x) questions correctly before missing x. It’s easy to see that if the player’s p=(8-x)/8, he has a 50-50 chance of winning.
Analyzing further, in this scenario no game will take longer than 7 questions. In fact, we can safely analyze this as a 7-question game where the player must miss fewer than x. The chance of a player answering all seven questions correctly is p^7; 6 out of 7 is 7p^6(1-p), 5 out of 7 is 21p^5(1-p)^2, and 4 out of 7 is 35p^4(1-p)^3 (the coefficients are the usual binomials numbers). To avoid writing all these expressions I’ll call these values P7, P6, P5, and P4 respectively.
So, if the player starts at 4, he/she benefits from all these possibilities, and the total probability of outrunning the omniscient chaser is P7+P6+P5+P4. When starting at three, the “4 out of 7” odds are lost, so the probability is reduced to P7+P6+P5. Starting at two is the toughest, with a probability of P7+P6.
Finally, if we assume the player and chaser are equal (p=q), the expected payouts at 2, 3, and 4 should be inversely proportional to the binomial coefficients. Thus, a payout of C when starting at 4 should be increased to (35/21)C at 3, and (35/7)C at 2.
Let P be the probability that a player wins from some fixed starting position where there’s at least one question asked. It seems obvious that dP/dp > 0 and dP/dq < 0, but I’m not sure exactly how to prove it. Further more, I have no idea how to go about computing d^2P/dpdq, which seems like an interesting quantity. Anyone have any ideas?
Are these indices correct? It seems like it should either be (2|3|4, 1) or (1|2|3, 0).
Also, what inputs are you using? I have a version in R and I’d like to double-check to make sure we get the same results.
I wrote a version in C++ to exercise my template metaprogramming skills (amusingly, it took about 3x the number of lines that his C program did), and I’m getting the same answers when I plug in the stated values for both the player and the chaser.
Excellent and interesting stuff so far. One question:
Are the probabilities you’ve calculated for p = q = {0.1, 0.2, 0.3, 0.5, 0.7}? I don’t really speak C all that well, so I’m not sure how to parse your input strings.
No, when the player is playing for the highest amount of money, he/she starts two steps ahead of the chaser.
Yes, and they were totally arbitrary settings. I verified correct results for fprob(7, 6) and fprob(7, 5) when p = q = 0.5, then “shipped it” without further ado.
Absent further testing, please don’t use the code in any life-critical applications.
It seems to me that this should follow from (given sufficiently small epsilon)
P(a,b+1) < P(a,b) < P(a+1,b)
But didn’t the great Laplace get around such matters with just Il est facile de voir?
I’m going to refine my conjecture further. Assuming that p, q \in (0, 1), I’m going to claim that for a fixed q, dP/dp goes to zero at the endpoints and is maximized when p = q. Likewise, dP/dq has the same limits at the endpoints, and is minimized when p = q. I still don’t have any intuition about the second derivatives beyond what the above implies.
This isn’t obvious to me, and Laplace died a long time ago.
Pardon me if I’m being really, really stupid here, but wouldn’t an easier way to calculate this simply be looking at the marginal value of a given position?
As in… X = M/(p/q), where M = money potentially won, p = player’s chance of getting a question right, and q being the chaser’s chance?
I know, ya’ll seem to know your math and your programming better than I, but I’m not seeing why it needs to be any more complicated.
In the case where the prize associated with each square is equal, this doesn’t distinguish between squares 2, 3, and 4, but we know that you’re better off starting on 4.