Expected number of trials until first success

Question

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

Answer 1

Here's a flowchart:

In this game, trials are repeated until a success occurs, where success $(S_i)$ on the $i$th trial means capture $(C_i)$ followed by recruitment $(R_i)$; that is, $S_i=C_iR_i$. The $i$th trial results in failure $(F_i)$ either by an immediate failure to capture $(\bar C_i)$ or by a capture followed by a failure to recruit $(C_i\bar R_i)$; that is, $F_i=\bar C_i\cup C_i\bar R_i$.

The game is such that, independent of which trial $(i)$ is considered, $P(C_i)=P_C$, and $P(R_i\mid C_i\cap\text{\{$j$ failures-to-recruit have occurred prior to the $i$th trial\}})=\min\{P_R + j\Delta,\,1\}$, where $P_C, P_R, \Delta$ are given constants. (The example mentioned in the question uses $P_C=25\%,\ P_R=10\%, \Delta=5\%$.)

Letting $P_k=P(F_1F_2\ldots F_{k-1}S_k)=P(\text{first success occurs on the $k$th trial})$, and letting $T$ denote the time (trial number) of the first success, we have $$\bbox[lightyellow]{E(T) = \sum_\limits{k=1}^\infty\,k\,P_k}\tag{1} $$ and we can express $P_k$ in terms of the given $P_C,P_R, \Delta$ by using the law of total probability. A method to do so is to partition the event $F_1F_2\ldots F_{k-1}S_k$ into the $2^{k-1}$ possible "paths to success" corresponding to whether each of the respective $k-1$ failures is by "failing to capture" $(\bar C_i)$, or by "capturing and failing to recruit" $(C_i\bar R_i)$. Thus, $P_k$ can be found by conditioning $S_k$ on each possible "path to success", which in each case allows determination of how many times (if any) the recruitment probability is incremented by $\Delta$:

$$\begin{align} P_1 &= P(S_1)= P(C_1R_1)=P_CP_R\\ \\ P_2 &= P(F_1S_2) \\ &=P(F_1S_2C_1)+P(F_1S_2\bar C_1)\\ &=P(S_2C_1\bar R_1)+P(S_2\bar C_1)\\ &=P(S_2\mid C_1\bar R_1)\cdot P(C_1\bar R_1)+P(S_2\mid\bar C_1)\cdot P(\bar C_1)\\ &=P_CP_R^{(1)}\cdot P_C(1-P_R)+P_CP_R\cdot(1-P_C)\\ \\ P_3&=P(F_1F_2S_3)\\ &=P(F_1F_2S_3C_1C_2)+P(F_1F_2S_3C_1\bar C_2)+P(F_1F_2S_3\bar C_1C_2)+P(F_1F_2S_3\bar C_1\bar C_2)\\ &=P(S_3\,C_1\bar R_1\,C_2\bar R_2)+P(S_3\,C_1\bar R_1\,\bar C_2)+P(S_3\,\bar C_1\,C_2\bar R_2)+P(S_3\,\bar C_1\,\bar C_2)\\ &=P(S_3\mid C_1\bar R_1\,C_2\bar R_2)\cdot P(C_2\bar R_2\mid C_1\bar R_1)\cdot P(C_1\bar R_1)\\ &\quad+P(S_3\mid C_1\bar R_1\,\bar C_2)\cdot P(\bar C_2\mid C_1\bar R_1)\cdot P(C_1\bar R_1)\\ &\quad+P(S_3\mid \bar C_1\,C_2\bar R_2)\cdot P(C_2\bar R_2\mid \bar C_1)\cdot P(\bar C_1)\\ &\quad+P(S_3\mid \bar C_1\,\bar C_2)\cdot P(\bar C_2\mid\bar C_1)\cdot P(\bar C_1)\\ &=P_CP_R^{(2)}\cdot P_C(1-P_R^{(1)})\cdot P_C(1-P_R)\\ &\quad+P_CP_R^{(1)}\cdot(1-P_C)\cdot P_C(1-P_R)\\ &\quad+P_CP_R^{(1)}\cdot P_C(1-P_R)\cdot(1-P_C)\\ &\quad+P_CP_R\cdot(1-P_C)\cdot(1-P_C)\\ \\ &\text{etc.}\\ \\ \end{align}$$

where $$\begin{align}P_R^{(j)}&=P(R_i\mid C_j\cap\{\text{$j$ failures-to-recruit occur prior to the $i$th trial\}})\\ &=\min\{P_R + j\Delta,\,1\}\end{align}$$

and we've used the fact that $F_i\bar C_i= \bar C_i,\ \ F_iC_i=C_i\bar R_i.$

To write the general formula for $P_k$, for convenience let $$\begin{align}F_i^{(0)}&:=F_i\bar C_i=\{\text{$i$th trial fails with $0$ capture}\}=\bar C_i\\ F_i^{(1)}&:=F_iC_i=\{\text{$i$th trial fails with $1$ capture}\}=C_i\bar R_i.\end{align}$$

