2

I'm working on the following problem: "A boy and his father are playing chess, and the game is set to be finished when one of them reaches $v$ victories. In each match, the boy has a $p$ probability of winning, and his father $q$. If $p+q<1$, calculate the probability of the boy's victory" I guess $p+q<1$ basically means that stalemates are possible. I was trying to use Markov chains but having to reach $v$ victories in order to win the game is causing me some trouble. Thank u so much if you read the whole thing :)

Yauset Cabrera
  • 185
  • 4
    Backwards induction is probably best. Label a state as $(i,j)$ if the son needs $i$ more victories and the father $j$. Transitions are easy to sort out. Note that the stalemate thing doesn't really matter, as those have no impact on the ultimate victor. just replace the probabilities by $\frac p{p+q}, \frac q{p+q}$. – lulu Jun 30 '22 at 17:34
  • @lulu: Father and son are playing a straight first to seven wins type of match, so why would we need backwards induction ? – true blue anil Jun 30 '22 at 20:22
  • @trueblueanil Where did $7$ come from? But, sure. You can do it for any $v$. And, as you say, you can do it directly. – lulu Jun 30 '22 at 22:12

1 Answers1

2

To simplify notation, let me call the initial probabilities $p' \; and \;q'$ for boy and father, $p'+q' <1$, and ignore draws (which don't matter)

P(boy wins a game) $=p=\frac{p'}{p'+q'}$
P(father wins a game) $=q= \frac{q'}{p'+q'}$
but now $p+q=1$

For concreteness, let $v = 7,$ say

Since whoever wins $7$ games wins, it is like a tennis tournament where first to $7$ wins gets the prize, and no recursion is needed

You need a maximum of $13$ games to decide who wins.

The easiest way to compute this is to allow $13$ games to played even if the match has already been decided, but restricting the loser to a maximum of $6$ wins.

Thus P(boy wins) $= \binom{13}0q^0p^{13} + \binom{13}1q^1p^{12} + \binom{13}2q^2p^{11}+ ... +\binom{13}6q^6p^7$

Restoring for the v wins needed, and making the formula compact,

$$P(boy \;wins)=\large{ \sum_{i=0}^{v-1}}\binom{2v-1}{i}q^ip^{2v-1-i}$$

If this seems counterintuitive, look here where all doubts about the concept have been cleared in detail.

NOTE:
Had the question been that you need to win $v$ more games than your opponent, then it would be a Markov process.

true blue anil
  • 41,295
  • Interesting formulation , aside form intuition I found an easy rigorous proof for such formulation here . BTW above it should be $2v-1$ not $2v+1$ which's the max no. of games to decide winner ? – C.C. Jul 01 '22 at 12:09
  • 1
    @C.C: Thanks, typo corrected. The third of the "intuitive" arguments given in my linked answer hints at how a mathematical proof could be written more formally. – true blue anil Jul 01 '22 at 12:27