Background
Hey folks. So I am, in addition to being a casual math and physics nerd, a Pokémon speedrunner. I run the game Pokémon Red Version and the category "Any % Glitchless (Classic)." For those of you who don't know speedrunning terminology, "Any %" means that the only goal is to finish the game (i.e. you are allowed to skip any optional content) and "glitchless" means that you may not use any glitches. In the "glitchless (classic)" category, you are also not permitted to "hard reset" the game (power it off and back on again), which is necessary to manipulate the game's random number generator function, so for runners of this category, the RNG is functionally truly random.
Of course, one of the main purposes that we want to manipulate the RNG function is to control whether we get encounters. The encounter mechanic in Pokémon (simplified) is that there is a certain probability in any given region of the game that each step in an encounter generating tile* will give an encounter. If any of y'all have played Generation I Pokémon, you'll know that Mount Moon is the absolute most obnoxious area in the game and tends to generate an absolute torrent of encounters. This is because, in "cave" areas, every tile on the map* is an encounter generating tile, whereas in other areas, only grassy tiles can generate encounters, so grassy tiles can be avoided. Famously, one Pokémon speedrunner with the handle "ExtraTricky" got an absurd 18 encounters in Mount Moon in a previous world record.
Naturally, I was wondering what the average number of encounters in Mount Moon should be.
Simplified Problem
You'll notice that I asterisked a few of the notes about the encounter generation function. We're going to ignore certain complexities of this function for the purposes of the simplified problem. In the full problem, we'll reintroduce those complexities.
Like I said previously, every region of the map has an "encounter rate" that determines the probability that you will generate an encounter when stepping in an encounter-generating tile on the map. In Mount Moon, that encounter rate is $\frac{10}{256}$, which maybe doesn't seem that bad, but optimal movement through the area requires 276 steps (for any glitchless classic runners, this assumes no Hiker strats). This version of the problem is actually pretty simple: it's a binomal distribution. Thus, we can state the probability function as follows:
Let $r$ be the number of encounters.
$$ \mathbb P (r) = {276 \choose r} \cdot \bigg ( \frac{10}{256} \bigg )^r \cdot \bigg ( \frac{246}{256} \bigg ) ^{276-r}$$
I even made a graph!
The average just ends up being the weighted sum, which I plugged into a spreadsheet, so:
$$ \bar r = \sum_{n=0}^{276} n \mathbb P (n) \approx 10.7813$$
Full Problem
There are two confounding factors that I want to add in here:
Factor 1: Nido DVs and Catch Level
So the main Poké that you use in Gen 1 is Nidoking, which means you will catch a Nidoran♂ in Route 22. You can encounter this Nidoran♂ at levels 2, 3, or 4. We do not catch level 2 Nidorans, so those may be ignored. The player is, in random encounters, twice as likely to encounter a level 3 Nidoran♂ as a level 4 Nidoran♂.** And, of course, the strats differ when using a level 3 Nidoran♂ vs. a level 4 Nidoran♂.
Then, each individual Poké in Generation 1 has a "determinant value" for each stat that determines how high that stat will be compared so another Poké of the same species and level, which can be any 4 bit number (i.e. 0–15). This also determines what strats we use. In particular, if the Nidoran♂ has an attack DV under 5, we reset (we do not continue the run), so those may be ignore. With a level 3 Nidoran♂ whose attack DV is $5\leq x \leq10$ we take an extra 20 steps in Mount Moon. With a level 4 Nidoran♂ whose attack DV is $5\leq x \leq 8$, we also take those extra 20 steps. These are the above-referenced "Hiker Strats". Assume all DVs for attack are equally likely. We want to account for how these DV and catch level strats will affect our average.
Of course, this isn't actually that hard. We'll just need to have two separate probability functions based on whether we use Hiker strats or not and multiply those results times the probability of any given Nidoran♂'s catch level and attack DV.
Factor Two: The Two-Step Rule
This is the asterisk I put above with the encounter rates. The first two steps upon entering Mount Moon and the first two steps after any battle (trainer or wild encounter) will not generate encounters. This means that the maximum number of encounters is not, in fact, 276 because you will not generate an encounter until your third step after a battle, meaning the theorhetical maximum number of encounters is $\Big \lfloor \frac{276}{3} \Big \rfloor = 92$. In the above step count, I excluded the first two steps after entering Mt. Moon and after every trainer battle, but I did not exclude steps after random encounters.
This is the part that has me a little stumped. I suppose I could some kind of script or program that uses brute force to calculate every possible encounter profile given this two-step rule, but I'm wondering if there is a more elegant way to do it that I'm not seeing.
And yes, I know the binomial distribution estimate is probably close enough, but I'm curious if there is a non-ridiculous way to calculate the average number of encounters taking the two-step rule into account.
** I'm not actually sure this is accurate. In the part of the game where we catch the Nidoran♂, we have a method of only searching for wild encounters when the RNG is likely to give us a Nidoran♂ (called "DSUMming") and I don't know if this is biased towards a level 3 or a level 4 and/or by how much if so.
