Fencing Relay
Probability ; Difficulty: medium
A game sequence probability puzzle from The Riddler: The Fencing Relay
This week’s Riddler Classic has an intuitive answer, tedious solution and highlights the value of high performers on a team. Here it is:
You are the coach at Riddler Fencing Academy, where your three students are squaring off against a neighboring squad. Each of your students has a different probability of winning any given point in a match. The strongest fencer has a 75 percent chance of winning each point. The weakest has only a 25 percent chance of winning each point. The remaining fencer has a 50 percent probability of winning each point.
The match will be a relay. First, one of your students will face off against an opponent. As soon as one of them reaches a score of 15, they are both swapped out. Then, a different student of yours faces a different opponent, continuing from wherever the score left off. When one team reaches 30 (not necessarily from the same team that first reached 15), both fencers are swapped out. The remaining two fencers continue the relay until one team reaches 45 points.
As the coach, you can choose the order in which your three students occupy the three positions in the relay: going first, second or third. How will you order them? And then what will be your team’s chances of winning the relay?
*spoiler alert* solution and answer follow below
Getting right into it
If your intuition suggests putting the best player at the end, then you are spot on. The reasoning here is straightforward. Just consider the extreme case where your best player is sure to win every round. Put this person up first and the best they can do is give you a 15 point advantage over the opponents, which is great but clearly not unassailable. Put them in round 3 and no matter how poorly your team does in the first two rounds, your team wins! This same reasoning holds when you have less than the perfect player, but someone better than the others. This much is easily intuited. Calculating the probability is unfortunately tiresome and comes down to enumerating the possible outcomes at the ends of each of the three rounds. I spent quite a bit of time trying to reason through urns with balls and colors and such to see if this could be framed in a more intuitive way, making the probability calculations easier, but drew a blank. Perhaps you’ve hit upon a simple framing. If so, let me know in the comments.
Probability Calculations:
Each individual match in a round is a Bernoulli trial with all matches in a round having the same probability of success \(p\) for your team. But the probabilities change with the players at the end of each round making the calculations more complicated than otherwise.
At the end of round 1, the scores are either \((i,15) \) if your team loses or \((15,i) \) if your team wins: \( 0 \le i \le 14 \) . Similarly, at the end of round two they are either \((j,30)\) or \((30,j)\). But the allowed range for \(j\) though depends on how round 1 ended. If your team won round 1: then \( 15 \le j \le 29\) in the case of a second round loss and \( i \le j \le 29\) for a second round win. You’d reason similarly for the case when your team round lost round 1. Each of these transitions has a different probability. This is much easier to understand, say in the simplified case of 2 rounds with a switchout occurring at 2 points and victory at 4. (See fig above: each path from the start at the top to the end at the bottom has a different probability)
The probability for each single round transition is fairly easily calculated. Consider round starting scores \((s_1 , s_2)\) and round end scores of \((e_1, e_2 )\) . Yours is team 1 and the opponent team 2.
Let:
\begin{align*}
d_1 &= (e_1 – s_1) \qquad \textit{score change for your team} \\
d_2 &= (e_2 – e_1) \qquad \textit{score change for the opposing team} \\
n &= (d_1) +(d_2) \quad \textit{the total no. of matches played that round} \\
l_d &= d_1 \qquad \textit{ if } e_1 < e_2 \\
&= d_2 \qquad \textit{ otherwise. i.e. } l_d \textit{ is the points scored in the round by the loser} \\
\end{align*}
Assuming your team wins i.e. \(e_1 > e_2 \) , this outcome requires \(d_1 -1 \) successes in the first \((n-1)\) Bernoulli trials and then a success at the last one. This has a probability:
\begin{align*}
R_n &= \binom{n-1}{d_1-1}p^{d_1-1}(1-p)^{d_2}p \\ \\
&= \binom{n-1}{d_1-1}p^{d_1}(1-p)^{d_2}
\end{align*}
OR if your team loses
\begin{align*}
&= \binom{n-1}{d_2-1}p^{d_1}(1-p)^{d_2}
\end{align*}
OR combining:
\begin{align*}
R_n &= \binom{n-1}{l_d}p^{d_1}(1-p)^{d_2} \\
\end{align*}
(This can also be obtained starting with the Negative Binomial Distribution)
Now it’s just a question of applying the formula for all the possible round transition scenarios for a given sequence of player probability outcomes \((p_1, p_2, p_3) \) and multiplying them since the feasible transitions are all independent. i.e.
\[\sum R_1R_2R_3 \quad \textit{where the sum is over all feasible transitions} \]
It’s instructive to run a simple version on a spreadsheet. This Google sheet enumerates this with targets of 2, 4 and finally 6 for a three round relay.
This can be mind-numbing on a spreadsheet for the problem Zach set for us this week; but mind numbing and time consuming is where computers shine.
Code to the rescue
You can find my Python code to run through the different scenarios below and also here. If you are able to run Python, you can play with scenarios and outcomes by varying the target score each round, probabilities etc.
The end result aligns with our intuition. It’s best to send your weakest first, and best fencer last for a win probability of 93.17%. Going in reverse is the worst possible option: your win probability drops to a pitiful 6.83%. Quite the change of fortune!
Since it’s my computer crunching the numbers, I also threw in a few other quantities for good measure: such as the number of expected matches in each round and the probabilities of winning the prior rounds: all summarized below.
| Fencer Sequence | (0.25, 0.50, 0.75) | (0.50, 0.25, 0.75) | (0.25, 0.75, 0.50) | (0.75, 0.25, 0.50) | (0.50, 0.75, 0.25) | (0.75, 0.50, 0.25) |
| Prob winning R1 | 0.18% | 50.00% | 0.18% | 99.82% | 50.00% | 99.82% |
| Prob winning R2 | 6.85% | 0.63% | 95.13% | 4.87% | 99.37% | 93.15% |
| Prob winning Relay | 93.17% | 92.49% | 82.61% | 17.39% | 7.51% | 6.83% |
| Best fencer expected match count | 33.12 | 34.74 | 33.05 | 19.99 | 22.86 | 19.99 |
| Exp. R1 match count | 19.99 | 25.67 | 19.99 | 19.99 | 25.67 | 19.99 |
| Exp. R2 match count | 29.60 | 22.86 | 33.05 | 33.05 | 22.86 | 29.60 |
| Exp. R3 match count | 33.12 | 34.74 | 28.99 | 28.99 | 34.74 | 33.12 |
| Exp. total matches | 82.71 | 83.27 | 82.04 | 82.04 | 83.27 | 82.71 |
Code used to calculate required probabilities:
from math import comb
r1_target = 15
r2_target = 30
r3_target = 45
prob_seq = [0.25, 0.5, 0.75] # chosen sequence of probabilities
#prob_seq = [1, 1, 1]
win_probabilty = 0 # final win prob initialization
loss_probability = 0 # final loss prob initialization
round_1_win_prob = 0
round_1_loss_prob = 0
round_2_win_prob = 0
round_2_loss_prob = 0
exp_matches_p1 = 0
exp_matches_p2 = 0
exp_matches_p3 = 0
# function to get probabilties given start (s1, s2) and end states (e1,e2) of your team (1) and opponent (2) and your probability p of winning
def get_prob(s1,e1,s2,e2,p):
d1 = e1 - s1
d2 = e2 - s2
n = d1 + d2
if e1 < e2:
ld = e1 - s1
else:
ld = e2 - s2
q = 1 - p
# print(s1,e1,s2,e2)
prob = comb(n-1,ld)*(p**d1)*(q**d2)
return prob
def round1():
global round_1_win_prob
global round_1_loss_prob
global exp_matches_p1
r1_counter = 0
while r1_counter <=1:
st1 = 0
st2 = 0
if r1_counter == 0:
et2 = r1_target
et1 = 0
while et1 < r1_target:
answer_prob = get_prob(st1,et1,st2,et2,prob_seq[0])
round_1_loss_prob += answer_prob
exp_matches_p1 += answer_prob*(et1-st1 + et2 - st2)
# print("from first", st1,st2,et1,et2, answer_prob)
round2(answer_prob,et1,et2)
et1 += 1
else:
et1 = r1_target
et2 = 0
while et2 < r1_target:
answer_prob = get_prob(st1,et1,st2,et2,prob_seq[0])
round_1_win_prob += answer_prob
exp_matches_p1 += answer_prob*(et1-st1 + et2 - st2)
# print("from second", st1,st2,et1,et2, answer_prob)
round2(answer_prob,et1,et2)
et2 += 1
r1_counter += 1
return()
def round2(prob,e1i,e2i):
global round_2_win_prob
global round_2_loss_prob
global exp_matches_p2
r2_counter = 0
while r2_counter <=1:
s1 = e1i
s2 = e2i
if r2_counter == 0:
e1 = s1
e2 = r2_target
while e1 < r2_target:
answer_prob = prob*get_prob(s1,e1,s2,e2,prob_seq[1])
round_2_loss_prob += answer_prob
exp_matches_p2 += answer_prob*(e1-s1 + e2 - s2)
# print(e1,e2, answer_prob)
round3(answer_prob,e1,e2)
e1 += 1
else:
e1 = r2_target
e2 = s2
while e2 < r2_target:
answer_prob = prob*get_prob(s1,e1,s2,e2,prob_seq[1])
round_2_win_prob += answer_prob
exp_matches_p2 += answer_prob*(e1-s1 + e2 - s2)
round3(answer_prob,e1, e2)
e2 +=1
r2_counter +=1
def round3(prob, e1i, e2i):
global win_probabilty
global loss_probability
global exp_matches_p3
r3_counter = 0
while r3_counter <=1:
s1 = e1i
s2 = e2i
if r3_counter == 0:
e2 = r3_target
e1 = s1
while e1 < r3_target:
loss_probability += prob*get_prob(s1,e1,s2,e2,prob_seq[2])
exp_matches_p3 += prob*get_prob(s1,e1,s2,e2,prob_seq[2])*(e1-s1+e2-s2)
e1 += 1
else:
e1 = r3_target
e2 = s2
while e2 < r3_target:
win_probabilty += prob*get_prob(s1,e1,s2,e2,prob_seq[2])
exp_matches_p3 += prob*get_prob(s1,e1,s2,e2,prob_seq[2])*(e1-s1+e2-s2)
# print("final", e1,e2, win_probabilty)
e2 += 1
r3_counter +=1
round1()
print(prob_seq)
print("Round 1 Win Probability:", round_1_win_prob, "Round 1 Loss Probability:", round_1_loss_prob, "Total: ", round_1_win_prob + round_1_loss_prob)
print("Round 2 Win Probability:", round_2_win_prob, "Round 2 Loss Probability:", round_2_loss_prob, "Total: ", round_2_win_prob + round_2_loss_prob)
print("Final Win Probability:", win_probabilty, "Final Loss Probability:", loss_probability, "Total: ", win_probabilty + loss_probability)
print("Expected matches in round 1: ", exp_matches_p1)
print("Expected matches in round 2: ", exp_matches_p2)
print("Expected matches in round 3: ", exp_matches_p3)
print("Expected total matches: ", exp_matches_p3 + exp_matches_p2 + exp_matches_p1)
#-----------
Observations:
The main insight from this math exercise is the outsize value that a single high performer (star) brings to a team and the benefits of giving them more time/opportunities:
- Our basic assumption that we do better when we allow our best fencer the opportunity to play the most games is generally validated. The table above shows a row for your best fencer match count right below probability of winning the relay.
- If your first fencer was a complete deadbeat sure to lose every game \((p_1 = 0 )\), you will still win the relay with probability 86.3% ! In fact, if you had two complete novices (zero win probability), your star fencer still gets you close to a 50% win rate for the relay (48%), same as going with three “average” fencers!
- The law of large numbers starts helping more and more as the round target scores are increased (while keeping them evenly spaced). If we went from 15,30,45 to 20,40,60, the relay win probability increases to ~96% and with 30,60,90, it increases to over 98%, and with 40,80,120 to over 99%. Conversely, the relay win probability decreases as round targets are decreased. At 5,10,15 it’s ~80% and drops to 66% at 1,2,3.
- Superstar effect: Based on the above, given the match repetitions, one better than average fencer more than balances out a mediocre one—a better option than having three “average” fencers. Kinda like how Lionel Messi carried FC Barcelona through La Liga with a dud team around him the last few years (had to throw that in 😀)
- Other fencer probabilities being the same, if your best fencer was at 0.6, your team wins 40% of the time; number jumps by half to 60% with a modest increase (8%) in win probability to 0.65; and then again by more than half to 93.17% when best fencer probability jumps to 0.75! This though simplistic helps explain in one way, why (sports) people who are a little better than their colleagues end up commanding outsize salaries.
- In the best sequence case, the probability of winning Round 1 , Round 2 are relatively small before the best fencer really swings the relay in your favor.
- The expected number of total matches remarkably shows little variance across sequences!
- The win probability and expected match count nos. are reversed when going (worst, average and best) to (best, average, worst) as you would expect since going with 0.25/0.75 flips to 0.75/0.25 for the opponent.