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.
 A: Let $\mathcal X$ be any subset of $\{1...N\}$, and $|\mathcal X|=n,$ and $x_i,x_j$ be any two elements from this set.
We can write $\min(x_i,x_j)$ as below:
$$\min(x_i,x_j)=\int_0^N \mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt$$
The reason of this equality is straightforward. The first indicator function will be $1$ until $x_i$; and the second indicator function is $1$ until $x_j$. The multiplication will be $1$ if both are $1$, which means until the minimum of $x_i$ and $x_j$. The integral then can be written as
$$\begin{align}\int_0^N\mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt&=\int_0^{\min(x_i,x_j)}\mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt\\&=\int_0^{\min(x_i,x_j)}1\times 1\times dt\\&=\min(x_i,x_j)\end{align}$$
Then, we substitute in to the PSD requirement:
$$\begin{align}\sum_{i=1}^n\sum_{j=1}^n c_i c_j \min(x_i,x_j)&=\sum_{i=1}^n\sum_{j=1}^n c_i c_j \int_0^N \mathbb 1(t\leq x_i)\mathbb 1(t\leq x_j)dt \\&=\int_0^N \underbrace{\left(\sum_{i=1}^n c_i\mathbb 1(t\leq x_i)\right)}_{M(t)}\underbrace{\left(\sum_{j=1}^n c_j\mathbb 1(t\leq x_j)\right)}_{M(t)}dt\\&=\int_0^NM(t)M(t)dt=\int_0^NM(t)^2dt\geq 0\end{align}$$
Both multiplicands are equal because both summations range from $1$ to $n$. We can also change the order of summations and integrations according to Fubini's theorem (in short, the sums and integrals are finite).
This covers PSD property and you've already mentioned the symmetric property in your comment.
A: 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.
