6
$\begingroup$

This is probably a fairly easy question, but I wasn't able to come up with a concrete answer. Let's pretend my friend and I are playing a trivia game. The rules of the game are each player is asked trivia questions until they answer one incorrectly at which point the other player gets the same opportunity. At any point when 1 player has answered 20 questions (20 questions total they do not have to be 20 in a row), that player is declared the winner. Now I answer trivia questions correctly about 70% of the time, but my friend is much smarter and answers them correctly about 85% of the time. How often will I win this trivia game?

The only avenue I've approached so far is thinking well the chance of me getting all 20 questions in a row is (.7)^20 which is .080%~ and his chance is (.85)^20 which is 3.876%~ which means he is 48x more likely to answer them all, which games him like a 98% chance of being the winner if the game had ended in 1 round. But I'm not sure if this stat would extend to say that is his chance of winning in the more likely situations where we miss a few questions. Can anyone help if I'm on the right track, or how to correctly approach this (it's not homework, I'm actually curious what my odds of beating my friend are =P).

$\endgroup$
  • 1
    $\begingroup$ Who goes first (it matters!)? Must you answer 20 in a row each attempt, or do you only have to get to 20 (e.g. if you answer 17 correct before a wrong answer then your opponent answers 12 correct and then one wrong, play passes back to you -- do you now need 20 or 3)? Can you clarify what you mean by "situations where we miss a few questions"? $\endgroup$ – Glen_b -Reinstate Monica Jan 10 '15 at 2:09
  • $\begingroup$ We'll say I go first, to give me a better chance. However I guess ideally I would like the stats of him winning when he goes first avg'ed with the stats of me going first, assuming it's half and half $\endgroup$ – Kevin DiTraglia Jan 10 '15 at 2:10
  • $\begingroup$ I wrote "situations where we miss a few questions" meaning I think I correctly calculated the odds of each player winning on their first round, but I've ignored all the cases of the game where neither player gets all 20 on the first round, I wasn't sure if that statistic correctly models the game by ignoring those cases $\endgroup$ – Kevin DiTraglia Jan 10 '15 at 2:16
  • 1
    $\begingroup$ Ah. It doesn't work the same when the play can extend over multiple rounds; that should improve the chances of the better player still further. $\endgroup$ – Glen_b -Reinstate Monica Jan 10 '15 at 2:26
  • $\begingroup$ I assumed that, but wasn't sure how to approach the problem $\endgroup$ – Kevin DiTraglia Jan 10 '15 at 2:26
5
$\begingroup$

This question generalizes the famous Problem of Points whose consideration by Blaise Pascal and Pierre Fermat in the summer of 1654 is generally credited as the beginning of probability theory. The Problem of Points itself has been traced back to problems of insurance raised under 13th century (CE) Islamic contract law. It concerns the situation where each play has equal chances of $0.5$ to win.

Recursion is the answer--but it requires a nice trick to work. With you to start, your chances are about $12.4\%$, but if you go second they drop to $7.6\%$. An analysis and working code follow. The analysis is similar to that proposed by Fermat.


Fix $p=0.7$ and $q=0.85$. Let $f(m,n)$ be the chance you will win the game when you need $m$ questions to win, your opponent needs $n$, and it's your turn. Similarly, let $g(n,m)$ (notice the reversal of arguments!) be the chance your opponent will win when she needs $n$ questions to win, you need $m$, and it is her turn.

Obviously $f(0,n) = g(0,m) = 1$ whenever $n\gt 0$ and $m\gt 0$.

On your turn to play, either

  • With probability $p$ you give a correct answer. It is still your turn and your chances of winning have become $f(m-1,n)$.

  • With probability $1-p$ your answer is wrong. It is now your opponent's turn. Her chances of winning are $g(n,m)$, so your chances of winning are $1-g(n,m)$.

Therefore

$$f(m,n) = p f(m-1,n) + (1-p)(1 - g(n,m)).$$

There is a comparable relation for $g$,

$$g(n,m) = q g(n-1,m) + (1-q)(1 - f(m,n)).$$

Unfortunately, these relations do not suffice for a recursive solution. The problem is that the $g(n,m)$ at the end will be expressed in terms of $g(n-1,m)$ and $f(m,n)$--but that brings us right back where we were before.

The solution is to replace $g(n,m)$ in the preceding equation with its equivalent:

$$\eqalign{ f(m,n) &= p f(m-1,n) + (1-p)(1 - \color{blue}{g(n,m)}) \\ &= p f(m-1,n) + (1-p)(1 - (\color{blue}{q g(n-1,m) + (1-q)(1 - f(m,n))})) . }$$

Isolating $f(m,n)$ yields

$$(1 - (1-p)(1-q))f(m,n) = p f(m-1,n) + q(1-p)\left(1 - g(n-1,m)\right).$$

Similarly

$$(1 - (1-p)(1-q))g(n,m) = q g(n-1,m) + p(1-q)\left(1 - f(m-1,n)\right).$$

Each lets us solve for $f$ or $g$ in terms of values of the other where $m+n$ has decreased by $1$. This will assuredly terminate with one of $m$ or $n$ equal to $0$ within $m+n-1$ moves. The algorithm, implemented as a dynamic program, requires $O(mn)$ time and space, making it practicable for $mn \lt 10^6$, more or less (where it will start taking around a minute in R or Mathematica, for instance).

With $m=n=20$, $p=0.7$, and $q=0.85$, we easily find

$$f(20,20) \approx 0.1238327668,\ g(20,20) \approx 0.9238111399.$$


The following is working R code.

f <- function(a, b, p, q, F, G) {
  if (missing(F)) F <- matrix(NA, a+1, b+1)
  if (missing(G)) G <- matrix(NA, b+1, a+1)
  F[1, ] <- G[1, ] <- 1

  d <- 1 - (1-p)*(1-q)
  pp <- p / d; pq <- (1-p)*q / d
  qq <- q / d; qp <- (1-q)*p / d

  f <- function(m, n) {
    x <- F[m+1, n+1]
    if (is.na(x)) F[m+1, n+1] <<- x <- pp * f(m-1, n) + pq * (1 - g(n-1, m))
    return (x)
  }
  g <- function(m, n) {
    x <- G[m+1, n+1]
    if (is.na(x)) G[m+1, n+1] <<- x <- qq * g(m-1, n) + qp * (1 - f(n-1, m))
    return (x)
  }
  return (list(Value=f(a, b), F=F, G=G, a=a, b=b)) 
}

m <- n <- 20
p <- 0.70; q <- 0.85
x <- f(m, n, p, q)
y <- f(n, m, q, p, x$G, x$F) # Don't recalculate the stored arrays

cat("Your chances of winning (if you start) are", 100*x$Value, "%\n")
    cat("If you do not start they are", 100*(1 - y$Value), "%\n")
$\endgroup$
  • 1
    $\begingroup$ This is why I love stackexchange, thank you very much for the very detailed / informative answer! $\endgroup$ – Kevin DiTraglia Jan 10 '15 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.