1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mindlack
    Jan 29 '19 at 13:00
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks! I was worried my question would get buried, so I'm relieved to get an answer so quickly. $\endgroup$
    – F1Krazy
    Jan 29 '19 at 19:32
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.