2
$\begingroup$

I've been playing a video game where this problem has come up. I know it's stupid reason for doing math but at least I can now prove to kids that math is useful in the real world.

Anyway I have a game where I need to reach 'X' points. Each win awards 1 point and each lose subtracts a point. My probability of winning is 'P'. 'N' will be the average number of games to pay to reach 'X' points.

Here's the twist. After you win 3 or more games in a row, then each win awards 2 points until your win streak is broken (you lose). Similarly if you lose 3 or more games in a row, then your next win will award 2 points.

What would be the formula be to solve this problem? So you can just substitute the chance of winning each individual game and points required in order to solve for the number of expected games played.

I assume this is akin to one of those coin flip problems, but my maths is so rusty I think it would be quicker for me to write a script and loop it a few thousand times and call it close enough.

Thanks in advance for any help you can provide. <3

$\endgroup$
  • $\begingroup$ I think sampling this is a fine idea. You could also do it recursively. That is, define $E[k,s]$ to be the expected number of games it'll take you to get $k$ more points assuming you have a current streak of $s$ wins. Then a win leads you to $E[k-1,s+1]$ or $E[k-2,s+1]$ depending on the size of $s$ and a loss leads you to $E[k,0]$. Helps to note that $s≥3\implies E[k,s]=E[k,3]$. $\endgroup$ – lulu Sep 21 '16 at 11:52
  • $\begingroup$ "What would be the formula be to solve this problem? " what problem exactly ? there are many candidates. $\endgroup$ – user354674 Sep 21 '16 at 21:34
0
$\begingroup$

Consider finite-state machine finite state machine

$(1)-$one consecutive loss, $(2)-$two consecutive losses, $(3)-3+$ consecutive losses,

$(4)-$one consecutive win, $(5)-$two consecutive wins, $(6)-3+$ consecutive wins.

There also exists $(0)$ state, which is not plotted. It represents situation when first game yet to be played. Obviously, it has transitions $(0)\to L \to (1)$ and $(0)\to W \to (4)$.

Then we can define sums $(S_i)$ of all sequences which lead to corresponding states: $$ \begin{cases} S_0=1\\ S_1=(S_0+S_4+S_5+S_6)L\\ S_2=S_1L\\ S_3=(S_2+S_3)L\\ S_4=(S_0+S_1+S_2+S_3)W\\ S_5=S_4W\\ S_6=(S_5+S_6)W \end{cases} $$ Then we take $L=pz$, $W=qz$, $p+q=1$ and solve system for $S_i$. Once we've done, we should consider $S_i$ as generating function and find respective series over $z$. Then for $S_i$ coefficient near $z^n$ will represent probability of state $i$ after $n$ games. Only thing left is to properly assign weights $(-1,+1,+2)$ and calculate mean value as function of $n$.

Saying this, I should notice that practical implementation of these steps is rather hard, as it involves factorization of cubic polinomials (constants dependant of $p,q$)

** Edit **

Suddenly I realized, that solution of problem is quite trivial, so here is it.

First, expand system of equations: $$ \begin{cases} S_1 = (1+S_4+S_5+S_6)L\\ S_2 = S_1L\\ S_3 = (S_2+S_3)L\\ S_4 = (1+S_1+S_2+S_3)W\\ S_5 = S_4W\\ S_6 = (S_5+S_6)W \end{cases}\to \begin{cases} S_1 = (1+S_4+S_5+S_6)L\\ S_2 = (1+S_4+S_5+S_6)L^2\\ S_3 = S_3L+(1+S_4+S_5+S_6)L^3\\ S_4 = (1+S_1+S_2+S_3)W\\ S_5 = (1+S_1+S_2+S_3)W^2\\ S_6 = S_6W+(1+S_1+S_2+S_3)W^3 \end{cases} $$ Once again, we treat $L=pz,W=qz,p+q=1$, that's why such things as $W^3$ have sence.

Next, introduce "new variables": $$ N_1 = 1+S_4+S_5+S_6\\ N_2 = 1+S_1+S_2+S_3 $$

Express system in terms of $N_1$ and $N_2$

