For every x, y ∈ IN = {1, . . . , N} define K(x, y) = min{x, y}. Prove that K is a valid kernel I need to prove K is a valid Kernel.
x and y are positive integers, and K is the minimum of x and y.
I know I should prove K positive definite. But May I see how.

Let $B_1, B_2, \ldots, B_N, \ldots$ be a sequence of independent zero-mean unit variance random variables.  For instance, each $B_i$ could be a Rademacher variable that has a $1/2$ chance of being $+1$ and a $1/2$ chance of being $-1.$
Let $X_i = B_1 + B_2 + \cdots + B_i$ be the partial sum.  The sequence $(X_i)$ is an example of a random walk.  We are going to compute the covariance matrix of this walk.  The algebra is simple, but I will give all the details just to be perfectly clear.
Because each $X_i$ is a sum of independent (therefore uncorrelated) variables, its variance is the sum of the variances of its components, whence $$\operatorname{Var}(X_i) = \operatorname{Var}(B_1) + \operatorname{Var}(B_2) + \cdots + \operatorname{Var}(B_i)  = i.$$
Morever, when $j\gt i$ the additional terms in $X_j$ (namely, $B_{i+1} + \cdots + B_j$) are independent of $X_i$ and therefore uncorrelated with it, showing that
$$\begin{aligned}
\operatorname{Cov}(X_i, X_j) &= \operatorname{Cov}(X_i, X_i + (X_j-X_i))\\
& = \operatorname{Cov}(X_i,X_i) + \operatorname{Cov}(X_i, X_j-X_i) \\
&= \operatorname{Var}(X_i) + 0 \\
&= i.
\end{aligned}$$
Since covariance is symmetric, $$\operatorname{Cov}(X_j,X_i) = \operatorname{Cov}(X_i,X_j) = i.$$
A convenient way to express all these results is

$$\operatorname{Cov}(X_i,X_j) = \min(i,j) = K(i,j).$$

Because $K$ is a covariance matrix and all covariance matrices are positive semi-definite, it is a kernel, QED.
