Probability of catching a Pokémon in an Escalation Battle

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%?

• Looks like the birthday paradox to me. The mechanism is equivalent to randomly drawing numbers between $1$ and $100$, and catching occurs as soon as one number appears twice. Jan 29 '19 at 13:00

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$$

• Thanks! I was worried my question would get buried, so I'm relieved to get an answer so quickly. Jan 29 '19 at 19:32

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$$.

• You seem to have forgotten $p_0,$ resulting in $E(X) = 12.21.$ Jan 29 '19 at 16:41
• @jvdhooft Oops, you are right! I will correct the solution. Thank you. Jan 29 '19 at 19:48