Now there are exactly $2^{k-1}$ disjoint paths to success $S_k$, being just those of form $F_1^{(x_1)}...F_{k-1}^{(x_{k-1})}S_k$, where $x=(x_1...x_{k-1})\in\{0,1\}^{k-1}$ is a string of $k-1$ bits. Therefore, we have the following union of disjoint sets: $$F_1\ldots F_{k-1}S_k={\bigcup}_{x\in\{0,1\}^{k-1}} F_1^{(x_1)}\ldots F_{k-1}^{(x_{k-1})}S_k $$ so $$\begin{align}P_k&=P\left({\bigcup}_{x\in\{0,1\}^{k-1}} F_1^{(x_1)}\ldots F_{k-1}^{(x_{k-1})}S_k \right) \\[2ex] &= \sum_\limits{x\in\{0,1\}^{k-1}}P(F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})}S_k)\\ &=\sum_\limits{x\in\{0,1\}^{k-1}}P(S_k\mid F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})})\cdot P(F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})})\\ &=\sum_\limits{x\in\{0,1\}^{k-1}}P(C_kR_k\mid F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})})\cdot P(F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})})\\ \end{align}$$ $$\bbox[lightyellow]{P_k=\sum_\limits{x\in\{0,1\}^{k-1}}\left(P_CP_R^{(|x|_{k-1})}\cdot\prod_\limits{j=1}^{k-1}\left((1-P_C)\textbf{1}_{\{x_j=0\}}+P_C(1-P_R^{(|x|_{j-1})})\textbf{1}_{\{x_j=1\}}\right)\right)}\tag{2}$$ where $|x|_j:=\sum_\limits{i=1}^{j}x_i$, and we have used the following facts:

1. We have $$\begin{align}P(C_kR_k\mid F_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})}) &=P(C_k)\cdot P(R_k\mid C_kF_1^{(x_1)}F_2^{(x_2)}\ldots F_{k-1}^{(x_{k-1})})\\ &=P_C\cdot P_R^{(|x|_{k-1})}\end{align}$$ because $F_1^{(x_1)}\ldots F_{k-1}^{(x_{k-1})}= \text{\{$|x|_{k-1}$ failures-to-recruit have occurred prior to the $k$th trial\}}.$

2. We have $$\begin{align}&P(F_1^{(x_1)}\ldots F_{k-1}^{(x_{k-1})})\\ &=P(F_1^{(x_1)})\cdot P(F_2^{(x_2)}\mid F_1^{(x_1)})\cdot P(F_3^{(x_3)}\mid F_1^{(x_1)}F_2^{(x_2)})\cdots P(F_{k-1}^{(x_{k-1})}\mid F_1^{(x_1)}\ldots F_{k-2}^{(x_{k-2})})\\ &=\prod_\limits{j=1}^{k-1}\left((1-P_C)\textbf{1}_{\{x_j=0\}}+P_C(1-P_R^{(|x|_{j-1})})\textbf{1}_{\{x_j=1\}}\right)\end{align}$$ because each factor in the product is one of the following two forms, for $j\in 1..{k-1}$:$$\begin{align}P(F_j^{(0)}\mid F_1^{(x_1)}\ldots F_{j-1}^{(x_{j-1})})&=P(\bar C_j\mid F_1^{(x_1)}\ldots F_{j-1}^{(x_{j-1})})=1-P_C\\ P(F_j^{(1)}\mid F_1^{(x_1)}\ldots F_{j-1}^{(x_{j-1})})&=P(C_j\bar R_j\mid F_1^{(x_1)}\ldots F_{j-1}^{(x_{j-1})})\\ &=P(C_j)P(\bar R_j\mid C_j F_1^{(x_1)}\ldots F_{j-1}^{(x_{j-1})})\\ &=P_C(1-P_R^{(|x|_{j-1})}).\end{align}$$

Note 1. Although the finite sums in Eq.(2) give the exact $P_k$ values, the time required to compute them increases exponentially as $k$ increases, approximately doubling with every increment in $k$; consequently, some values of $(P_C,P_R,\Delta)$ will make it infeasible to compute $E(T)$ to a required precision. For the example in the question, my computer required about $33$ hours to find $E(T) = 11.93... + \sum_{k\gt 30}k\,P_k,$ and the series is still growing by about $0.5$ per $k$-increment at this point, though the rate is gradually decreasing. (This is consistent with Monte Carlo simulations by myself and others that find $E(T)\approx 18$, but my computer would need many years to confirm that by these formulas!)

Note 2. The following table summarizes various cases in which enough terms could be computed using Formula (2) to determine $E(T)$ rounded to the number of digits shown, generally requiring $k\le 23$. In all cases, the results agree with Monte Carlo simulations precise to at least three significant figures (at $95\%$ confidence), which required up to $10^6$ simulated trials.

P_C  P_R  Delta  E(T)
------------------------
.75  .50  .25    2.16666
.50  .75  .25    2.50000
.50  .50  .50    3.00000
.50  .50  .25    3.2500
.50  .40  .20    3.78
.50  .40  .10    4.12
.40  .40  .40    4.30
.50  .30  .20    4.33
.50  .25  .25    4.44
.40  .30  .20    5.4 

---

Here are the (Sage) programs I used:

%sage
P_C, P_R, dP = 25/100, 10/100, 5/100    #(global variables)

#------------------------
#Implementing Formula (2):

def PR(i): return min(P_R + i*dP, 1)
def Pterm(k,x):
    x = x.digits(2,padto=k-1)
    p = P_C*PR(sum(x))
    for j in xrange(k-1):
        if x[j]: p *= P_C*(1-PR(sum(x[:j])))
        else: p *= 1-P_C
    return p

def P(k):
    tot = 0
    x = 0
    while x < 2^(k-1):
        tot += Pterm(k,x)
        x += 1
    return tot

def E(n):  
    tot = 0
    for k in [1..n]:
        p = P(k)
        tot += k*p
        print "%s (k = %s)" % (tot.n(), k)

E(30)

#-----------
#Monte Carlo:

def simulate(n):
    times = [] 
    for _ in [1..n]:
        PR = P_R 
        failed = True
        time = 0 
        while failed:
            time += 1
            if random() <= P_C:
                if random() <= PR:
                    failed = False
                else:
                    PR += dP
                    PR = min(PR,1)
        times += [time] 
    return times

times = simulate(10^6)  
print mean(times).n(), (std(times)/sqrt(len(times))).n()

Answer 2

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.

Answer 3

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.