2
$\begingroup$

I'm trying to find the expected number of trials, $x$, to achieve $n$ number of successes, when the probability of a success is dependent on the results of the last trial.

Specifically, I'm trying to calculate the effects of gacha pity on the expected number of trials to achieve $n$ number of successes. How it works is if a certain number of trials, $t$, have occurred without a success, the probability of success, $p$, will be increased by a set amount, $q$, for each failure. Once a success has been achieved, the number of trials in order to activate the probability increase is set back to $t$. I know that the expected number of trials for a number of successes is given by $x = n/p$, but this only works when $p$ is constant.

In the gacha system I'm examining:

$$p = 0.02,$$ $$t = 50,$$ $$q = +0.02$$

Any ideas or places you could point me to would be appreciated!

$\endgroup$
5
  • $\begingroup$ @Henry I'm not sure how you got that number since n (the target number of successes) is a variable. Additionally, I was looking for a way to find the average number of attempts, not the max number of attempts. I already know the max number of attempts for n is n*100 since p will equal 1 at 100 trials provided no successes occurred. $\endgroup$
    – MathNoob4
    Commented Nov 1, 2021 at 2:16
  • $\begingroup$ What is $n$ here? $\endgroup$
    – Henry
    Commented Nov 1, 2021 at 8:09
  • $\begingroup$ @Henry $n$ is the number of successes. For example, if $n$ = 3, you are trying to find the average number of trials to obtain 3 successes. $\endgroup$
    – MathNoob4
    Commented Nov 2, 2021 at 1:01
  • $\begingroup$ Thank you. So it seems the expected number of attempts for $n$ successes is $n$ times the expected number of attempts for one success. Next question: it seems that after $50$ consecutive failures, the probability of success rises from $0.02$ to $0.04$. Does it rise to $0.06$ after one more failure or after $50$ more failures? $\endgroup$
    – Henry
    Commented Nov 2, 2021 at 1:43
  • $\begingroup$ @Henry it rises after one more failure. $\endgroup$
    – MathNoob4
    Commented Nov 2, 2021 at 3:31

1 Answer 1

1
$\begingroup$

The expected number of attempts for $n$ successes is $n$ times the expected number of attempts for one success, and it is easier to look at the expected number of attempts for one success.

  • The probability of no success after $m$ attempts when $m\le t$ is $(1-p)^m$
  • The probability of no success after $m$ attempts when $t \lt m\le t+\frac{1-p}{q}$ is $(1-p)^t \prod\limits_{k=1}^{m-t}(1-p-kq)$
  • The probability of no success after $m$ attempts when $t+\frac{1-p}{q} \lt m$ is $0$

If you add these all up to give the expected number of attempts for one success and then multiply by $n$, then you get $$n \left(\frac{1-p^{t+1}}{1-p} + \left(1-p^{t}\right)\sum\limits_{m=t+1}^{t+\lfloor(1-p)/q\rfloor} \prod\limits_{k=1}^{m-t}(1-p-kq)\right)$$

This will not have a closed form, but in the example in the question with $n=3, p=q=0.02$ and $t=50$ it seems to give about $3\times 34.594555=103.783665$ from the earlier result

It may be possible to give approximations, at least for large $t$ and small $p$ and $q$ in special circumstances. For example if $c=\frac1p=\frac1q$ for some integer $c$ then I think you may be able to use, if I have done this correctly, an approximation like $$n\left(c-e^{-t/c}\left(c-\sqrt{\frac \pi 2}\sqrt{c}+\frac56-\frac7{12}\sqrt{\frac \pi 2}\sqrt{\frac{1}{c}} + \frac{617}{1080}\frac1c -\cdots\right) \right) $$

which with $n=3, t=50$ and $c=50$ gives about $103.7806$, which is not far away from the earlier result.

$\endgroup$
6
  • $\begingroup$ @MathNoob4 I do not follow your code but $47.5$ looks too high to me. If there was no pity then the expectation would be $\frac{1}{0.02}=50$. With the pity, you clearly cannot take more than $99$ attempts and if the system was "no pity until $98$ attempts but a guaranteed win on the $99$th attempt", the expectation would be about $43.23$. In fact the pity is much more generous and so the expectation must be lower and $34.59$ is plausible. $\endgroup$
    – Henry
    Commented Nov 7, 2021 at 0:13
  • $\begingroup$ yes, I actually noticed that I made a mistake in the program. I programmed it as if (1-p^t) was in a bracket with the earlier term. I've changed it since and it produced 24.5 instead, which is too low. link $\endgroup$
    – MathNoob4
    Commented Nov 7, 2021 at 0:54
  • $\begingroup$ I don't really understand how you came up with your formula, but I calculated the answer to the question using geometric distribution and received an answer that was identical to yours. Could you perhaps explain how you created this formula in a bit more detail? link to the calculation with geometric distribution $\endgroup$
    – MathNoob4
    Commented Nov 8, 2021 at 6:51
  • $\begingroup$ @MathNoob4 Do you mean the "If you add these all up ..." formula or the "It may be possible to give approximations, ..." expression? $\endgroup$
    – Henry
    Commented Nov 8, 2021 at 9:08
  • $\begingroup$ the "if you add these all up" part. In particular, I noticed that you were using the geometric series to add all the probabilities of no successes. What I'm a bit confused by is why adding the probability of no successes for every value of $m$ will result in the expected number of attempts. $\endgroup$
    – MathNoob4
    Commented Nov 9, 2021 at 2:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .