# If a player is 50% as good as I am at a game, how many games will it be before she finally wins one game?

This is a real life problem. I play Foosball with my colleague who hasn't beaten me so far. I have won 18 in a row. She is about 50% as good as I am (the average margin of victory is 10-5 for me). Mathematically speaking, how many games should it take before she finally wins a game for the first time?

-
The average margin of victory isn't enough information. For an arbitrary average margin of victory in your favor, your colleague could still beat you most of the time (she might win by small margins most of the time and you might win by extremely large margins some of the time). The relevant information is the actual probability that you win a game, which you can compute using more information, e.g. the probability that each of you scores a point in a given round and the number of rounds (assuming that this probability is constant and that the rounds are independent...). –  Qiaochu Yuan Aug 1 '12 at 19:11
@QiaochuYuan, maybe I am incorrect in my calculation of the probability, but in all of the 18 games so far, her max score was 8, where I won 10-8. Her scores are always in the range from 10-0 to 10-8 but more towards 10-5. I have always won so far. –  CodeBlue Aug 1 '12 at 19:14
That is not enough information. (It could be that she will never score more than $8$ points and you will never score less than $10$ points, so you will always win.) Anyway, if you can compute in some way the probability $p$ that she wins a game, then the expected number of games needed for her to win a game is $\frac{1}{p}$. –  Qiaochu Yuan Aug 1 '12 at 19:15
Well, there is always the experimental method (playing until she wins). –  Qiaochu Yuan Aug 1 '12 at 19:17
Be kind, and let her win sometimes, so she gets some pleasure to play against you :) –  Xoff Aug 1 '12 at 20:35

A reasonable model for such a game is that each goal goes to you with probability $p$ and to her with probability $1-p$. We can calculate $p$ from the average number of goals scored against $10$, and then calculate the fraction of games won by each player from $p$.

The probability that she scores $k$ goals before you score your $10$th is $\binom{9+k}9p^{10}(1-p)^k$, so her average number of goals is

$$\sum_{k=0}^\infty\binom{9+k}9p^{10}(1-p)^kk=10\frac{1-p}p\;.$$

Since you say that this is $5$, we get $10(1-p)=5p$ and thus $p=\frac23$. The probability that you get $10$ goals before she does is

$$\sum_{k=0}^9\binom{9+k}9\left(\frac23\right)^{10}\left(\frac13\right)^k=\frac{1086986240}{1162261467}\approx0.9352\;,$$

so her chance of winning a game should be about $7\%$, and she should win about one game out of $1/(1-0.9352)\approx15$ games – so you winning $18$ in a row isn't out of the ordinary.

-
So sooner or later she is gonna win one! –  CodeBlue Aug 1 '12 at 19:56
@CodeBlue: That is always true, as long as her chances of scoring are non-zero and your chances of scoring are not 100% –  BlueRaja - Danny Pflughoeft Aug 2 '12 at 0:51

Here's one plausible model: each new point (independent of past history) has probability $2/3$ of being scored by you and $1/3$ of being scored by her. The game ends, I assume, when one player has $10$ points. The probability that she wins by a score of $10$ to $x$, i.e. that of the first $9+x$ points she scores exactly $9$ and then she wins the last point, is ${{9+x} \choose 9} (1/3)^{10} (2/3)^x$. The total probability that she wins the game is then $\displaystyle p = \sum_{x=0}^9 {{9+x} \choose 9} 2^x/3^{10+x} = \frac{75275227}{1162261467} \approx 0.0648$. The expected number of games until she wins is $1/p \approx 15.44$.

-

A simple model treats each goal as independent and assigns fixed probabilities to its outcome. Under this model, you would like to know how frequently a player whose probability of scoring is $p$ reaches $10$ points before his opponent (whose probability of scoring is $1-p$). The probability of reaching the score of $m$ to $n$ (after $m+n$ goals) is then $$P_{m,n}={{m+n}\choose{m}}p^{m}\left(1-p\right)^{n}=\frac{(m+n)!p^{m}\left(1-p\right)^{n}}{m!n!}.$$ The winning goal will be scored, with probability $p$, when the score is $9$ to $n$ for some $n\le 9$, so the probability of winning is $$P(p)=p\sum_{n=0}^{9}P_{9,n}=\sum_{n=0}^{9}\frac{(9+n)!p^{10}\left(1-p\right)^{n}}{9!n!}.$$ Based on your observations, your opponent's scoring probability is about $p=1/3$. So her probability of winning is $$P(1/3)=\sum_{n=0}^{9}\frac{(9+n)!\left(\frac{1}{3}\right)^{10}\left(\frac{2}{3}\right)^{n}}{9!n!}=0.064766...=\frac{1}{15.440...},$$ and you should expect her to win about one of every $15$ games. This analysis assumes that you can win by a single point... if you play until someone wins by two points, then the better player (you) should have a slightly greater advantage that he otherwise would, and the worse player should win slightly less often.

-

How to convert scores into wins depends a lot on the details of the game; it is not at all the same for all games. In games where the scores vary a lot, a player who scores on average much less frequently can win with a relatively short lucky run.

