Lottery in which your luck increases every turn, but resets once you win.

Question

Problem:

Suppose a lottery exists in which your luck increases as you play. The probability of winning a prize starts at 1%. After every unsuccessful attempt, the probability of winning increases by 1% from your previous odds (so 1% becomes 2%). When a prize is won, the chance of winning is reset to 1%. What is the expected number of prizes that you will receive after 100 uses?

What we know so far:

So far we have tried recurrence formulas but failed to get a closed form answer.

Through a python script and brute forcing we have calculated the answer to be 7.8608…

We have also tried by viewing 1% as 1/100, we added up the fractions: 1/100 + 2/100 + 3/100... + 14/100, which yielded a sum of 105/100. Based on this calculation, the probability of winning appears to exceed 100%. To determine the number of times this outcome would occur within 100 attempts, we divided 100 by 14. But we again found a problem as we ended up with a sum of 105/100.

All of our answers lie closely to each-other but we have yet to find a concrete answer

We would appreciate any help that we can get!

Answer 1

Using the following python script:

def cache(function):
    cache = {}
    def f(*args):
        if args in cache: return cache[args]
        result = function(*args)
        cache[args] = result
        return result
    return f

@cache
def wins_average(turns_completed=0, probability=1):
    if turns_completed == 100: return 0
    return probability * (100**(100-turns_completed) + \
            wins_average(turns_completed+1)) + \
        (100-probability) * wins_average(turns_completed+1, probability+1)

print(wins_average())

we get that the exact answer is 7.86080126403229668198182908097394362384354574898764667238115242755521947164335122692038436352382356040222738777625219891364911130702970910977870565447613758476042568092806020045109899810694869084004791. However, we have yet to get insight as to why this is.

Answer 2

$\def\eqd{\stackrel{\text{def}}{=}}$ Let $\ \frac{X_t}{100}\ $ be the probability of your winning on the $\ t$-th try. Then you will have won on the $\ t$-th try if and only if $\ X_{t+1}=1\ $. Your expected number of wins after $100$ tries is therefore $$ \sum_{t=1}^{100}\Bbb{P}\big(\text{You win on the $\ t$-th try}\big)=\sum_{t=1}^{100}\Bbb{P}\big(X_{t+1}=1\big)\ . $$ Now $\ X_t\ $ is a discrete, homogeneous, $100$-state Markov chain, the entries of whose transition matrix are given by \begin{align} P_{pq}&=\Bbb{P}\big(X_{t+1}=q\,\big|\,X_t=p\big)\\ &=\cases{1-\frac{p}{100}&if $\ q=p+1$\\ \frac{p}{100}&if $\ q=1$\\ 0&otherwise.} \end{align} If $\ \pi_t\ $ is the (column ) vector of probabilities of $\ X_t\ $ being in any given state: $$ (\pi_t\big)_q\eqd\Bbb{P}\big(X_t=q\big)\ , $$ then $$ (\pi_1)_q=\cases{1&if $\ q=1$\\ 0&otherwise,} $$ and \begin{align} \pi_{t+1}^T&=\pi_t^TP\tag{1}\label{1}\\ &=\pi_1P^t\ . \end{align} Your expected number of wins after $100$ tries is therefore given by \begin{align} \sum_{t=1}^{100}\Bbb{P}\big(X_{t+1}=1\big)&=\sum_{t=1}^{100}\big(\pi_{t+1}\big)_1\\ &=\sum_{t=1}^{100}\pi_{t+1}^T\pi_1\\ &=\sum_{t=1}^{100}\pi_1^TP^t\pi_1\ . \end{align} Because the matrix $\ P\ $ is sparse, with only two non-zero entries in every row, the recursion \eqref{1} can be used to calculate the vectors $\ \pi_{t+1}\ $ for $\ t=1,2,\dots,100\ $ quite quickly: \begin{align} (\pi_{t+1}^TP)_q&=\sum_{p=1}^{100}\big(\pi_t\big)_pP_{pq}\\ &=\cases{\sum_\limits{p=1}^{100}\frac{p\big(\pi_t\big)_p}{100}&if $\ q=1$\\ \frac{\pi_{q-1}(101-q)}{100}&if $\ 2\le q\le100$}\ . \end{align}

The Magma script given below performs the calculations described above, and obtains exactly the same answer as Number Basher does with the Python script he gives in his answer. To run the script, copy and paste it into the online Magma calculator and click on the "submit" button.

nt:=100;
n:=100;
oldpi:= ZeroMatrix(Rationals(),1,nt);
newpi:= ZeroMatrix(Rationals(),1,nt);
oldpi[1,1]:=1;

expw:=0;
for t in [1..nt] do
  for p in [1..n] do
    newpi[1,1]:=newpi[1,1]+p*oldpi[1,p]/n;
  end for;
  for q in [2..n] do
    newpi[1,q]:=oldpi[1,q-1]*(101-q)/n;
  end for;
  expw:=expw+newpi[1,1];
  oldpi:=newpi;
  newpi:= ZeroMatrix(Rationals(),1,nt);
end for;

print expw;