Expected number of trials until first success I am trying to calculate the expected number of attempts to obtain a character in a game.
The way the game works is there is a certain probability in order to capture the character. Given that you capture the character, there is now another probability that you will actually obtain (aka Recruit) the character. If the recruit fails, the probability to recruit increases by a certain amount.
For example: There is a 25% chance to capture CharX. Given CharX is captured, there is now a 10% chance to recruit CharX. If not recruited, the chance to recruit on the next try jumps to 15% instead of 10%.
I can calculate the probability of recruiting based on one trial, but am not able to calculate the number of overall attempts expected because of the increasing probability on each trial. Can someone please help? Thanks.
EDIT: if not clear, on each trial you have to successfully capture AND recruit in order to obtain the character.
code:
from random import randint

repetitions = 10000
trials = 0
caps = 0
recs = 0

for i in range(0, repetitions):
    captureRate = 25
    recruitRate = 10
    failed = True
    while failed:
        trials += 1
        num = randint(1,100)
        if num <= captureRate:
            caps += 1
            num2 = randint(1,100)
            if num2 <= recruitRate:
                recs += 1
                failed = False
            else:
                recruitRate += 5
                if recruitRate > 100:
                    recruitRate = 100
recRate = (float(recs) / float(trials))
print 'Recruit Rate: %0.6f  ->  1 / %0.6f' % (recRate, 1.0 / recRate)

Output of this being:
Recruit Rate: 0.055254  ->  1 / 18.098260

 A: A good way to simplify the problem is to first figure out how many captures you need. Here is a simple recursive calculation:
from fractions import Fraction

base_recruit_rate = Fraction(10,100)
step_recruit_rate = Fraction(5, 100)

def ncaps(recruit_rate):
    """Expected number of captures needed"""
    if recruit_rate >= 1:
        return 1
    assert recruit_rate >= 0
    next_rate = recruit_rate + step_recruit_rate
    return (
        recruit_rate * 1 +
        (1 - recruit_rate) * (1 + ncaps(next_rate))
        )

print(ncaps(base_recruit_rate))

I assert the expected number of trials you need is the product of:


*

*The expected number of captures per recruitment $\approx 4.52$

*The expected number of trials per captures $= 4$


which multiply to give $18.08$. The number of trials per capture is given by a geometric distribution, which is how I obtained the value above.
The exact values are:


*

*The expected number of captures per recruitment $= 144626007107398739/32000000000000000$

*The expected number of trials per captures $= 4$

*The expected number of trials per recruitment $= 144626007107398739/8000000000000000$



Note that my assertion should be (IMO) highly plausible, but its truth should by no means be immediately obvious.
I want to emphasize this point because it is distressingly common for people to be completely dismissive of the interdependencies that can arise in problems like this; I want to make sure the reader knows the bold assertion is of the type they should have some suspicions about.
Agreement with empirical results give us additional confidence in the assertion. As r.e.s. points out in the comments, we have rigorous justification as well, since the assertion is of the form justified by Wald's lemma.
A: The probability of obtaining the character in the first trial is:
$$p_1 = \frac{1}{4} \frac{10}{100}.$$
The probability of capturing him in the second is:
$$p_2 = \frac{1}{4} \frac{15}{100}(1-p_1).$$
Once more, the probability of capturing him the third time is the probability that we do not get him the first and second and finally get him in the third trial. So
$$p_3 = \frac{1}{4} \frac{20}{100}(1-p_1)(1-p_2).$$
Observe the increase of probability of recrutation (from 10 to 15 and from 15 to 20). If we iterate this we have that the probability of obtaining the character in the $k$-th trial is
$$p_k = \frac{1}{4} \frac{(k+1)5}{100} \prod_{i=1}^{k-1}(1-p_i).$$
Important observation When $k=19$ (if we happen to get to the 19th trial) then 1/4 is the probability of getting the character since then the recrutation probability is now up to 100% which is 1. So
$$
p_k = \frac{1}{4} \frac{(k+1)5}{100} \prod_{i=1}^{k-1}(1-p_i) \mbox{ for } k=1,\dots,19$$
and
$$ p_k = \frac{1}{4}\prod_{i=1}^{k-1}(1-p_i), \mbox{ for } k\geq 20$$.
In a compact form we have
$$
p_k = \frac{1}{4} \left(\frac{(k+1)5}{100}\textbf{1}_{\{k\leq 19\}} + \textbf{1}_{\{k\geq 20\}}\right) \prod_{i=1}^{k-1}(1-p_i) \mbox{ for } k\geq 1$$
Let $X$ be the random variable that counts the number of trials until the character is captured. The random variable $X$ takes values in $\{1,2,3,\dots\}$ with probability mass function $P(X=k)=p_k$ , $k\geq 1$.
Observe that if all probabilities had been equal then $X$ is geometrically distributed with the same parameter, call it $p$ and its probability function is $P(X=k)=p(1-p)^{k-1}$ and it is known that $E[X] = 1/p$. In this case it is more involved:
The expected value is given by
$$E[X] = \sum_{k=1}^\infty k P(X=k) = \sum_{k= 1}^{\infty} k p_k.$$
This sum seems to converge relatively quick (already for $N$=50 iterations) I used R to compute the value (not efficient at all but this does not matter here): Here's the code and result:
    N=50

prod = rep(NA, length=N+1)

prod[1] = 1

for(i in 2:(N+1)){
    if(i <= 19){
        prod[i] = prod[i-1]*(1- (1/4)*((i+1)*5)/100)
    }
    if(i >= 20){
        prod[i] = prod[i-1]*(1- (1/4))

    }
}

sum <- 0

for(k in 1:N){
    if(k <= 19){
        sum = sum + k*(1/4)*((k+1)*5/100)*prod[k]
    }
    if(k >= 20){
        sum = sum + k*(1/4)*prod[k]
    }
}

sum

$$E[X] \approx sum = 8.56$$
A quick "test" is that this value should be between $\left(\frac{1}{4}\right)^{-1}$ and $\left(\frac{1}{4}\frac{10}{100}\right)^{-1}$ which it is. The reason is that if $X$ had been a geometric distribution with the highest constant probability $1/4$ then $E[X] =\left(\frac{1}{4}\right)^{-1}= 4$ on the contrary if $X$ had been a geometric distribution with the smallest constant probability then $E[X]= \left(\frac{1}{4}\frac{10}{100}\right)^{-1} = 40$. In our situation the probability starts being very small and then increases up to $1/4$ and hence the expected value should be between 4 and 40.
