I am interested in some general theorems related to lower bounds on discrete time finite Markov chains hitting probabilities (preferably ergodic chains , but not necessarily ), with references . Similar results related to continuous time Markov chains, that allow discretization, are welcome. Thank you.

  • 3
    $\begingroup$ The question is too broad. if you narrow it down a bit you may get more helpful answers. To quote Heisenberg "you can say nothing about everything, and everything about nothing". $\endgroup$ May 22 '19 at 10:40
  • $\begingroup$ @LiviuNicolaescu Thank you for your feedback. The question is connected to this paper that I posted on arXiv server: arxiv.org/abs/1804.11181 This is my Clustered Sparrow Algorithm. I claim that NP complete problems, like 3SAT can be solved efficiently by randomised algorithms. Basically I propose to prove that NP=RP. My theoretical analysis is incomplete, but I strongly believe this could be an interesting approach. Unfortunately, my BSc. training level in mathematics limits my success odds in this direction. In other words, I could use some help in this direction. $\endgroup$ May 22 '19 at 15:19
  • $\begingroup$ Those are the roots of my question. I have studied this problem (NP=RP) for a few years. I think that some strong results in ergodic Markov chain theory should solve the problem stated in my previous comment. $\endgroup$ May 22 '19 at 15:24
  • $\begingroup$ I cannot reformulate the question in a more specific manner, unless I talk about the Clustered Sparrow Algorithm and the associated Markov chain model, and this is not meant to be a self .promotional post, but this is the background related to my question. $\endgroup$ May 22 '19 at 15:30
  • $\begingroup$ Your comments address my suggestion. Let's hope somebody out there can help you. $\endgroup$ May 23 '19 at 10:15

Chapter 10 in the book "Markov chains and mixing times (see http://www.ams.org/publications/authors/books/postpub/mbk-107 and https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf ) is all about bounding hitting times for discrete chains.

  • $\begingroup$ Thank you for the free link to your book, as time allows me I will get to work. I explained the background related to my question on stackexchange, and indicated a link to my paper that I posted on arXiv (second comment), in which I developed the Clustered Sparrow Algorithm. The fundamental ideas on which my algorithm is based belong to Professor Schoning (given in references), and all I do is develop his ideas a little bit further. As a consequence, I do not claim any kind of priority in this direction of research. $\endgroup$ May 24 '19 at 6:30
  • $\begingroup$ For me this is just a fascinating problem, with an importance hard to overestimate. If you also find these ideas interesting, and if you can allocate time for this task, please feel free to develop them further. My theoretical analysis is incomplete , but Schoning's ideas are reallly, really interesting. $\endgroup$ May 24 '19 at 6:36
  • $\begingroup$ I browsed chapter 10 of your book, yes, this is the real deal. Once again, thank you @YuvalPeres $\endgroup$ May 24 '19 at 7:28

Wouldn't gambler's ruin work? It has a lower bound (being bankrupt), and it is discrete finite MC. You can calculate the probability of being bankrupt too.

  • $\begingroup$ In 1991, Professor Papadimitriou proposed a randomised algorithm that solves 2SAT in quadratic time with high probability. The associated Markov chain model can indeed be reinterpreted in terms of the gambler's ruin problem. Your intuition is correct. Unfortunately, this type of algorithms cannot be proved efficient for 3SAT,. More refined techniques and Markov chain models come into play, in relation to this problem. $\endgroup$ May 23 '19 at 5:48
  • $\begingroup$ I assume you read all the previous comments. Going back to the question that I asked, I was hoping for some guidance and specially references related to much deeper results in the direction mentioned in my question. Unfortunately, it seems to me that the experts are convinced that these hard problems (mentioned in my comments above ) cannot be efficiently solved by randomised algorithms in every single instance. I dare to disagree, but I am not an expert, so I will stop here. $\endgroup$ May 23 '19 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.