McDiarmid's inequality works fine here. en.wikipedia.org/wiki/McDiarmid%27s_inequality

Formula 2.22 of Aldous-Fill gives you a nice formula for the variance in terms of the expected hitting time starting from the stationary distribution.

You need at least that $\int_X K(x,x)dP(x) = \infty$. So in most practical cases the answer for your question is that such thing does not happen.

@TheMoreTheMerrier A lot of the models can look very similar, for example, the SI model is a sort of rumour spreading model. The problem is that people use different metaphors and sometimes they refer to the same object. I guess infections, rumours and voting are the most common ones. Books: - Probability on Graphs by Geoffrey Grimmett - Epidemics and Rumours in Complex Networks by Draief and Massoulie - you can also have a look at some interacting particles systems books, however they tend to focus on infinite lattices and stuff like that

You are describing the "rumour spreading" model. This is a very well known stuff, and it has been studied in graphs where you pick a random vertex of it, and such vertex sends its information to a random neighbour. Have a look at people.maths.bris.ac.uk/~maajg/teaching/complexnets/rumours.‌​pdf

I am not sure about the limiting constant, but it seems that a first and second moment computation will get you the answer

It worked. I think I have to prove that the local optimum is also a global optimum, but it does not look so hard. Thanks :)