# Homework Help: Probability question

Tags:
1. Jan 6, 2017

### gruba



Two players, $A$ and $B$, are playing a sequence of matches of some game. In each match, one player wins (there is no draw game in any match). For winning the match, the player gets $1$ point, and for losing, $0$ points. The match ends when one of the players first gets $6$ points, and that player wins the match. At the beginning of each match, players invest the same amount of the stake.
Assume that the game is interrupted at the result $4:3$ for player $A$. If the performance of both player are approximately good, what needs to be the ratio of stakes such that the split of stakes is righteous?

Question: How to approach this problem? What methods in probability are useful?

2. Jan 6, 2017

### PeroK

I guess you have to calculate how likely it is that player A would win the match from 4-3.

3. Jan 6, 2017

### Ray Vickson

Model the system as a Markov chain on a state-space $S = \{ -6,-5, \ldots, -1,0,1, \ldots, 5 ,6\}$. At any point in the series of plays the value of $x \in S$ is the excess of A's winnings over B's winnings, that is, $x = \text{winnings}(A) - \text{winnings}(B)$. The game ends when the system reaches one of the two end-states -6 and +6. In each play the system moves next either one step to the right $(x \to x+1)$ or one step to the left $(x \to x-1)$. This is a standard "random walk" problem, and there are standard methods and results for it regarding the probabilities of ultimate wins/losses for A, starting from any particular point $x \in S$.

4. Jan 7, 2017

### gruba

Could you give a reference to the similar solved problem type if you know, or could you give detailed explanation of the problem?

5. Jan 7, 2017

6. Jan 7, 2017

### PeroK

It's not that complicated. Try to model what would happen if they continued the game. To help you get started, the next play would result in:

A score of 4-4 (with probability 1/2)
A score of 5-3 (with probability 1/2)

7. Jan 7, 2017

### Ray Vickson

Google "gamblers ruin problem" or "random walk and ruin problems".

8. Jan 7, 2017

### Ray Vickson

I should point out that the random walk method would be appropriate if we were looking at net winnings for both players, and stop the game when one of the players has net winnings reaching +6. Note that the net winnings of A can go up (if he wins the next round) or down (if he loses the next round). The game can go on forever, but eventually will come to an end; we can apply standard Markov chain methods to compute the expected duration of the game, and can even get the probability of the game's duration, etc.

However, after re-reading the original problem a bit more carefully I realize that the above interpretation is incorrect. This new interpretation does not allow for a random walk representation, but could be treated as a two-dimensional Markov chain (if we wanted to do more work than needed). Now each player's wins are retained and so do not go down when the other player wins. Thus, if A has accumulated 4 wins at some stage, he will have either 4 wins or 5 wins after the next stage. The game is over when one of the players reaches 6 wins.

In this version the game has a finite duration, because someone will win in at most 11 plays.

From some point $(n_A,n_B)$ ($n_A$ wins for A, etc) we can just go ahead and enumerate all the paths leading to a "stop" state; there are a modest number of them because on an (x,y) grid---with a move to the right if A wins or a move up if B wins---there are a limited number of different paths.

9. Jan 7, 2017

### haruspex

Another way to look at the problem is to rephrase it in the form: A needs to win at least r of the next n games. Can you see what r and n are?

10. Jan 8, 2017

### StoneTemplePython

The original post is a thinly veiled version of the Problem of Points -- a foundational problem in probability. Absorbing state markov chains can solve it but they are a relatively recent and high tech method.

This problem, in effect, created the field of probability. Fermat solved it using counting. (Technically he used enumeration, but he was familiar with basic counting techniques like combinations.) Pascal solved it by drawing a tree and doing backward induction. I recommend doing both. If you are only going to do one, do Pascal's method. Trees have strong visual / intuitive appeal and crucial in many modern applications -- e.g. in computing.

11. Jan 9, 2017

### gruba

An article https://en.wikipedia.org/wiki/Problem_of_points
says that in a game where one player needs r points to win (the one closer to winning) and the other needs s points to win, the correct division of the stakes is in the ratio of:
$$\sum_{k=0}^{s-1}{r+s-1 \choose k} : \sum_{k=s}^{r+s-1}{r+s-1 \choose k}$$
in favor of the player who is closer to winning.

This ratio is valid when draw games are included.
Setting $r=2,s=3$, we get that the split of stakes is $11:5$ in favor of the player $A$.

How could this ratio formula be used when draw games are excluded?

12. Jan 9, 2017

### Ray Vickson

After a win is declared (in the excluded-games case) you could just continue playing useless games until a total of r+s-1 games have been played. That does not alter the win/lose probabilities. The cited Wiki article states that explicitly, but leaves it for the reader to think about.

In modern language, if A needs to win $a$ and B needs to win $b$, the probability that A wins the tournament is the probability of at least $a$ A-wins in $a+b-1$ rounds, which is $P(X_A \geq a)$, with $X_A \sim \text{Binomial}(a+b-1,1/2)$.

Last edited: Jan 9, 2017