3 ms·
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/probabil
by ascar 6y ago
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 https://en.m.wikipedia.org/wiki/Probabilistic_Turing_machine).
- red0point 6y agoSure 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)).
- leapis 6y agoFor 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/Lectures/Lec13-Ineq.pdf https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...