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%?
 A: 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$$
A: 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$.
