The bug
When you let a structure block with integrity lower than 1.0 and seed of 0 (= random seed) load a structure every tick, the block at the lowest X, Y and Z coordinate of the structure appears to be less random over time. Compared to the other blocks of the structure, there are longer "streaks" where the block is either loaded or not loaded.
An extreme example (and reproduction steps) can be seen in this video: https://youtu.be/N8azjRO4KM0
Every tick a 8x8x8 cube of blocks is placed and afterwards a structure block loads a 8x8x8 cube with an integrity of 0.5. The block at the lowest X, Y and Z coordinates of the resulting cube stays for a significant amount of time the same.
Code analysis
20w49a, Mojang names
When a random seed is used (value 0) the method net.minecraft.world.level.block.entity.StructureBlockEntity.createRandom(long) creates a new Random instance based on the current milliseconds. Despite the milliseconds value being different every tick, the values are too similar as seed for the JDK Random implementation, as described in @unknown's comment.
A better solution might be to have only one static Random instance which is reused.
Linked issues
Comments 7
The problem with randomness is that you never know for sure if it's truly random.
For example, I'm going to draw 6 random numbers between 0-9: 9, 9, 9, 9, 9, 9.
How do you know if there was a problem with randomness or it was just a very unlikely but possible streak?
It happens constantly and consistently. This is no coincidence; if it were it would be an astronomically low coincidence.
Can confirm Marcono's comment that this is caused by the seeds being too similar to each other due to being initialized to the current time in milliseconds. Before producing any outputs, a Random object will multiply the seed you give by 0x5deece66d; there are 50ms in a tick, so you could expect the internal seed of the Random to differ by a maximum of approximately 0x5deece66d * 50 = 1‚260‚745‚195‚850 (give or take a few milliseconds). This make look like a lot, but nextFloat() < 0.5 will only be true if this internal seed is between 0 and 2^47 (mod 2^48), which about 100x larger. This explains the delay of seconds you can see.
The other blocks in the structure are not as noticeably affected, as repeated multiplication of 0x5deece66d (and then addition of 11 which I left out for simplicity) quickly scrambles seeds even if they started close together.
P.S. can confirm for 1.16.3
Can probably confirm for 17w16b but it is hard to tell since the blocks are alternating.
Probably related to MC-108629 and possibly caused by the fact that the current milliseconds are not a good value to initialize the random number generator because the values might be too similar to each other.