Take for example $\Z_2^d$ with the metric defined in exam. The diameter of $\Z_2^d$ is $d$ and for any $1$-Lipschitz function $f:\Z_2^d\rar\R$ we have $\G(f,f)\leq d/2$ and thus $\G(f/\sqrt{d/2},f/\sqrt{d/2})\leq1$; by corollary it follows that:
$$
\mu(|f-\la f\ra| > \e\sqrt d)\leq2e^{-2\vp(\e\sqrt2)}~.
$$
Though the space has diameter $d$ most of the points of $\Z_2^d$ can be found in a set where the order of variation of $f$ is at most $\sqrt d$. In particular (remember: $\l_1=2$):
$$
\mu(|f-\la f\ra| > d/4)\leq2e^{-\sqrt{d/2}}~.
$$
In the subsequent subsection we will improve significantly upon the right hand side and show that it's actually bounded by $e^{-d/16}$.
Curvature - the Bakry-Emery criterion
Following D. Bakry and M. Emery (cf. e.g. M. Ledoux) we say that the curvature of $\D_R$ is bounded from below by $C$ if
$$
\forall f\in L_2(G)\,\forall x\in G:\quad
\G_2(f,f)(x)\geq C\G(f,f)(x)~.
$$
That's the so called (infinite dimensional) Bakry-Emery criterion; it was originally aedined for diffusions on mainfolds. We are going to elaborate what this criterion con produce in a discrete setting! First of all, we notice, that in our case it's enough to check the case $x=e$, i.e.:
$$
\forall f\in L_2(G):\quad
\G_2(f,f)(e)\geq C\G(f,f)(e)~.
$$
By the Spectral Gap Theorem we must have $C\leq\l_1$. Thus if we can find some lower bound $C$ for the curvature, then $\l_1\geq C$. However, we are actually aiming at a stronger form of the concentration of measure result.
Obviously $\G_2(f,f)\geq\tfrac14\sum_{x\in R}(\nabla_x\nabla_xf)^2$. Since $x^2=e$, we have: $\nabla_x\nabla_xf=2\nabla_xf$.
In particular for the groups $\Z_2$ and $S(n)$ with $R$ the set of transpositions the curvature is bounded from below by $2$.
Put $S=R\times\{e\}\cup(\{e\}\times R$, then
\begin{eqnarray*}
\G_2(f,f)(e,e)
&=&\sum_{(x,y)\in S}\sum_{(u,v)\in S}(\nabla_{(x,y)}\nabla_{(u,v)}f(e,e))^2\\
&\geq&\sum_{x\in R}\sum_{u\in R}(\nabla_{(x,e)}\nabla_{(u,e)}f(e,e))^2
+\sum_{y\in R}\sum_{v\in R}(\nabla_{(e,y)}\nabla_{(e,v)}f(e,e))^2\\
&=&\G_2(f(.,e),f(.,e))(e)+\G_2(f(e,.),f(e,.))(e)\\
&\geq&C\sum_x(\nabla_{(x,e)}f(e,e))^2+C\sum_x(\nabla_{(e,x)}f(e,e))^2
\end{eqnarray*}
A lower bound for the curvature for $\Z_3$ with $R=\{\pm1\}$ is thus given by $3/2$.
Now we are going to apply the Bakry-Emery criterion:
$\proof$
2. We will again utilize the Hermite-Hadamard inequality for $\vp(x)=e^x$:
\begin{eqnarray*}
\G(f,e^{\l f})(y)
&=&\tfrac12\sum_{x\in R}
(f(xy)-f(y))(e^{\l f(xy)}-e^{\l f(y)})\\
&=&\tfrac12\sum_{x\in R}
\l(f(xy)-f(y))^2\frac{e^{\l f(xy)}-e^{\l f(y)}}{f(xy)-f(y)}\\
&\leq&\tfrac14\l\sum_{x\in R}(f(xy)-f(y))^2(e^{\l f(xy)}+e^{\l f(y)})
\end{eqnarray*}
Summing over $y\in G$ yields by symmetry of $R$:
$$
\la\G(f,e^{\l f})\ra\leq\l\la e^{\l f},\G(f,f)\ra~.
$$
1. By differentiation of the function $F(s)\colon=P_s\G(P_{t-s}f,P_{t-s}f)$ we get for $u=P_{t-s}f$:
$$
F^\prime(s)
=-P_s\D_R\G(u,u)+P_s\G(u,\D_Ru)+P_s\G(\D_Ru,u)
=2P_s\G_2(u,u)
\geq2CP_s\G(u,u)
=2CF(s)
$$
Hence $F(t)\geq F(0)e^{2Ct}$, i.e. for all $f$:
$$
\G(P_tf,P_tf)\leq e^{-2Ct}P_t\G(f,f)~.
$$
$\eofproof$
Now we will employ Herbst's argument to prove a concentration of measure result:
$\proof$
W.l.o.g. we may assume that $\la f\ra=0$. Put for $\l\geq0$: $F(t)\colon=\la e^{\l P_tf}\ra$. Then by lemma:
\begin{eqnarray*}
-F^\prime(t)
&=&\l\la\D_RP_tf,e^{\l P_tf}\ra
=\l\la\G(P_tf,e^{\l P_tf})\ra\\
&\leq&\l\la\l e^{P_tf},\G(P_tf,P_tf)\ra
\leq\l^2e^{-2Ct}\la e^{\l P_tf}\ra
=\l^2e^{-2Ct}F(t),
\end{eqnarray*}
Thus $(\log F)^\prime(t)\leq-\l^2 e^{-2Ct}$ and since $\log F(\infty)=0$ we conclude that $\log F(0)\leq\l^2/2C$, which by Chebyshev's inequality implies:
$$
\mu(f > \e)
=\mu(\exp(\l f) > \exp(\l\e))
\leq\exp(-\l\e)\la e^{\l f}\ra
\leq e^{-\l\e+\l^2/2C}~.
$$
Putting $\l=C\e$, we get the desired deviation inequality.
$\eofproof$