It has been empirically observed, for example, that one can predict a professional baseball team's win-loss ratio for a season quite accurately by calulating:

$$s^2\over s^2+a^2$$

where $s$ is their runs scored in the season and $a$ is the runs scored by their opponents. But in basketball, where scores are higher, the exponent 2 must be replaced by something more like 14.

One can adopt a model in which:

• Each point is won at random, with your friend winning $\frac13$ of the points and you winning $\frac23$ of the points; over the long run you will score twice as many points as your friend.
• A game goes to the first player to take 10 points. (Is that correct?)

It's not hard to calculate the chances that each player wins in such a model. I'll do it for a three-point game instead of a 10-point game:

$$\begin{matrix} 1 & ?& ?& ?\\ ? & ?& ?& ?\\ ? & ?& ?& ?\\ ? & ?& ?& ? \end{matrix}$$

Here the entry in the $i$ row and $j$ column $M(i,j)$ is the probability of reaching a game state in which you have $i$ points and your friend has $j$ points. All games begin in the $(0,0)$ state, so that has a probability of 1. Each other state $M(i,j)$ can be assigned the probability $\frac23 M(i-1,j) + \frac13 M(i, j-1)$, except that the game ends at 3 points, so $M(3,2)$ for example is $\frac23 M(2,2)$, not $\frac23 M(2,2) + \frac13 M(3,1)$, since if the game reached the $(3,1)$ state it would be over.

We can easily go through the matrix one entry at a time, filling in the probabilities:

$$\begin{matrix} 1 & \frac13 & ?& ?\\ \frac23 & ? & ? & ? \\ ? & ?& ?& ?\\ ? & ?& ?& ? \end{matrix}$$

$$\begin{matrix} 1 & \frac13 & \frac19 & ?\\ \frac23 & \frac49 & ? & ? \\ \frac49 & ?& ?& ?\\ ? & ?& ?& ? \end{matrix}$$

$$\begin{matrix} 1 & \frac13 & \frac19 & \frac1{27}\\ \frac23 & \frac49 & \frac6{27} & \frac6{81} \\ \frac49 & \frac{12}{27}& \frac{24}{81}& \frac{24}{243}\\ \frac8{27}& \frac{24}{81} & \frac{48}{243} & 0 \end{matrix}$$

The right-hand column represents the chance of your friend winning: $\frac1{27}$ of winning 3-0, plus $\frac6{81}$ of winning 3-1, plus $\frac{24}{243}$ of winning 3-2, which totals $\frac{55}{243} \approx 21.0\%$.

Similarly, the bottom row represents the probability of your winning: $\frac8{27}+\frac{24}{81}+\frac{48}{243} = \frac{192}{243}\approx 79.0\%$.

I should emphasize that this is exactly the same calculation that Joriki and Robert Israel's are doing, but in a less compact form.

You can do the same thing with the full 10×10 table to calculate the chances that you will win a 10-point game, or for any other size table. Using a computer, I calculated that this model gives your friend a $10.3\%$ chance of winning a 7-point game, a $6.5\%$ chance of winning a 10-point game, and a $1.4\%$ chance of winning a 21-point game. Her chance of winning drops rapidly as the game length increases, because it is very unlikely she will be able to put together the long run of points needed to win.

Using similar methods, you can calculate the likelihood that your friend will win from any particular game state, and then select a game state with a probability close to 50% that she will win. In this case, for a 10-point game, your friend will have a 52% chance of winning if your friend starts the game with 5 points.

-
Why replace $2$ with $18$ for basketball? –  Alex Becker Aug 1 '12 at 19:25
Actually 14 for basketball; I remembered wrong. And the actual value for baseball is not really 2, but only 1.8 or so. The answer is that there is no theoretical reason for these values; they are just values that have been observed to work well in practice. –  MJD Aug 1 '12 at 19:45

EDIT: Due to a helpful comment, I just realized that the winner is the player who scores 10 points first. Oops...

This is extremely shaky math, but it is the best I can think of given the information provided.

As of this post, there is no information about the spread of the distribution of OP's score (all we know is that it is frequently 10), so I will assume that OP always gets a 10. As for his opponent's score distribution, it has been said that the mean is approximately 5, but the max was 8 and min was 0. Using more extremely shaky math, let us assume that the range (0 - 8) covers 95% of the data, since 1/18 is approximately 5%. This means that 8 points is 4 standard deviations of the distribution, leading to a standard deviation of 2. The mean is 5, meaning that to get to OP's score of 10, his opponent must be 2.5 standard deviations above the mean. The probability of this is 0.621%, and so using a geometric distribution, we find that OP's opponent should win after 161 games.

This seems very high (and probably is), and take this result with a huge grain of salt because of the limited information we have.

-
I believe in this game, the winner is the first player to 10 points. So there IS actually enough information in the problem as stated. –  user22805 Aug 1 '12 at 20:03
Oops, didn't realize that! –  Draksis Aug 1 '12 at 20:14