Hacker News Reader

Comment by Animats | Hacker News Reader

Short version: Roller Coaster Tycoon has a random walk type maze solver, and you can create a maze which takes O(2^N) time to solve.

View on HN

Is it really O(2^N)? If so, how'd you determine that so quickly? I'd like that intuition.

I do ok at big-O reasoning, but in this case turning probabilities into big-O eludes me.

In the video, there's an opposite maze which biases the guests to walk towards the exit, making it much easier to solve. What's the big-O of that version?

Let's pose the problem mathematically. Initial state is (0, forwards).

State (0, *) transitions to (1, forwards)

For k > 1, state (k, forwards) transitions to (k+1, forwards) with 5/8 probability and to (k-1, backwards) with probability 3/8.

For k > 1, state (k, backwards) transitions to (k+1, forwards) with 1/8 probability and to (k-1, backwards) with probability 7/8.

My intuition is that this very much resembles a biased walk so it should take exponential time. But there is the "momentum" to take into account.

Edit: It looks like we can use https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...

Came here for this - I knew there must be an analytical solution involving Markov chains.

I'm pretty sure this can be modeled with markov chains.

Your vertices would be (x, y, f), f being facing.

Edges are along the lines of (x, y, 0) - (x+1, y, {0,1,2,3}\1); (x, y, 1) - (x-1, y, {0,1,2,3}\0); (x, y, 2) - (x, y+1, {0,1,2,3}\3); (x, y, 3) - (x, y-1, {0,1,2,3}\2).

Probabilities are modeled in the video and need to be rotated 4 times for the four facings.

After that, I just don't recall my eigenvector calculation anymore. It feels like a good markov exercise, though.

I'm also absolutely not an expert on this (M.Sc. CS).

I would argue using Big O here is wrong and Landau symbols are not well defined on Markov chains/probabilistic turing machines. The point of Landau symbols is to give asymptotic bounds of functions with N approaching a certain value (usually positive infinity). My intuition says that the runtime of a probabilistic turing machine isn't necessarily a function tho (i.e. a deterministic association between any N and time(N)).

Google wasn't really helpful on complexity theory of Markov chains and based on the research papers that pop up it seems far enough away that I would avoid using Big O in this scenario.

Probabilistic turing machines even seem to have their own complexity classes (https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine).

Sure you can use Big O, just look at it as the expected runtime. For example, QuickSort is O(n^2) in worst case, but expected O(nlog(n)).

For probabilistic algorithms, we can look at the worst-case-w.h.p runtime: that is, a randomized quicksort, although technically still having an "absolute" worst case of O(n^2), actually is considered to have a worst case of O(nlog(n)), with probability 1 - 1 / (n^c) when bounded by Chernoff, as shown here: https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...

Note that they likely messed up slightly, it'll be more or less exponential in some base but possibly not 2. However big O notation does require you to get the base correct (or at least provide an upper bound), you can't ignore it like you can ignore a multiplicative or additive constant.

I think the key insights are:

- only the most significant (in terms of exponentially) factor(s) matters for big O (i.e. if you have a linear factor, the constant time factor is ignored)

- You have to determine whether you are talking worst case or average case or best case. Assuming average case I’d guess the opposite maze is O(n) because the time expands linearly with number of segments.

(Disclaimer: I am not formally educated in computer science, so admittedly I am not up to snuff on the mathematical side of things. Hopefully I am close enough here.)

edit: Oops, I failed to actually cover any time complexity calculation at all. I do not know if my approach is correct, but here's how I view the original:

    def walk_path(n):
        // probability of _not_ recursing is (1/n^2)
        // probability of _recursing_ is (1 - 1/n^2)
        // likelihood of recursing doubles with n
        // therefore, the average case of this loop is O(2^n)
        for (i : 0 -> n)
            if (random() < 0.5)
                walk(); // = O(1)
            else
                // Ignoring the actual walking on the branch, we just pretend we turn around directly.
                for (j : i -> 0) // = O(n/2)
                    walk();
                return walk_path(n);

and the opposite is straight forward, since the branches are 'constant time' - so it's more like a straight loop.

In this instance, you're only concerned with the average case.

Worst case is infinite: you just always take the path back in the direction of the entrance, and never even get past the first inlet.

Best case is O(n): you always take the path forward.

Yep, sorry, it quickly became apparent after rereading this that the original analysis was not worst-case. I have revised my comment to also include how I view calculating the actual time complexity since I didn't actually do that initially.

I'm not 100% confident in my explanation below, but maybe it's something like this, if we don't have prior knowledge of the asymptotic behavior of random walks:

The measured values are empirically exponential with a factor of 1.424 per indentation. If we assume that as an upper bound (which I don't think is quite right), then we have O(1.424^N) where N is the number of indentations.

Any exponent can be written in terms of any other base by multiplying by a constant. Since we often use base 2, we can choose to rewrite it in base 2 as O(2^(K*N)), where K is approximately 0.51.

Constant terms can be ignored in big O notation, so we can just drop the K to get O(2^N) (I am less sure about dropping a constant within the exponent).

You can't drop constant multiplicative terms in an exponent - O(2^n) is not equivalent to O(2^(2n)) as O(4^n) \= O(2^n) (the first one grows a lot faster).

You cannot drop constant terms from exponents in big-O notation.

Note that calling it 2^O(N) (or Omega) would be more accurate, unless you stumbled upon a really lucky coincidence.

Interesting, I'd never seen this kind of thing.

Are there any functions f(n) ∈ O(n) such that 2^(f(n)) ∉ O(2^(n))? If not, then either statement is accurate.

Yes, for example 2^(2n) ∉ O(2^(n)). Any function of a different linear coefficient. Big-O notation represents a bound by a constant factor (by modifying the exponent multiplier you get an exponential factor).

Thanks, you're right of course.

It's actually worse than a pure random walk - it had a clockwise bias which could be exploited to create travel asymmetries.

The devs have since updated the game to remove the clockwise bias.

Reply on news.ycombinator.com