RNG correlation (Generation I)

RNG correlation is a phenomenon that may affect the probabilities of random events in a game. Even though each individual output of most RNGs can be considered "random enough" (at worst slightly biased) in the absence of luck manipulation (e.g. after waiting a random amount of time), there is always correlation between multiple consecutive outputs of the RNG, since a finite number of different seeds (i.e. RNG internal states) cannot produce an infinite number of random sequences. With good RNG designs (e.g. cryptographically secure pseudorandom number generator), the presence of correlation can be made unnoticeable. However, bad RNG designs, combined with bad usage patterns, may allow RNG correlation to have an appreciable effect.

The effect of RNG correlation is usually only noticeable when the RNG is used multiple times in succession, without processing user input in-between. One famous example in Pokémon Red, Blue, and Yellow is generating the DVs of wild encounters, where one RNG value is used to determine whether an encounter happens, and two more are used as the DVs. This causes many of the 65536 possible DV combinations to be impossible or unlikely. Another common "bad" usage pattern is rejection sampling, where random values are drawn in a tight loop until a value in a certain range is generated. This would bias both the result and the RNG state thereafter. Notably, it can significantly affect the catch rate in Generation I.

Mechanics

See also: Luck manipulation (Generation I)#Mechanics of the RNG

In Pokémon Red, Blue, and Yellow, the value of the RNG advances each time by the value of the rDIV register, which itself is incremented at a rate of 16384Hz (~16779Hz on SGB). Since the game advances the RNG each frame, in normal gameplay, the state of the RNG can be considered uniformly random. This would suffice to generate two independent uniformly random bytes. However, assuming that the timing are fixed, a third RNG output byte will be highly correlated with the previous two, with at most a small variation due to different timings for rDIV increment (the "sub-rDIV" value). Furthermore, the three values will be related by a simple arithmetic relation, so the correlation will be noticeable even when only the approximate ranges of the values matter.

In particular, if the random numbers are drawn in a tight loop, then they will approximately follow a quadratic function (modulo 256), with the leading coefficient depending on the timing of the loop.

Effect on wild encounter DVs

The wild encounter system is one of the cases where too many random numbers are used. Even though the encounter slot is determined by hRandomSub (which enables DSum manipulation), the RNG is still used three times, once to determine whether an encounter happens, and twice to determine the DVs. At a result, many DV combinations are "impossible", since the necessary RNG state would result in the encounter not happening in the first place. The lower the encounter rate is, the less DV combinations are possible.

More precisely, usually four consecutive RNG values are used during this process:

1. Encounter check
2. Unused (caused by an inevitable lag frame)
3. Low byte of the DV (16 * Speed DV + Special DV)
4. High byte of the DV (16 * Attack DV + Defense DV)

Since the encounter check is confined to a small range, the low and high bytes of the DV are related in a way such that when the low byte increases or decreases by 2, the range of high byte increases or decreases by 3. Since both values "wrap around" at 256, this means that:

• For each value of the low byte, there are two ranges of the high byte.
• For each value of the high byte, there are three ranges of the low byte.

For grass with encounter rate 25, when the low byte is 0, the two ranges of the high byte are 13 – 26 and 141 – 154. Since the Attack DV and the Speed DV are the high nybbles of their respective bytes, they are more obviously correlated than the other two DVs. A complete list of possible DVs can be found here.

Note that, in unusual cases, an extra lag frame may happen between encounter check and DV generation. This may allow some "impossible" DVs to be generated.

Effect on the catch rate

In Generation I, whether a thrown Poké Ball successfully catches a wild Pokémon is determined by two random bytes, the first of them drawn by rejection sampling if the ball is better than a regular one: A Great Ball guarantees it to be in the range 0 – 200 (inclusive), and an Ultra Ball or a Safari Ball guarantees 0 – 150 (inclusive). Under normal circumstances, the Pokémon is caught if the first is less than or equal to the base catch rate of its species, and the second is less than or equal to an "HP factor" that is approximately inversely proportional to the percentage of remaining HP, and boosted specifically by Great Balls (but not Ultra Balls or Safari Balls). (Status effects affect the procedure in a complicated way.)

Ostensibly, this means that the catch rate is min((C + 1) / B, 1) * min((F + 1) / 256, 1), where C is the base catch rate, F is the HP factor, and B is 256 for regular Poké Balls, 201 for Great Balls, and 151 for Ultra Balls and Safari Balls. However, when B is not 256, the rejection sampling would create an RNG correlation that may significantly affect the catch rate.

For example, consider Tauros in the Safari Zone. Without throwing bait or rock, C is 45, and a typical value of F is 87 (it can vary a little depending on the max HP of Tauros). Therefore the success rate of each Safari Ball should be (46 / 151) * (88 / 256) ≈ 10.472%. However, simulation shows that, due to RNG correlation, the actual catch rate is only about 6.633%.

In fact, this is close to the most devastating effect RNG correlation can have on the catch rate. When the first RNG value tried in the rejection sampling is between 0 and 150, the probability 10.472% should be accurate. Meanwhile, when the first RNG value tried is not between 0 and 150, the probability of success drops to about 1.113%. In general, the catch rate with RNG correlation is at least 151/256 ≈ 59% of the "ideal" catch rate.

Some concrete analysis will illustrate why the effect is so large in this case. Experiment shows that each iteration of the rejection sampling takes 516 cycles (2.015625 rDIV periods), and there are 23960 cycles (93.59375 rDIV periods) between the last RNG call in the rejection sampling and the RNG call for the second random byte. Assuming that the rejection sampling did not get 0 – 150 on the first try, we can consider the last three RNG calls:

1. The second-to-last iteration of the rejection sampling, which must be in the range 151 – 255 for the rejection sampling to continue.
2. The last iteration of the rejection sampling, which must be in the range 0 – 45 to have a chance to catch the Tauros.
3. The second random byte, which must be in the range 0 – 87 to actually catch the Tauros.

Denoting those values as r₁, r₂, and r₃, we have (r₃ - r₂) - (r₂ - r₁) = 93 or 94 (depending on the "sub-rDIV" value). However, those ranges are very "misaligned", as visualized in the graph below.

From the graph, it can be seen that the only way for all three values to be in their respective ranges is that:

• r₁ must be in the range 151 – 184,
• r₂ must be in the range (r₁ - 94) / 2 – 45.
  • This range shrinks as r₁ increases: It is 29 – 45 for r₁ = 151, and only 45 for r₁ = 184.

Furthermore, there is no way to put another iteration of rejection sampling before this and still make a consistent RNG sequence. Therefore the second-to-last iteration is in fact the first iteration.

To put this in perspective, one can estimate the probability of success, given that the first RNG value is not between 0 and 150. Ideally, this probability should still be 10.472%, since the first value is rejected and should have no effect. In reality:

• To have a chance of success, this first value, i.e. r₁, must be in the range 151 – 184, which happens with conditional probability 34/105.
• The next RNG value, i.e. r₂, must hit a range with average length (1 + 17) / 2 = 9, which happens with probability 9/256.

Therefore, this conditional probability can be estimated as 34/105 * 9/256 ≈ 1.138%. (The actual probability is even lower, because the above analysis is optimistic about the "sub-rDIV" value.)