Probability of catching a Pokémon in an Escalation Battle

Question

This question is inspired by the Escalation Battles in Pokémon Shuffle. There's a couple of other Pokémon-related questions on here, but they don't address this specific problem.

The way an Escalation Battle works is, the $n$th time you beat it, you have $n$% chance of catching the Pokemon. If you've already caught the Pokémon, you get items instead. When $n=100,$ you're guaranteed to catch the Pokémon, but the chance of having not caught it by then must be vanishingly small.

I've competed in a few Escalation Battles, and I always seem to catch the Pokémon when $15 \leq n \leq 25.$ It's been years since I studied statistical probability at school, but this doesn't seem very intuitive to me. So I started wondering about the cumulative probability - how likely you are to have caught the Pokémon after $n$ levels.

Is there a general formula to calculate the cumulative probability of having caught the Pokémon after $n$ attempts? How many attempts will it take for the cumulative probability to exceed 50%?

Answer 1

Let $P(i)$ be the probability of having caught the Pokémon after the $i$th attempt. We have:

$$P(1) = 0.01$$ $$P(2) = P(1) + 0.02 (1 - P(1)) = 0.02 + 0.98 P(1) = 0.0298$$ $$P(3) = P(2) + 0.03 (1 - P(2)) = 0.03 + 0.97 P(2) \approx 0.0589$$ $$\ldots$$ $$P(100) = 1$$

Using this approach, we find that $P(11) \approx 0.4968$ and $P(12) \approx 0.5572.$ For the expected number of attempts, we can start calculating from the back. When starting the $n$th attempt, the expected value for the remaining turns $E[X_{n}]$ equals:

$$E[X_{n}] = \frac{n}{100} \cdot 1 + \left(1 - \frac{n}{100}\right) (E[X_{n+1}] + 1)$$

Working recursively, we find:

$$E[X_{100}] = 1$$ $$E[X_{99}] = 0.99 \cdot 1 + 0.01 (E[X_{100}] + 1) = 1.01$$ $$E[X_{98}] = 0.98 \cdot 1 + 0.02 (E[X_{99}] + 1) = 1.0202$$ $$\ldots$$ $$E[X_{2}] = 0.02 \cdot 1 + 0.98 (E[X_{3}] + 1) \approx 11.32$$ $$E[X_{1}] = 0.01 \cdot 1 + 0.99 (E[X_{2}] + 1) \approx 12.21$$

Alternatively, you could use the formula:

$$E[X] = \sum_{i=1}^{100}iP(i),$$

where $P(i)$ is the probability of catching the Pokémon on the $i$th attempt. Since the first $i-1$ attempts must fail, and the $i$th attempt must succeed, we find:

$$P(i) = \prod_{j=1}^{i-1} (1-P(j)) \frac{i}{100}$$

This ultimately results in:

$$E[X] \approx 12.21$$

Answer 2

It may be easier to compute the probability that the Pokemon survives up to and including the $n$th attempt; so let's say $p_n$ is the probability he survives up to and including step $n$, for $n= 1,2,3,\dots,100$. If I understand the problem correctly, the chance he survives the first attempt is $p_1 = 1-1/100 = 0.99$. To survive the $n$th attempt for $1 < n \le 100$ he must first survive up to step $n-1$ and then survive the attempt at step $n$, so $$p_n = p_{n-1} (1-n/100)$$ This recursion is sufficient to calculate $p_n$ for $n = 2,3,4, \dots ,100$.

It turns out that $p_{11}=0.503$ and $p_{12} = 0.443$, so the probability of capture first exceeds $0.5$ on step $12$, with probability of capture $0.557$. We might also compute the average number of attempts required, using the theorem $$E(X) = \sum_{n=0}^{\infty} P(X>n) = \sum_{n=0}^{100} p_n$$ where $X$ is the step on which he is captured. This computation yields $E(X) = 12.21$.