Why is a stochastic matrix a $l^2$ contraction If $P$ is a doubly stochastic matrix i.e. $P=(p_{ij})_{1\leq i,j \leq n}$ is s.t. the row sums $\sum_j p_{ij}=1$ for all $i$ and $\sum_i p_{ij}=1$ for all $j$, then may I know why
$$||Px||\leq ||x||$$
for all $x\in \mathbb{R}^n$ where $||\cdot||$ is the $l^2$ norm?
 A: It isn't.  Consider $$P = \pmatrix{1 & 0\cr 1 & 0\cr},\ x = \pmatrix{1\cr 0\cr},
\ P x = \pmatrix{1\cr 1\cr} $$
Perhaps you want to assume $P$ is doubly stochastic (elementwise nonnegative, and both row and column sums $1$)?
A: This is related to the more general formulation that if $P\colon L^2\to L^2$ is given by $Pf(x) = \int p(x,y)\,f(y)\,dy$, and
\begin{align*}
\sup_x\int|p(x,y)|\,dy &\le 1,\\
\sup_y\int|p(x,y)|\,dx &\le 1, \tag{$\ast$}
\end{align*}
then $\|P\|_{L^2\to L^2}\le 1$. To see this, recall that
\begin{align*}
\|P\|_{L^2\to L^2} &= \sup |\langle Pf,g\rangle|\\
&= \sup\bigg|\iint p(x,y)\,f(y)\,g(x)\,dy\,dx\bigg|
\end{align*}
where the sup is taken over all $f,g$ with $\|f\|_{L^2},\|g\|_{L^2}\le 1$. Then, since $|fg| \le \frac12(|f|^2 + |g|^2)$, we have
\begin{align*}
\|P\|_{L^2\to L^2}&\le \sup\bigg(\frac12\iint |p(x,y)|\,|f(y)|^2\,dy\,dx + \frac12\iint |p(x,y)|\,|g(x)|^2\,dy\,dx\bigg).
\end{align*}
Now in the first integral, integrate first with respect to $x$ and then with respect to $y$, and in the second integral, integrate first with respect to $y$ and then with respect to $x$, and the conclusion is that
\begin{align*}
\|P\|_{L^2\to L^2} \le \frac12 + \frac12 = 1.
\end{align*}
This argument can be easily adapted to the case you are interested in where $Pf$ is given by
\begin{align*}
(Pf)_x = \sum_y p_{xy}f_y
\end{align*}
and the doubly stochastic assumption gives us the two inequalities $(\ast)$, where we replace integration by summation in this case.
