Mark, I think I am going to restate the formulation of my problem by restricting the assumption so that your answer is correct (just change the i, j to i, i+1). It's a special case, and it's still interesting. It's now interpretable as a noisy bubble-sort algorithm. Also, it is useful because I think now that my original conjecture was wrong!

I have two questions: 1. What is in the interpretation of $n\choose 2$ in the balance equation? 2. It seems that the third equality requires that $\ell(\tau)=\ell(\sigma)\pm 1$. This is always the case when $i$ and $j$ are adjacent, but not in general.

Thank you Mark!

Thanks. Typo corrected. I had briefly checked the Diaconi paper. I didn't think it applied to this case. The stationary distribution is uniform on $S$ for p=1/2 and concentrated at the ordered (inverse ordered) sequence for p=1 (=0).

Thanks. I had worked out the same equations after asking the question.

Thanks. Very helpful. The only book I had is Ewing's Calculus of Variations.

I think you replace integration by part with divergence when you deal with problems in many variables. In this case the problem is in a single variable, $x$.

Carlo, it makes sense but can you think of a counterexample?

Yes, I agree. I believe the RHS could be an even stronger $\exp(-cN\epsilon^2)$, but would be happy with the original conjecture.