In this question this game is presented:

Suppose in an independent game which has 2 players, player 1 and player 2, the probability of player 1 to win each game is r. To be the overall winner of the game, one of the players needs to win 2 more games than the other.

Now, instead of asking for the probability of player 1 to win, I want to know what is the expected number played to end the game?

  • $\begingroup$ Since there are already answers to your earlier question, it is good to ask a new one instead of retroactively changing the old one. But please make your new question self-contained so it contains all the necessary information rather than just referring back to the earlier one. (It is good also to link to the old question, but it should not be necessary to follow the link in order to figure out what you're asking). $\endgroup$ – hmakholm left over Monica Oct 9 '12 at 16:54

Let $a$ be the expected number of additional games that need to be played if the two players are tied in wins. In particular, $a$ is our required number, since the players start off tied.

Let $b$ be the expected number of additional games if Player $1$ is leading by $1$. And let $c$ be expected number of additional games if Player $1$ is trailing by $1$. We have the equations $$\begin{align}a&=1+rb+(1-r)c,\\ b&=1+(1-r)a, \\ c&=1+ra.\end{align}$$

Use the above system of linear equations to find $a$.

Remarks: $1.$ To justify the first equation, note that for sure we will be playing one more game. That's the $1$ in the equation. And we will not be finished. With probability $r$ our expected number of games beyond that will be $b$, and with probability $1-r$ our expected number of games beyond that will be $c$. That yields the first equation. It may be prettier and clearer to write the equation as $a=r(1+b)+(1-r)(1+c)$.

The justifications for the other two equations are similar. Again, one might like to write the second equation as $b=r(1)+(1-r)(a+1)$, and do a similar rewrite of the third equation.

$2.$ As pointed out by Marc van Leeuwen, the argument tacitly assumes that the expectations exist. To show that they do is not difficult. Whatever $r$ is, the probability of two opposite results in a row is $2r(1-r)$, which is $\le 1/2$. So the probability that a game length $2n$ or more is $\le (1/2)^n$, and therefore the expected length is finite.

$3.$ We used a strategy broadly similar to the one used in the related question about the probability that Player $1$ wins. This kind of strategy tends to work more widely for expectations than for probabilities, because of the linearity of expectation.

  • 1
    $\begingroup$ I think this reasoning needs in addition an argument that the expected number is finite. If there were a positive probability that the game goes on forever (as would be the case for certain variations of the termination clause) then all expectations would be infinite, which possibility the given equations do not contradict. $\endgroup$ – Marc van Leeuwen Oct 9 '12 at 17:30
  • $\begingroup$ @MarcvanLeeuwen: You are of course absolutely right. T thought it was better not to mention it, but will add a remark. $\endgroup$ – André Nicolas Oct 9 '12 at 17:37
  • $\begingroup$ well, i think this relation is really interesting, we don't even need to set up any random variable and get the expected number. $\endgroup$ – Mathematics Oct 9 '12 at 17:54
  • $\begingroup$ @Mathematics: Random sequence approaches are more broadly useful. $\endgroup$ – André Nicolas Oct 9 '12 at 18:04
  • $\begingroup$ What do you mean by random sequence approaches? $\endgroup$ – Mathematics Oct 10 '12 at 4:37

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.