Solution
= Solution
For points $x_1,\ldots,x_n$ and coefficients $c_1,\ldots,c_n$,
$$
\sum_{r,s=1}^n c_rc_s k(x_r,x_s)
=\mathbb E\!\left[\left(\sum_{r=1}^n c_r\widehat\phi(x_r)\right)^2\right]\geq0.
$$
The bound $|\widehat\phi|\leq M$ ensures that this <expected value> is finite. Symmetry is immediate, so an expected outer product of a <random feature map> always defines a <positive-semidefinite kernel>.