# 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.

• to prove it symmetric is easy; k(x,y) = min{x,y} = min{y,x} = k(y,x) but how can I prove positive semi-definite: I need to show v^{T}Kv > 0 or show that sum(sum(c_x c_y K(x,y))) >= 0 Jun 13 at 10:22
• x, y belong to I = {1, 2, , ..., N} Jun 13 at 13:46
• Immediate proof: $K$ is the covariance matrix of Brownian motion on $\{1,2,\ldots, N\}.$
– whuber
Jun 15 at 13:17

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.

• Can you please explain how you wrote the min in an integral form. Jun 13 at 10:25
• It's a common trick. Do you understand it equals to min(x,y)? Jun 13 at 10:29
• No, I didn't really get it Jun 13 at 10:38
• I have added some explanation for it. Let me know if it's more understandable. Jun 13 at 10:45
• yeah it is vert clear, thank you sir! Jun 13 at 10:54

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.

• Quite interesting perspective! There is small typo, it should be like the following I believe: $\operatorname{var}(X_i)=\operatorname{var}(B_1)+...$ Jun 18 at 12:48
• @gunes LOL -- I am constantly surprised at what I manage to overlook.
– whuber
Jun 18 at 14:21