The fact that this is done on a computer with a PRNG is significant here. (unless the game sources entropy from the environment, which is unlikely)
The PRNG has finite state. This means that it must be cyclical. This cycle of of states will manifest in a guest which will either loop infinitely without progressing into the maze. Or it will manifest in a guest which will progress a fixed, finite number of steps into the maze before the state of the PRNG cycles.
Therefore the guest either never completes the maze, or the guest completes the maze in time O(n * 2^k) where k is the number of bits of state in the PRNG and n is the number of inlets.
I've not looked at the source, but I doubt that each guest has a unique PRNG. It's more likely that there's one PRNG for the whole game, and so the behavior will depend as much on the number of guests in the park as anything else.
This is true, and it'll extend the size of the loop past the naive "once around the PRNG". However, 10^20k years is so much larger that it's safe to guess that even if you do your best to extend the size of the loop based on the behavior I saw there (the park puts in a certain number of people which stays fairly constant), you still end up with too few states reachable to ever prevent looping.
Assuming a roughly 4Hz update rate, 10^20k years is around 10^2.5trillion iterations.
The PRNG has fewer than 2048 bits (being very conservative), and with (let's round way up) 100 patrons exploring the same let's say 256 slots or so [1], you can encode an additional byte per patron, but you're still a long, long ways away from coming even close to the size where it's even close. That gets you a very generous 2^4608 (approx 10^1387) states you can reach, which isn't anywhere near close to the number of random iterations we can guess this will take. So it's safe to say the simulation as a whole will still loop, even with the state beyond the PRNG itself.
Note you have room to add a looooooooot more state in to my estimates before it's even remotely close. There's nowhere near enough bits available to encode things and avoid loops.
[1]: The number they can explore is not relevant, it's the number they will explore. I'm also naively assuming each of the 256 is equally likely, which is false, but is also a best case for this analysis. In reality the patrons tend to encode much less than that as they are much more likely to be towards the front of the maze.
Even a Mersenne twister won't be enough to represent 10^20,000+ states that'd be needed to complete just one maze run.
At a minimum, you need a PRNG with 100,000+ bits... or a 12.5kB+ state machine for your PRNG before you had a decent chance of one NPC finishing the maze. I don't think any modern PRNG has such state (most states cap out at 64-bits or 128-bits these days, because there's no feasible simulation that'd use all those RNGs. Mersenne Twister was probably the last "old style" PRNG algorithm that tried to make a huge cycle-length with a large-state).
Or the game could just use the OS equivalent of urandom, which adds environmental randomness to the pool when available. I'm pretty sure there's something similar on Windows...
The PRNG has finite state. This means that it must be cyclical. This cycle of of states will manifest in a guest which will either loop infinitely without progressing into the maze. Or it will manifest in a guest which will progress a fixed, finite number of steps into the maze before the state of the PRNG cycles.
Therefore the guest either never completes the maze, or the guest completes the maze in time O(n * 2^k) where k is the number of bits of state in the PRNG and n is the number of inlets.