$$ \begin{cases} S_1 = N_1L\\ S_2 = N_1L^2\\ S_3 = N_1\left(\frac{L^3}{1-L}\right)\\ S_4 = N_2W\\ S_5 = N_2W^2\\ S_6 = N_2\left(\frac{W^3}{1-W}\right) \end{cases} $$ If we plug these expressions back into the definition of $N_1$ and $N_2$, and simplify a bit: $$ \begin{cases} N_1 = 1+\frac{W}{1-W}N_2\\ N_2 = 1+\frac{L}{1-L}N_1 \end{cases}\to \begin{cases} N_1 = \frac{1-L}{1-L-W}\\ N_2 = \frac{1-W}{1-L-W} \end{cases}\to \begin{cases} N_1 = \frac{1-pz}{1-z}\\ N_2 = \frac{1-qz}{1-z} \end{cases} $$ Now we have direct expressions for $N_1$ and $N_2$, so it is possinle to calculate $S_i$: $$ \begin{cases} S_1 = p^2z-(1-p)p+\frac{(1-p)p}{1-z}\\ S_2 = p^3z^2-p^2(1-p)z-p^2(1-p)+\frac{(1-p)p^2}{1-z}\\ S_3 = p^3\left(-z^2-z-1+\frac{1}{1-z}\right)\\ S_4 = q^2z-(1-q)q+\frac{(1-q)q}{1-z}\\ S_5 = q^3z^2-q^2(1-q)z-q^2(1-q)+\frac{(1-q)q^2}{1-z}\\ S_6 = q^3\left(-z^2-z-1+\frac{1}{1-z}\right) \end{cases} $$ Expand expressions above in series over $z$ and hide addenda in sums where possible: $$ \begin{cases} S_1 = (p-p^2)z^2+pz+(1-p)p\sum^{\infty}_{n=3}z^n\\ S_2 = p^2z^2 + (1-p)p^2\sum^{\infty}_{n=3}z^n\\ S_3 = p^3\sum^{\infty}_{n=3}z^n\\ S_4 = (q-q^2)z^2 + qz + (1-q)q\sum^{\infty}_{n=3}z^n\\ S_5 = q^2z^2+(1-q)q^2\sum^{\infty}_{n=3}z^n\\ S_6 = q^3\sum^{\infty}_{n=3}z^n \end{cases} $$ As said coefficients near respective power of $z$ in $S_i$ represent probability of system being in state $i$ after $n$ games. It's easy to check than that if we sum all $S_i$, then all coefficients at $z^n$ will be $1$ (Recall that $S_0=1$).

At this point we almost done. As stated in task we receive or lose points when we win/lose game. In terms of finite-state machine it happens when we transit from one state to another. Knowing probabilities of states, we can immediately get probabilies of all transitions. $$ \begin{cases} S_0\to S_1: L = pz\\ S_0\to S_4: W = qz\\ S_1\to S_2: S_1L=(p^2-p^3)z^3+p^2z^2+(1-p)p^2\sum^{\infty}_{n=4}z^n\\ S_1\to S_4: S_1W=(p-p^2)qz^3+pqz^2+(1-p)pq\sum^{\infty}_{n=4}z^n\\ S_2\to S_3: S_2L=p^3z^3+(1-p)p^3\sum^{\infty}_{n=4}z^n\\ S_2\to S_4: S_2W=p^2qz^3+(1-p)p^2q\sum^{\infty}_{n=4}z^n\\ S_3\to S_3: S_3L=p^4\sum^{\infty}_{n=4}z^n\\ S_3\to S_4: S_3W=p^3q\sum^{\infty}_{n=4}z^n\\ S_4\to S_1: S_4L=(q-q^2)pz^3+pqz^2+(1-q)pq\sum^{\infty}_{n=4}z^n\\ S_4\to S_5: S_4W=(q^2-q^3)z^3+q^2z^2+(1-q)q^2\sum^{\infty}_{n=4}z^n\\ S_5\to S_1: S_5L=pq^2z^3+(1-q)pq^2\sum^{\infty}_{n=4}z^n\\ S_5\to S_6: S_5W=q^3z^3+(1-q)q^3\sum^{\infty}_{n=4}z^n\\ S_6\to S_1: S_6L=pq^3\sum^{\infty}_{n=4}z^n\\ S_6\to S_6: S_6W=q^4\sum^{\infty}_{n=4}z^n\\ \end{cases} $$ Virtually, all of them can have different weights, but acoording to the task, we have $S_3\to S_4$ and $S_6\to S_6$ $+2$ points, everything else involved $W$ transition $+1$ point and $L$ transition $-1$ point.

Expected value of points after $n$ games is sum of probabilities (multiplied on weights) of transitions for all powers $i$ of $z$, such as $0\le i \le n$.

Let us collapse transitions over weights: $$ ES=(-1)\left(p(z+z^2+z^3)+p\sum^{\infty}_{n=4}z^n\right)+\\(+1)\left(q(z+z^2+z^3)+\left[q-q(p^3+q^3)\right]\sum^{\infty}_{n=4}z^n\right)+\\(+2)\left(q(p^3+q^3)\sum^{\infty}_{n=4}z^n\right)\\ $$ Simplify it $$ ES = (q-p)(z+z^2+z^3)+(q-p+q(p^3+q^3))\sum^{\infty}_{n=4}z^n $$ Hence, for the first $3$ games expected number of points received for one game is $q-p$, while for games after 3rd this value is $q-p+q(p^3+q^3)$. It's expectable, because we can receive 2 points only starting from 4th game.

Finally, let us consider the case proposed by OP: target $30$ points, winning rate $60\%\to q=0.6;p=0.4$ $$ q-p=0.2\quad q-p+q(p^3+q^3)=0.368\\ n-3=\frac{30-0.2*3}{0.368}\approx 79.89\\ n\approx 82.89\approx 83 $$ where $n-$average number of games required to hit the target amount of points.

$\endgroup$
0
$\begingroup$

Thanks everyone for the answers. The steady state solution Kostiantn provided was very interesting. Unfortunately I barely remember the math I learnt in university.

Fortunately I do remember the programming. Here's a little script I made. https://jsfiddle.net/Lbdhnsg0/15/

My current situation in the game is: Goal points to reach = 30 probability of winning each game = 60% It appears the average number of games is approximately 92.

Didn't realise it was going to take me in my game, considering a Game takes about 15 minutes and I've got 10 days to reach the goal.

Anyway, thanks again everyone for the help. I'm sure the answers here will help future students. I know questions like these really helped me get through university.

$\endgroup$

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.