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).