Expected gems needed to level up

Question

There is a game where you have an item and you can raise the level of the item from +0 to a higher value.

To do this you have to spend a Gem. First 6 upgrades are 100% successful. The 7th upgrade has a 50% chance of successfully raising the item 1 level and 50% chance of dropping it 1 level. The 8th upgrade is 50% successful just like the 7th, but it will drop the level to +0 on failure.

I'm trying to determine what is the average number of Gems I have to spend to raise the item from +0 to +8. Without loss of progress I think the average value would be 6+2*(1/50%) = 10 gems (six 100% upgrades and two 50% upgrades), but I don't know how to account for the level drop.

Answer 1

Let $a_k$ be the expected number of gems needed to get to level 8 if currently at level $k$.

$a_7 = 1 + \frac{1}{2} a_0$ [one gem spent and half the time you have to start over from 0]

$a_6 = 1 + \frac{1}{2} a_7 + \frac{1}{2} a_5$ [one gem spent, and half the time forward and half the time backward]

$a_5 = 1 + a_6$ [always 1 gem needed to get from level 5 to level 6]

$a_0 = 5 + a_5$ [always 5 gems needed to get from level 0 to level 5]

Solving these 4 linear equations for $a_0,a_5,a_6,a_7$ would give all the information you want.

Answer 2

Let $N$ be the total number of gems spent then we want to find $E(N)$, the expected number of gems.

$$ N=2\times F_6+8\times(1+F_7) $$ where $F_6$ is the number of times we drop at the seventh gem (thus have to pay two gems to get back to $+6$) and $F_7$ is the number of times we drop at the eighth gem (thus have to pay seven gems to get back to $+7$). The probability of failing at $+6$ and $+7$ are both $1/2$, so $$ E(N)=2\times\sum_{k=1}^\infty k(1/2)^k+8\times(1+1/2\times\sum_{k=1}^\infty k(1/2)^k) $$ Here the 1/2 in front of the second sum is there because there is only 50% chance of reaching 7 each time. Now $\sum_{k=1}^\infty k(1/2)^k=2$ so the expected number of gems is $E(N)=20$.

Numerical confirmation:

20.024052
2.002802
1.002306

Computer code is as follows:

package main

import (
    "math/rand"
    "fmt"
)

func half() bool {
    if rand.Intn(2) >= 1 {
        return true
    }
    return false
}

func main() {
    maxtries := 1000000
    totalgems := 0
    totalsixers := 0
    totalseveners := 0
    for try := 0; try < maxtries; try++ {
        gems := 0
    again:
        gems += 6
        gems++
        for half() {
            gems += 2
            totalsixers += 1
        }
        gems++
        if half() {
            totalseveners += 1
            goto again
        }
        totalgems += gems
    }
    fmt.Printf("%g\n", float64(totalgems)/float64(maxtries))
    fmt.Printf("%g\n", float64(totalsixers)/float64(maxtries))
    fmt.Printf("%g\n", float64(totalseveners)/float64(maxtries))
}