Start → Mid(1, ↑)
prob: 1, time: 1?
Mid(1,↑) → Start
prob: ⅜, time: 3
Mid(1,↑) → End
prob: ¼, time: 1
prob: ⅜, time: 3
(not 100% sure about those times, here they are in units of the timesteps that a person spends to go from one square to another, so the 3 is “go to the left square, go to the middle square but coming from the left, go from here up/down having the normal orientation again”).There seem to be two ways to do this. First you could determine the average time to leave the park by pumping 1 person into the park every timestep until it reached a steady-state where one person was leaving the park, then just count how many people there are in the park. Assuming steady state, you do not need to use travel times to calculate that exactly 1.6 people occupy Start and 1.6 occupy Mid, with 0.6 making the journey back and 0.4 making the fast journey out and 0.6 making the slow journey out. These two slow journeys taking time 3 can be viewed as having (3–1)•0.6 occupation, or 1.2 people in each, so the total is 1.2 + 1.2 + 1.6 + 1.6 = 5.6 people in the park, so this should be the number of timesteps.
Or if you prefer a straight calculation it is S where
S = 1 + T
T = ⅜(3+S) + ¼(1) + ⅜(3)
S being the average time from Start → End and T bring the average time from Mid → End. This can be solved to similarly find S = 28/5 = 5.6 timesteps.I think the former approach is going to be theoretically easier to understand when you are asking, “I want to convert End to Mid(n+1, ↑) and introduce a new End and also a node Mid(n, ↓), how does adding these three nodes change the system?”
In fact I think to solve it you will want to always calculate three different flows. I have only given you one of them, a steady state where one person arrives in Start and then they leave out of End. The other one is that they arrive in Mid(n–1, ↑) at a steady rate and then leave out of End at that same rate. And finally there is the flow where they arrive in Mid(n–1, ↓) at a steady rate and then leave at the same rate. [I think Mid(0, _) is just Start here.]
If I have those three populations/average travel times then I have a way to add those 3 nodes to the system at each stage and this gives me a recurrence which can calculate the thing exactly.
I would need to think a bit about how to program all of that.
The small discrepancy of 1.424 vs your 1.41 is worth digging into. It might have a surprising reason. Or you might be right. Games are simulations, and simulations have emergent behaviors when you throw in a time dimension.
That doesn't necessarily mean that my simulation is perfect (and, another commentor has made an improvement on it!), but it does mean that this evidence alone is not enough to suspect the simulation.
Run with 5 million iterations per size:
15 size: 2514.4287536 steps (1.413 growth)
16 size: 3543.3930332 steps (1.409 growth)
17 size: 4986.7099864 steps (1.407 growth)
18 size: 7008.892906 steps (1.406 growth)
19 size: 9834.1058896 steps (1.403 growth)
20 size: 13806.3093036 steps (1.404 growth)
Also seems like it converges to a value below sqrt2, which doesn't surprise me. The function that drives the behavior just doesn't feel like it would end up on an irrational number for a growth rate.
Based on the logic presented in the video, I wrote a program that does a more efficient simulation, so that we could get a better estimate of the growth rate. Note that my simulation estimates a guest always takes the exact same amount of time to make 1 step, and there may be incorrect edge cases in my simulation.
In my simulation, I attempt each size of make 50,000 times and record the average number of steps it took to complete a maze of each size 1-25.
https://play.golang.org/p/FglwpqbsPPr
Results:
<output truncated for ease of viewing>
20 size: 9966 steps (1.397 growth)
21 size: 14057 steps (1.410 growth)
22 size: 19738 steps (1.404 growth)
23 size: 27372 steps (1.387 growth)
24 size: 38660 steps (1.412 growth)
25 size: 54266 steps (1.404 growth)
Marcel estimated a growth rate of 1.424 per added indent, and my larger sample simulation estimates a growth rate of about 1.4, slightly smaller but very much in a similar ballpark.