Extra Point Conversion and Delirious Ducks
Jason Shaw
1/17/2020
Extra Point Conversion (Riddler Express)
For convenience, the problem statement is given below.
The Riddler Football League (RFL) playoffs are upon us! As the coach, you’ve devised a new strategy for scoring after a touchdown. Your team will line up 2 yards away from the goal line in such a way that it could attempt either a 1-point conversion or a 2-point conversion. (Unlike other football leagues, the distance is the same for both types of conversion, and you need not announce which you’ll be attempting.) Your opponent can only properly defend against one of those two possibilities, so they’ll have to guess.
If you attempt a 1-point conversion and the other team defends against it properly, you’ll score 90 percent of the time. If they don’t defend it properly, you’ll score 100 percent of the time.
If you instead attempt a 2-point conversion and the other team defends against it properly, you’ll score 40 percent of the time. If they don’t defend it properly, you’ll score 60 percent of the time.
To tell your team which they should attempt, your team’s offensive coordinator will communicate to your team’s captain the probability with which they should attempt each. For example, the coordinator might say: “Go for 1 with a 51 percent chance, and go for 2 with a 49 percent chance.” Using a random number generator, the captain will then ultimately decide to go for 1 point or 2 points. (Naturally, every athlete in the RFL has a random number generator handy.)
However, given all the spying that occurs in the RFL these days, you can assume that the offensive coordinator’s message will also be heard by your opponent — that means the defense knows the exact probability with which you’ll attempt either conversion. Your opponent also knows the probability of you scoring in each of the four scenarios listed above.
With all that said, what strategy will maximize the average number of points you’ll score (i.e., how often should your team go for 1 or 2)? What should your opponent’s defensive strategy be? How many points will you score, on average, after each touchdown?
Solution
Let \(p_O\) be the probability the offence goes for a 1 pt conversion and \(p_D\) the probability for the defense to set up to defend a 1 pt conversion. Then \(1-p_O\) and \(1-p_D\) will be the probabilities that the offense and defense will go for/defend the 2 pt conversion.
With probability \(1*p_0*(1-p_D)\) the offense will set up for a 1 pt conversion, the defense will defend against the 2 pt conversion, and the point will be scored.
With probability \(0.9*p_O*p_D\), the offense will set up for a 1 pt conversion, the defense will defend against the 1 pt conversion, and the point will be scored.
With probability \(0.6*(1-p_O)*p_D\), the offense will set up for a 2 pt conversion, the defense will defend against the 1 pt conversion, and the 2 points will be scored.
With probability \(0.4*(1-p_O)*(1-p_D)\), the offense will set up for a 2 pt conversion, the defense will defend against the 2 pt conversion, and the 2 points will be scored.
Putting this together, we can come up with the following expected number of points scored by the offense as a function of the two variables \(p_O\) and \(p_D\). The expected value is given as \[ E(p_O, p_D) = p_O[(1-p_D)+0.9p_D]+2(1-p_O)[0.6p_D+0.4(1-p_D)], \] which simplifies to \[ E(p_O,p_D) = 0.2p_O+0.4p_D-0.5p_Op_D+0.8. \] Taking a partial derivative of this with respect to \(p_D\) will give \[ \frac{\partial E}{\partial p_D} = 0.4-0.5p_O. \] For a fixed \(p_O>0.8\), the partial derivative is negative. This means that the original function would be strictly decreasing with respect to \(p_D\), so it makes sense to set \(p_D = 1\) whenever \(p_O>0.8\).
For a fixed \(p_O<0.8\), the partial derivative is positive, meaning \(E\) is strictly increasing. Choosing \(p_D = 0\) will minimize \(E\) in this case.
If offense uses the strategy \(p_O = 0.8\), the partial derivative is zero which makes \(E\) constant for any choice of \(p_D\).
Values will be tested in a small neighborhood of \(p_O=0.8\).
E <- function(p_O, p_D){
return(0.2*p_O+0.4*p_D-0.5*p_O*p_D+0.8)
}
## For p_O = 0.85
E(0.85, 1)## [1] 0.945E(0.85,0.95)## [1] 0.94625## For p_O = 0.8
E(0.8,1)## [1] 0.96E(0.8,0.5)## [1] 0.96E(0.8,0)## [1] 0.96## For p_O = 0.75
E(0.75,0)## [1] 0.95E(0.75,0.05)## [1] 0.95125From this, we see that the strategy for the offense should be to go for a 1 pt conversion 80% of the time and a 2 pt conversion 20% of the time, taking away any kind of strategy from the defense. This results in the maximum average of 0.96 points.
The Delirious Ducks (Riddler Classic)
Again, here is the problem statement for convenience.
After a long night of frivolous quackery, two delirious ducks are having a difficult time finding each other in their pond. The pond happens to contain a 3×3 grid of rocks.
Every minute, each duck randomly swims, independently of the other duck, from one rock to a neighboring rock in the 3×3 grid — up, down, left or right, but not diagonally. So if a duck is at the middle rock, it will next swim to one of the four side rocks with probability 1/4. From a side rock, it will swim to one of the two adjacent corner rocks or back to the middle rock, each with probability 1/3. And from a corner rock, it will swim to one of the two adjacent side rocks with probability 1/2.
If the ducks both start at the middle rock, then on average, how long will it take until they’re at the same rock again? (Of course, there’s a 1/4 chance that they’ll swim in the same direction after the first minute, in which case it would only take one minute for them to be at the same rock again. But it could take much longer, if they happen to keep missing each other.)
Extra credit: What if there are three or more ducks? If they all start in the middle rock, on average, how long will it take until they are all at the same rock again?
A Simulation
Let’s label the 3x3 grid of rocks in the following way.
RockGrid <- matrix(1:9, nrow=3, byrow=TRUE)
RockGrid## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 4 5 6
## [3,] 7 8 9So, the ducks begin on rock 5 and will transition to either 2, 4, 6, or 8 with probability 1/4. In fact, if we think of each of these rocks as a state, we can see that this can be modeled with a Markov Chain.
The transition matrix for this Markov chain is the following 9x9 matrix:
DD <- matrix(c(0,1/3,0,1/3,0,0,0,0,0,
0.5,0,.5,0,.25,0,0,0,0,
0,1/3,0,0,0,1/3,0,0,0,
.5,0,0,0,.25,0,.5,0,0,
0,1/3,0,1/3,0,1/3,0,1/3,0,
0,0,.5,0,.25,0,0,0,.5,
0,0,0,1/3,0,0,0,1/3,0,
0,0,0,0,.25,0,.5,0,.5,
0,0,0,0,0,1/3,0,1/3,0), nrow=9)
DD## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [1,] 0.0000000 0.50 0.0000000 0.50 0.0000000 0.00 0.0000000 0.00
## [2,] 0.3333333 0.00 0.3333333 0.00 0.3333333 0.00 0.0000000 0.00
## [3,] 0.0000000 0.50 0.0000000 0.00 0.0000000 0.50 0.0000000 0.00
## [4,] 0.3333333 0.00 0.0000000 0.00 0.3333333 0.00 0.3333333 0.00
## [5,] 0.0000000 0.25 0.0000000 0.25 0.0000000 0.25 0.0000000 0.25
## [6,] 0.0000000 0.00 0.3333333 0.00 0.3333333 0.00 0.0000000 0.00
## [7,] 0.0000000 0.00 0.0000000 0.50 0.0000000 0.00 0.0000000 0.50
## [8,] 0.0000000 0.00 0.0000000 0.00 0.3333333 0.00 0.3333333 0.00
## [9,] 0.0000000 0.00 0.0000000 0.00 0.0000000 0.50 0.0000000 0.50
## [,9]
## [1,] 0.0000000
## [2,] 0.0000000
## [3,] 0.0000000
## [4,] 0.0000000
## [5,] 0.0000000
## [6,] 0.3333333
## [7,] 0.0000000
## [8,] 0.3333333
## [9,] 0.0000000Let’s build a function that will play one round of this simulation.
oneDDRound <- function(){
## use the matrix inside the function so we don't have to use it globally.
DD <- matrix(c(0,1/3,0,1/3,0,0,0,0,0,
0.5,0,.5,0,.25,0,0,0,0,
0,1/3,0,0,0,1/3,0,0,0,
.5,0,0,0,.25,0,.5,0,0,
0,1/3,0,1/3,0,1/3,0,1/3,0,
0,0,.5,0,.25,0,0,0,.5,
0,0,0,1/3,0,0,0,1/3,0,
0,0,0,0,.25,0,.5,0,.5,
0,0,0,0,0,1/3,0,1/3,0), nrow=9)
## Initial state of each duck is in state 5.
d1 <- 5
d2 <- 5
## We now have an initial transition.
t <- 1
## Using the 5th row of the matrix as a probability vector, take a sample of 1
## from 1:9.
d1 <- sample(1:9,1,prob=DD[d1,])
d2 <- sample(1:9,1,prob=DD[d2,])
## We do this until both of them match.
while(d1!=d2){
t <- t+1
d1 <- sample(1:9,1,prob=DD[d1,])
d2 <- sample(1:9,1,prob=DD[d2,])
}
return(t)
}
## A few rounds to see how it works.
set.seed(205)
oneDDRound()## [1] 15oneDDRound()## [1] 15oneDDRound()## [1] 4oneDDRound()## [1] 4oneDDRound()## [1] 9Now, we look at simulating this any \(N\) number of times when taking sample sizes \(n\), and return an average and a histogram.
DDSim <- function(n,N){ ## Simulate average values from samples of n, N times
T <- c() # Keeps track of mean results from sample size n
for(i in 1:N){
t <- 0 ## within sample total.
for(i in 1:n){
t <- t + oneDDRound()
}
T <- c(T,t/n)
}
hist(T) ## A histogram as a side effect
return(mean(T)) ## Output the mean of means
}
set.seed(20200117)
DDSim(1,10000)
## [1] 4.9656DDSim(10,1000)
## [1] 4.9396DDSim(500,1000)
## [1] 4.903802It looks like we’re looking for a value in the 4.9 region.
Analytical Solution
Let’s make the following observation about the ducks as they move from rock to rock: they move back and forth between the sets \(\{1,3,5,7,9\}\) and \(\{2,4,6,8\}\). Connecting these points on the grid will make the first set look like an X and the second set appear as a square rotated 45 degrees (a diamond).
Let’s observe what kind of states both ducks are in when they are inside each set. For now, forget the names of the states, and look at only the shape of the X and the diamond. In the X state, the ducks could be on opposite ends of either of the two lines that make the X, they can be both be on an end but not opposite of each other, one could be in the center and one could not, or they could both be in the same place. I will call these states XOpp, XAdj, XOIC, Same.
When they are in the diamond, they could either be on opposite sides of the diamond, on the same side of the diamond, or in the same place. I will call these states DOpp, DAdj, Same.
Similar to the simulation, we build a Markov chain that will transition from either of the six states XOpp, XAdj, XOIC, DOpp, DAdj, Same. Once they are in the Same state, we’ll build it so they remain.
XD <- matrix(c(0,0,0,2/9,1/9,0,
0,0,0,2/9,2/9,0,
0,0,0,4/9,4/9,0,
1/2,1/4,1/4,0,0,0,
1/2,1/2,1/2,0,0,0,
0,1/4,1/4,1/9,2/9,1), nrow = 6)
XD## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.0000000 0.0000000 0.0000000 0.50 0.5 0.0000000
## [2,] 0.0000000 0.0000000 0.0000000 0.25 0.5 0.2500000
## [3,] 0.0000000 0.0000000 0.0000000 0.25 0.5 0.2500000
## [4,] 0.2222222 0.2222222 0.4444444 0.00 0.0 0.1111111
## [5,] 0.1111111 0.2222222 0.4444444 0.00 0.0 0.2222222
## [6,] 0.0000000 0.0000000 0.0000000 0.00 0.0 1.0000000By using this Markov chain, we need to build the probabity vector after the first transition. By starting in the center, the ducks can either end up in DOpp with probability 1/4, DAdj with probability 1/2, or Same with probability 1/4. This will be the probability vector after first transition.
x1 <- c(0, 0, 0, 1/4, 1/2, 1/4)
x1## [1] 0.00 0.00 0.00 0.25 0.50 0.25To calculate the expected value, we will keep track of the 6th entry in the state vectors as we’ll need to subtract consecutive accumulated probabilities to get the probability of getting to the same place for the first time.
t <- 1
E <- t*x1[6]
for(t in 2:100){
E <- E + t*((x1%*%(XD%^%(t-1)))[6]-(x1%*%(XD%^%(t-2)))[6])
}
E## [1] 4.905405This answer of 4.905405 transitions (or minutes in terms of the problem statement) is correct to at least 6 decimal places.
Extra Credit
For the extra credit, we will copy the code above and alter it to fit three ducks.
oneDDDRound <- function(){
## use the matrix inside the function so we don't have to use it globally.
DD <- matrix(c(0,1/3,0,1/3,0,0,0,0,0,
0.5,0,.5,0,.25,0,0,0,0,
0,1/3,0,0,0,1/3,0,0,0,
.5,0,0,0,.25,0,.5,0,0,
0,1/3,0,1/3,0,1/3,0,1/3,0,
0,0,.5,0,.25,0,0,0,.5,
0,0,0,1/3,0,0,0,1/3,0,
0,0,0,0,.25,0,.5,0,.5,
0,0,0,0,0,1/3,0,1/3,0), nrow=9)
## Initial state of each duck is in state 5.
d1 <- 5
d2 <- 5
d3 <- 5
## We now have an initial transition.
t <- 1
## Using the 5th row of the matrix as a probability vector, take a sample of 1
## from 1:9.
d1 <- sample(1:9,1,prob=DD[d1,])
d2 <- sample(1:9,1,prob=DD[d2,])
d3 <- sample(1:9,1,prob=DD[d3,])
## We do this until both of them match.
while(!all(d1==d2,d2==d3,d1==d3)){
t <- t+1
d1 <- sample(1:9,1,prob=DD[d1,])
d2 <- sample(1:9,1,prob=DD[d2,])
d3 <- sample(1:9,1,prob=DD[d3,])
}
return(t)
}
## A few rounds to see how it works.
set.seed(205)
oneDDDRound()## [1] 3oneDDDRound()## [1] 3oneDDDRound()## [1] 38oneDDDRound()## [1] 37oneDDDRound()## [1] 19A similar simulation to above with the necessary edits:
DDDSim <- function(n,N){ ## Simulate average values from samples of n, N times
T <- c() # Keeps track of mean results from sample size n
for(i in 1:N){
t <- 0 ## within sample total.
for(i in 1:n){
t <- t + oneDDDRound()
}
T <- c(T,t/n)
}
hist(T) ## A histogram as a side effect
return(mean(T)) ## Output the mean of means
}
set.seed(20200117)
DDDSim(1,10000)
## [1] 18.4642DDDSim(10,1000)
## [1] 18.7564DDDSim(500,1000)
## [1] 18.43474We’re looking for a value close to 18.4. To solve this analytically, we can find it similarly to how we found the two duck case, but it gets quite complicated. This will involve an 11 state matrix. Once again, the three ducks can either be in the diamond set \(\{2,4,6,8\}\) or in the X set \(\{1,3,5,7,9\}\). But, in what configurations?
In the X set, they can either be * all on their own rock with one in middle and two on an edge (X1), * all on their own rock in a diagonal (X2), * all on their own rock with none in the middle (X3), * two on one corner, and one an edge corner (X4), * two on one corner, and one in the middle (X5), * two on one corner, and one on the opposite diagonal corner (X6), * two in the middle and one in a corner (X7), or * all on the same rock.
In the diamond set, they can either be * all on their own individual rock (D1), * two on one rock, and another on a rock opposite (D2), * two on one rock, and another on a rock adjacent (D3), or * all on the same rock.
If we don’t count being on the same rock as two states, this is an eleven state Markov chain (with the exception of the first transition from the same rock in the middle). The states below are put in the order of X1-X7, D1-D3, Same.
XD3 <- matrix(c(rep(0,7),3/8,3/16,3/8,1/16,
rep(0,7),1/2,1/4,1/4,0,
rep(0,7),1/2,1/4,1/4,0,
rep(0,7),1/4,1/8,1/2,1/8,
rep(0,7),1/4,1/8,1/2,1/8,
rep(0,7),1/2,1/4,1/4,0,
rep(0,7),3/8,3/8,3/16,1/16,
2/9,4/27,4/27,2/27,2/27,2/27,2/9,0,0,0,1/27,
2/9,4/27,4/27,2/27,2/27,2/27,2/9,0,0,0,1/27,
2/9,2/27,2/27,4/27,4/27,1/27,2/9,0,0,0,2/27,
rep(0,10),1), nrow=11, byrow=TRUE)
XD3## [,1] [,2] [,3] [,4] [,5] [,6]
## [1,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [2,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [3,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [4,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [5,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [6,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [7,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [8,] 0.2222222 0.14814815 0.14814815 0.07407407 0.07407407 0.07407407
## [9,] 0.2222222 0.14814815 0.14814815 0.07407407 0.07407407 0.07407407
## [10,] 0.2222222 0.07407407 0.07407407 0.14814815 0.14814815 0.03703704
## [11,] 0.0000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000
## [,7] [,8] [,9] [,10] [,11]
## [1,] 0.0000000 0.375 0.1875 0.3750 0.06250000
## [2,] 0.0000000 0.500 0.2500 0.2500 0.00000000
## [3,] 0.0000000 0.500 0.2500 0.2500 0.00000000
## [4,] 0.0000000 0.250 0.1250 0.5000 0.12500000
## [5,] 0.0000000 0.250 0.1250 0.5000 0.12500000
## [6,] 0.0000000 0.500 0.2500 0.2500 0.00000000
## [7,] 0.0000000 0.375 0.3750 0.1875 0.06250000
## [8,] 0.2222222 0.000 0.0000 0.0000 0.03703704
## [9,] 0.2222222 0.000 0.0000 0.0000 0.03703704
## [10,] 0.2222222 0.000 0.0000 0.0000 0.07407407
## [11,] 0.0000000 0.000 0.0000 0.0000 1.00000000This is a Markov chain that models everything after the initial state of all ducks in middle. The ducks can transition from the middle rock to any of four rocks on the diamond set in 64 different ways. They can all be on their own rock in 24 different ways, two can be on one and one can be on the opposite side in 12 different ways, two can be on one and one can be adjacent in 24 different ways, and they can all be on the same rock in 4 different ways.
This produces the following first state probability vector.
x1 = c(rep(0,7), 3/8, 3/16, 3/8, 1/16)
x1## [1] 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.3750 0.1875 0.3750
## [11] 0.0625Now, similar to before, we keep track of the probability of being on the same rock on a particular transition given that ducks have not been on the same rock yet.
t <- 1
E <- t*x1[11]
for(t in 2:350){
E <- E + t*((x1%*%(XD3%^%(t-1)))[11]-(x1%*%(XD3%^%(t-2)))[11])
}
E## [1] 18.86607As this is consistent with the simulated values, and increasing 350 does not change the answer, we have an answer correct to 6 decimal places as long as I haven’t missed anything.